零崎有很多朋友，其中有一個叫做lfj的接盤俠。
lfj是一個手殘，他和零崎一起玩網游的時候不好好打本，天天看拍賣行，沒過多久，就成為了一個出色的商人。時間一長，雖然掙了不少錢，卻沒時間練級了。
作為lfj的友人，零崎實在看不下去，於是他決定幫lfj一把。當然了，零崎肯定不會自己動手，活還得你們來干。
lfj可以提供給你們拍賣行所有能買到物品的價格和利潤，由於游戲產出不限，所以可以假定只要有錢，即使是同一種東西，多少個也都能買到手。lfj還會告訴你他初始的成本。雖然零崎想讓你們給出一次交易中利潤最大的購買方案，但是lfj覺得只要知道最大利潤就可以了。
每組數據第一行為兩個整數P和N，表示本金和拍賣行物品種類數。
接下來N行，每行兩個數據pi,ci代表第i類物品的利潤和購買價格。
1<=P<=20000,1<=N<=300,1<=c,p<=200
對於每組數據，輸出一行，為能獲得的最大利潤
3 1
2 1
2 3
1 1
1 2
2 16
4使用if直接比較不要調用max（）以防超時
完全背包問題：
完全背包和0-1背包的不同之處：完全背包的物品不再是只有一件而是有無數件，所以對於某一件物品也不再是拿（1）不拿（0）。而是變為了拿0件，1件，2件...k件,按照0-1背包問題的狀態轉移方程同樣可以寫出完全背包的狀態轉移方程：
f[i][v]=max{f[i-1][v-k*c[i]]+k*w[i]|0<=k*c[i]<=v}
分析上述的狀態轉移方程
這跟01背包問題一樣有O(N*V)個狀態需要求解，但求解每個狀態的時間已經不是常數了，求解狀態f[i][v]的時間是O(v/c[i])，總的復雜度是超過O(VN)的。
因此我們需要對改狀態方程進行改進：
O(VN)的算法：
1 for (int i = 1; i <= N; i++) 2 3 for (int v = 0; v <= V; v++) 4 5 f[v] = max(f[v], f[v - c[i]] + w[i]);
或者f[i][v]=max(f[i-1][v],f[i][v-c[i]]+w[i])
可以發現和0-1背包不同的地方只是在於內部for循環的起止改變了順序，為什麼這樣可以實現完全背包的要求呢？
首先想想為什麼P01中要按照v=V..0的逆序來循環。這是因為要保證第i次循環中的狀態f[i][v]是由狀態f[i-1][v-c[i]]遞推而來。換句話說，這正是為了保證每件物品只選一次，保證在考慮“選入第i件物品”這件策略時，依據的是一個絕無已經選入第i件物品的子結果f[i-1][v-c[i]]。而現在完全背包的特點恰是每種物品可選無限件，所以在考慮“加選一件第i種物品”這種策略時，卻正需要一個可能已選入第i種物品的子結果f[i][v-c[i]]，所以就可以並且必須采用v= 0..V的順序循環。這就是這個簡單的程序為何成立的道理。
因此可以得到完全背包的代碼實現：
1 void CompletePack(int cost , int weight)
2 {
3 for (int i = weight ; i <= W ; ++ i)
4 f[i] = max(f[i],f[i-weight]+cost) ;
5 }
下面給出本題的代碼實現：
1 #include <bits/stdc++.h>
2 long long f[20010];
3 long long c[310];
4 long long v[310];
5 using namespace std;
6
7 int main()
8 {
9 int V,k;
10 while(~scanf("%d%d",&V,&k))
11 {
12 memset(f,0,sizeof(f));
13 memset(c,0,sizeof(c));
14 memset(v,0,sizeof(v));
15 for(int i=1; i<=k; i++)
16 scanf("%lld%lld",&v[i],&c[i]);
17 for(int i=1; i<=k; i++)
18 {
19 for(int j=c[i]; j<=V; j++)
20 {
21 if(f[j-c[i]]+v[i]>=f[j])
22 f[j]=f[j-c[i]]+v[i];
23 else
24 f[j]=f[j];
25 }
26 }
27 printf("%lld\n",f[V]);
28 }
29 }
