Posted on 2008-06-05 09:56
superman 阅读(288)
评论(0) 编辑 收藏 引用 所属分类:
ZOJ
1 /* Accepted 1366 C++ 00:09.36 936K */
2 #include <iostream>
3
4 using namespace std;
5
6 int main()
7 {
8 int cash, N, n[11], d[11];
9 bool x[100001];
10
11 while(cin >> cash >> N)
12 {
13 for(int i = 1; i <= N; i++)
14 scanf("%d %d", n + i, d + i);
15
16 memset(x, false, cash + 1);
17
18 x[0] = true;
19 for(int i = 1; i <= N; i++)
20 for(int j = cash; j >= d[i]; j--)
21 for(int k = 1; k <= n[i]; k++)
22 if(d[i] * k <= j)
23 x[j] = x[j] || x[j - d[i] * k];
24 else
25 break;
26 for(int i = cash; i >= 0; i--)
27 if(x[i])
28 {
29 cout << i << endl; break;
30 }
31 }
32
33 return 0;
34 }
35