Problem Description
For food, the happiest thing for the New Year is to eat, none!
But for girls, calories (calories) are natural enemies!
Senior beauty “is well versed in the principle of” fat coming like mountains, fat goes like a shredded “, so she hopes that you can help develop a recipe, so that she can eat happily, and will not create too many natural enemies.
But for girls, calories (calories) are natural enemies!
Senior beauty “is well versed in the principle of” fat coming like mountains, fat goes like a shredded “, so she hopes that you can help develop a recipe, so that she can eat happily, and will not create too many natural enemies.
Of course, in order to make you make a recipe, it has given you a daily food list, which describes the happiness that each food she wants to eat that day and the amount of calories that will be increased.
Input
Input contains multiple groups of test cases.
Each set of data starts with an integer n, indicating that there are N kinds of food in the daily food list.
The next N line, two integer A and B per line, of which A means that this kind of food can bring the happiness value (the larger the value, the happier the value), and B means that eating this food will be absorbed by it will be absorbed Calculating.
At the end is an integer M, which means that 湫湫 湫湫 湫湫 湫湫 9 9 9 9 9 9 9 9 9 m.
Each set of data starts with an integer n, indicating that there are N kinds of food in the daily food list.
The next N line, two integer A and B per line, of which A means that this kind of food can bring the happiness value (the larger the value, the happier the value), and B means that eating this food will be absorbed by it will be absorbed Calculating.
At the end is an integer M, which means that 湫湫 湫湫 湫湫 湫湫 9 9 9 9 9 9 9 9 9 m.
[Technical Specification]
1. 1 <= n <= 100
2. 0 <= a,b <= 100000
3. 1 <= m <= 100000
Output
Pay an integer on each list, that is, the maximum happiness value can be obtained while satisfying the absorption amount in the calories.
Sample Input
3 3 3 7 7 9 9 10 5 1 1 5 3 10 3 6 8 7 5 6
Sample Output
10 20
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
using namespace std;
int dp[200010],w[100010],v[100010];
int main()
{
int n,i,j,m;
while(~scanf("%d",&n))
{
memset(dp,0,sizeof(dp));
for(i=0;i<n;++i)
scanf("%d%d",&v[i],&w[i]);
scanf("%d",&m);
for(i=0;i<n;++i)
for(j=w[i];j<=m;++j)
dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
printf("%d\n",dp[m]);
}
return 0;
}