# JOI 13 本選 IOI Manju ( DP )

IOI Manju | Aizu Online Judge
なんか難しいものから逃げてばかりな感じで不安。。。

```#include <bits/stdc++.h>
using namespace std;
const int MAXM = 1e4 + 4;
const int MAXN = 500 + 2;
const int MAXPCE = 1e4 + 4;
const int INF = 0x3f3f3f3f;

int m, n;
int p[ MAXM ];
int c[ MAXN ], e[ MAXN ];

int dp[ MAXM ]; // minimum cost of boxes to take i cookies

void solve(){
memset( dp, INF, sizeof(dp) );
dp[ 0 ] = 0;
for(int i = 0; i < n; ++i)
for(int j = m - 1; j >= 0; --j){
int nj = j + c[ i ];
if( nj > m ) nj = m;
dp[ nj ] = min( dp[ nj ], dp[ j ] + e[ i ] );
// printf("dp[ %d ] <- dp[ %d ] + %d\n", nj, j, e[ i ]);
// printf("%d\n", dp[ nj ]);
}
sort( p, p + m, greater<int>() ); // sell from the most expensive
int ans = 0;
int income = 0;
for(int i = 1; i <= m; ++i){ // buy how much
income += p[ i - 1 ];
ans = max<int>( ans, income - dp[ i ] );
}
printf("%d\n", ans);
}

int main(){
scanf("%d%d", &m, &n);
for(int i = 0; i < m; ++i)
scanf("%d", &p[ i ]);
for(int i = 0; i < n; ++i)
scanf("%d%d", &c[ i ], &e[ i ]);
solve();
return 0;
}
```