http://paiza.jp/poh/kirishima/result/712087ffa2ff08c13307c84b871be06c

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
using namespace std;
int main(){
int M, N, i, j;
scanf("%d%d",&M, &N);
vector<int> num(N), cost(N);
for( i=0; i<N; i++) scanf("%d%d",&num[i],&cost[i] );
unsigned int total = accumulate(num.begin(), num.end(), 0);
vector<unsigned int> X(total+1 ,-1); X[0]=0;
for(j=0; j<N; j++) {
int k = num[j];
for( i=total-k; i>=0; i--) if( X[i]!=-1 ) {
int x = X[i]+cost[j];
if( X[k+i]>x ) X[k+i]=x;
}}
cout<< *min_element(X.begin()+M, X.end()) << endl;
return 0; }