31 lines
513 B
C
31 lines
513 B
C
#include <stdio.h>
|
|
|
|
#define MAX_COST 100000
|
|
|
|
int min(int a, int b) {
|
|
return a > b ? b : a;
|
|
}
|
|
|
|
int dp[1101];
|
|
|
|
int main() {
|
|
int C, N;
|
|
scanf("%d %d",&C, &N);
|
|
|
|
dp[0] = 0;
|
|
for(int i=1; i<=C+100; i++) dp[i] = MAX_COST;
|
|
|
|
while(N--) {
|
|
int cost, man;
|
|
scanf("%d %d",&cost, &man);
|
|
|
|
for(int c=man; c<C+101; c++) dp[c] = min(dp[c], dp[c-man] + cost);
|
|
}
|
|
|
|
int ans = MAX_COST;
|
|
for(int i=C; i<C+101; i++) ans = min(ans, dp[i]);
|
|
|
|
printf("%d\n",ans);
|
|
|
|
return 0;
|
|
} |