# LeetCode Shopping Offers

LeetCode Shopping Offers
In LeetCode Store, there are some kinds of items to sell. Each item has a price.
However, there are some special offers, and a special offer consists of one or more different kinds of items with a sale price.
You are given the each item's price, a set of special offers, and the number we need to buy for each item. The job is to output the lowest price you have to pay for exactly certain items as given, where you could make optimal use of the special offers.
Each special offer is represented in the form of an array, the last number represents the price you need to pay for this special offer, other numbers represents how many specific items you could get if you buy this offer.
You could use any of special offers as many times as you want.
Example 1:

Input: [2,5], [[3,0,5],[1,2,10]], [3,2]
Output: 14
Explanation:
There are two kinds of items, A and B. Their prices are $2 and$5 respectively.
In special offer 1, you can pay $5 for 3A and 0B In special offer 2, you can pay$10 for 1A and 2B.
You need to buy 3A and 2B, so you may pay $10 for 1A and 2B (special offer #2), and$4 for 2A.

Example 2:

Input: [2,3,4], [[1,1,0,4],[2,2,1,9]], [1,2,1]
Output: 11
Explanation:
The price of A is $2, and$3 for B, $4 for C. You may pay$4 for 1A and 1B, and $9 for 2A ,2B and 1C. You need to buy 1A ,2B and 1C, so you may pay$4 for 1A and 1B (special offer #1), and $3 for 1B,$4 for 1C.
You cannot add more items, though only \$9 for 2A ,2B and 1C.

Note:

1. There are at most 6 kinds of items, 100 special offers.
2. For each item, you need to buy at most 6 of them.
3. You are not allowed to buy more items than you want, even if that would lower the overall price.

class Solution {
private:
int dot(vector<int>& price, vector<int>& needs) {
int ans = 0;
for (int i = 0; i < needs.size(); ++i) {
ans += price[i] * needs[i];
}
return ans;
}
int shopping(vector<int>& price, vector<vector<int>>& special, vector<int>& needs, int idx) {
if (idx == special.size())return dot(price, needs); // 原价购买
int i = 0, n = special[idx].size();
vector<int> small_needs = needs;
for (i = 0; i < n - 1; ++i) {
if (special[idx][i] > needs[i])break;
small_needs[i] -= special[idx][i];
}
if (i == n - 1)return min(shopping(price, special, small_needs, idx) + special[idx][n - 1], shopping(price, special, needs, idx + 1));
else return shopping(price, special, needs, idx + 1);
}
public:
int shoppingOffers(vector<int>& price, vector<vector<int>>& special, vector<int>& needs) {
return shopping(price, special, needs, 0);
}
};

# LeetCode Combination Sum IV

LeetCode Combination Sum IV
Given an integer array with all positive numbers and no duplicates, find the number of possible combinations that add up to a positive integer target.
Example:

nums = [1, 2, 3]
target = 4
The possible combination ways are:
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)
Note that different sequences are counted as different combinations.
Therefore the output is 7.

What if negative numbers are allowed in the given array?
How does it change the problem?
What limitation we need to add to the question to allow negative numbers?

class Solution {
private:
void dfs(vector<int>& nums, int sum, int& ans) {
if (sum == 0) {
++ans;
return;
}
if (sum < 0)return;
for (const auto &i : nums) {
if (sum >= i) {
dfs(nums, sum - i, ans);
}
}
}
public:
int combinationSum4(vector<int>& nums, int target) {
int ans = 0;
dfs(nums, target, ans);
return ans;
}
};

class Solution {
public:
int combinationSum4(vector<int>& nums, int target) {
vector<int> dp(target + 1, 0);
dp[0] = 1;
for (int i = 0; i < nums.size(); ++i) { // 对每个数字
for (int j = target; j >= nums[i]; --j) {
dp[j] += dp[j - nums[i]]; // 取值；不取dp[j]保持不变；所以取和不取加起来就是+=dp[j-nums[i]]
}
}
return dp[target];
}
};

class Solution {
public:
int combinationSum4(vector<int>& nums, int target) {
vector<int> dp(target + 1, 0);
dp[0] = 1;
for (int i = 1; i <= target; ++i) {
for (int j = 0; j < nums.size(); ++j) {
if (i >= nums[j])dp[i] += dp[i - nums[j]];
}
}
return dp[target];
}
};

# hihoCoder 1506-投掷硬币

hihoCoder 1506-投掷硬币

### 输出

2 1
0.5 0.5

0.500000

#include<iostream>
#include<cstdlib>
#include<algorithm>
#include<vector>
#include<string>
#include<unordered_map>
using namespace std;
double ans = 0;
int n, m;
void dfs(const vector<double>& probs, double curprob, int step, int up) {
if (up == m) {
double oneans = curprob;
for (int i = step; i < n; ++i)oneans *= (1 - probs[i]);
ans += oneans;
return;
}
if (step < n) {
dfs(probs, curprob*probs[step], step + 1, up + 1);
dfs(probs, curprob*(1 - probs[step]), step + 1, up);
}
}
int main() {
//freopen("input.txt", "r", stdin);
scanf("%d %d", &n, &m);
vector<double> probs(n, 0);
for (int i = 0; i < n; ++i) scanf("%lf", &probs[i]);
dfs(probs, 1, 0, 0);
printf("%lf\n", ans);
return 0;
}

#include<iostream>
#include<cstdlib>
#include<algorithm>
#include<vector>
#include<string>
#include<unordered_map>
using namespace std;
int main() {
//freopen("input.txt", "r", stdin);
int n, m;
scanf("%d %d", &n, &m);
vector<double> probs(n + 1, 0);
for (int i = 1; i <= n; ++i)scanf("%lf", &probs[i]);
vector<vector<double>> dp(n + 1, vector<double>(n + 1, 0));
dp[0][0] = 1.0;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= i; ++j) { //现在有i枚硬币，所以正面向上的个数j不超过i
dp[i][j] += dp[i - 1][j - 1] * probs[i];  // head
dp[i][j - 1] += dp[i - 1][j - 1] * (1 - probs[i]); // tail
}
}
printf("%lf\n", dp[n][m]);
return 0;
}

# LeetCode Target Sum

LeetCode Target Sum
You are given a list of non-negative integers, a1, a2, ..., an, and a target, S. Now you have 2 symbols + and -. For each integer, you should choose one from + and - as its new symbol.
Find out how many ways to assign symbols to make sum of integers equal to target S.
Example 1:

Input: nums is [1, 1, 1, 1, 1], S is 3.
Output: 5
Explanation:
-1+1+1+1+1 = 3
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3
There are 5 ways to assign symbols to make the sum of nums be target 3.

Note:

1. The length of the given array is positive and will not exceed 20.
2. The sum of elements in the given array will not exceed 1000.
3. Your output answer is guaranteed to be fitted in a 32-bit integer.

class Solution {
private:
void dfs(vector<int>& nums, int step, int S, int& ans) {
if (step == nums.size() && S == 0) {
++ans;
return;
}
if (step == nums.size())return;
dfs(nums, step + 1, S - nums[step], ans);
dfs(nums, step + 1, S + nums[step], ans);
}
public:
int findTargetSumWays(vector<int>& nums, int S) {
int ans = 0;
dfs(nums, 0, S, ans);
return ans;
}
};

dp[i][j]=dp[i-1][j-nums[i]]+dp[i-1][j+nums[i]]

DP的代码如下：

class Solution {
public:
int findTargetSumWays(vector<int>& nums, int S) {
int n = nums.size(), sum = 0;
for (int i = 0; i < n; ++i)sum += nums[i];
if (S<-sum || S>sum)return 0;
//if (S == -sum || S == sum)return 1; // nums={1,0},S=1; 1=1+0=1-0
vector<vector<int>> dp(n + 1, vector<int>(2 * sum + 1, 0));
dp[0][sum] = 1;
for (int i = 1; i <= n; ++i) {
for (int j = 0; j < 2 * sum + 1; ++j) {
//考虑第i个数字是+还是-
//i从1开始，所以第i个数字的下标是i-1
if (j >= nums[i - 1])dp[i][j] += dp[i - 1][j - nums[i - 1]];
if (j + nums[i - 1] < 2 * sum + 1)dp[i][j] += dp[i - 1][j + nums[i - 1]];
}
}
return dp[n][S + sum];
}
};

DP的问题一般都可以优化空间，比如上述代码可以用两个数组互相滚动赋值来代替n+1个数组。

class Solution {
public:
int findTargetSumWays(vector<int>& nums, int S) {
int n = nums.size(), sum = 0;
for (int i = 0; i < n; ++i)sum += nums[i];
if (S<-sum || S>sum)return 0;
vector<vector<int>> dp(2, vector<int>(2 * sum + 1, 0));
int i = 0, pre = (i & 1) ? 1 : 0, cur = (i & 1) ? 0 : 1;
dp[pre][sum] = 1; // 取0个数字，加和为0的方案有1种。把和0偏移到sum位置
while (i < n) {
pre = (i & 1) ? 1 : 0;
cur = (i & 1) ? 0 : 1;
for (int j = 0; j < 2 * sum + 1; ++j) {
if (dp[pre][j] != 0) {
if (j + nums[i] < 2 * sum + 1)dp[cur][j + nums[i]] += dp[pre][j]; // 在j的基础上加nums[i]
if (j - nums[i] >= 0)dp[cur][j - nums[i]] += dp[pre][j]; // 在j的基础上减nums[i]
}
}
fill(dp[pre].begin(), dp[pre].end(), 0); // 清空pre数组，因为下一轮pre要用作cur数组
++i;
}
return dp[cur][S + sum];
}
};

# LeetCode Ones and Zeroes

LeetCode Ones and Zeroes
In the computer world, use restricted resource you have to generate maximum benefit is what we always want to pursue.
For now, suppose you are a dominator of m 0s and n 1s respectively. On the other hand, there is an array with strings consisting of only 0s and 1s.
Now your task is to find the maximum number of strings that you can form with given m 0s and n 1s. Each 0 and 1 can be used at most once.
Note:

1. The given numbers of 0s and 1s will both not exceed 100
2. The size of given string array won't exceed 600.

Example 1:

Input: Array = {"10", "0001", "111001", "1", "0"}, m = 5, n = 3
Output: 4
Explanation: This are totally 4 strings can be formed by the using of 5 0s and 3 1s, which are “10,”0001”,”1”,”0”

Example 2:

Input: Array = {"10", "0", "1"}, m = 1, n = 1
Output: 2
Explanation: You could form "10", but then you'd have nothing left. Better form "0" and "1".

class Solution {
public:
int findMaxForm(vector<string>& strs, int m, int n) {
vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
for (int i = 0; i < strs.size(); ++i) {
vector<int> cnts(2, 0);
for (int j = 0; j < strs[i].size(); ++j)++cnts[strs[i][j] - '0'];
for (int j = m; j >= cnts[0]; --j) {
for (int k = n; k >= cnts[1]; --k) {
dp[j][k] = max(dp[j][k], dp[j - cnts[0]][k - cnts[1]] + 1);
}
}
}
return dp[m][n];
}
};

# HDOJ 3535-AreYouBusy

HDOJ 3535-AreYouBusy
AreYouBusy
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 3450 Accepted Submission(s): 1342
Problem Description
Happy New Term!
As having become a junior, xiaoA recognizes that there is not much time for her to AC problems, because there are some other things for her to do, which makes her nearly mad.
What's more, her boss tells her that for some sets of duties, she must choose at least one job to do, but for some sets of things, she can only choose at most one to do, which is meaningless to the boss. And for others, she can do of her will. We just define the things that she can choose as "jobs". A job takes time , and gives xiaoA some points of happiness (which means that she is always willing to do the jobs).So can you choose the best sets of them to give her the maximum points of happiness and also to be a good junior(which means that she should follow the boss's advice)?
Input
There are several test cases, each test case begins with two integers n and T (0<=n,T<=100) , n sets of jobs for you to choose and T minutes for her to do them. Follows are n sets of description, each of which starts with two integers m and s (0<m<=100), there are m jobs in this set , and the set type is s, (0 stands for the sets that should choose at least 1 job to do, 1 for the sets that should choose at most 1 , and 2 for the one you can choose freely).then m pairs of integers ci,gi follows (0<=ci,gi<=100), means the ith job cost ci minutes to finish and gi points of happiness can be gained by finishing it. One job can be done only once.
Output
One line for each test case contains the maximum points of happiness we can choose from all jobs .if she can’t finish what her boss want, just output -1 .
Sample Input
3 3
2 1
2 5
3 8
2 0
1 0
2 1
3 2
4 3
2 1
1 1
3 4
2 1
2 5
3 8
2 0
1 1
2 8
3 2
4 4
2 1
1 1
1 1
1 0
2 1
5 3
2 0
1 0
2 1
2 0
2 2
1 1
2 0
3 2
2 1
2 1
1 5
2 8
3 2
3 8
4 9
5 10
Sample Output
5
13
-1
-1
Author
hphp
Source
2010 ACM-ICPC Multi-University Training Contest（10）——Host by HEU
Recommend
zhouzeyong | We have carefully selected several similar problems for you: 3033 1712 3449 2639 2159

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
using namespace std;
const int kMaxN = 105, kINF = 0x7ffffff;
int dp[kMaxN][kMaxN];
int main()
{
//freopen("input.txt", "r", stdin);
int n, t;
while (~scanf("%d %d", &n, &t))
{
for (int i = 0; i < kMaxN; i++)
for (int j = 0; j < kMaxN; j++)
dp[i][j] = -kINF;
for (int i = 0; i < kMaxN; i++)
dp[0][i] = 0;
int m, s, c, g;
for (int i = 1; i <= n; i++) { scanf("%d %d", &m, &s); if (s == 0) { while (m--) { scanf("%d %d", &c, &g); for (int j = t; j >=c; j--)
dp[i][j] = max(dp[i][j], max(dp[i - 1][j - c] + g, dp[i][j - c] + g));
}
}
else if (s == 1)
{
for (int j = t; j >= 0; j--)
dp[i][j] = dp[i - 1][j];
while (m--)
{
scanf("%d %d", &c, &g);
for (int j = t; j >= c; j--)
dp[i][j] = max(dp[i][j], dp[i - 1][j - c] + g);
}
}
else if (s == 2)
{
for (int j = t; j >= 0; j--)
dp[i][j] = dp[i - 1][j];
while (m--)
{
scanf("%d %d", &c, &g);
for (int j = t; j >= c; j--)
dp[i][j] = max(dp[i][j], max(dp[i - 1][j - c] + g, dp[i][j - c] + g));
}
}
}
printf("%d\n", max(dp[n][t], -1));
}
return 0;
}

# hihoCoder 1137-Recruitment

hihoCoder 1137-Recruitment
#1137 : Recruitment

A company plans to recruit some new employees. There are N candidates (indexed from 1 to N) have taken the recruitment examination. After the examination, the well-estimated ability value as well as the expected salary per year of each candidate is collected by the Human Resource Department.
Now the company need to choose their new employees according to these data. To maximize the company's benefits, some principles should be followed:
1. There should be exactly X males and Y females.
2. The sum of salaries per year of the chosen candidates should not exceed the given budget B.
3. The sum of ability values of the chosen candidates should be maximum, without breaking the previous principles. Based on this, the sum of the salary per year should be minimum.
4. If there are multiple answers, choose the lexicographically smallest one. In other words, you should minimize the smallest index of the chosen candidates; If there are still multiple answers, then minimize the second smallest index; If still multiple answers, then minimize the third smallest one; ...
Your task is to help the company choose the new employees from those candidates.

The first line contains four integers N, X, Y, and B, separated by a single space. The meanings of all these variables are showed in the description above. 1 <= N <= 100, 0 <= X <= N, 0 <= Y <= N, 1 <= X + Y <= N, 1 <= B <= 1000.
Then follows N lines. The i-th line contains the data of the i-th candidate: a character G, and two integers V and S, separated by a single space. G indicates the gender (either "M" for male, or "F" for female), V is the well-estimated ability value and S is the expected salary per year of this candidate. 1 <= V <= 10000, 0 <= S <= 10.
We assure that there is always at least one possible answer.

On the first line, output the sum of ability values and the sum of salaries per year of the chosen candidates, separated by a single space.
On the second line, output the indexes of the chosen candidates in ascending order, separated by a single space.

4 1 1 10
F 2 3
M 7 6
M 3 2
F 9 9

9 9
1 2

DP的状态转移过程为：假设dpm[i][j]表示从【当前】所有男性中选取i个，工资总和为j时获得的最大能力总和。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int kMaxN = 105, kMaxB = 1005;
int dpf[kMaxN][kMaxB], dpm[kMaxN][kMaxB];//dpf[i][j]从所有女性应聘者中选取i个，工资总和为j时的最大能力和
unsigned long long idf[kMaxN][kMaxB][2];//记录女性选取情况
unsigned long long idm[kMaxN][kMaxB][2];//记录男性选取情况
int N, X, Y, B, V, S;
char G[2];
int ans_v = 0, ans_s = 0;//总能力，总工资
unsigned long long ans_id[2] = { 0 };//总选取情况
void DP()
{
dpf[0][0] = dpm[0][0] = 0;
int cnt_f = 0, cnt_m = 0, sum_s = 0;
for (int i = 1; i <= N; i++)
{
scanf("%s %d %d", G, &V, &S);
sum_s += S;
sum_s = min(sum_s, B);
if (G[0] == 'F')
{
cnt_f++;
cnt_f = min(cnt_f, Y);//最多选取Y位
for (int j = cnt_f; j >= 1; j--)
{
for (int k = sum_s; k >= S; k--)
{
if (dpf[j - 1][k - S] < 0)
continue;
if (dpf[j - 1][k - S] + V > dpf[j][k])
{
dpf[j][k] = dpf[j - 1][k - S] + V;
idf[j][k][0] = idf[j - 1][k - S][0];
idf[j][k][1] = idf[j - 1][k - S][1];
if (i <= 50)
idf[j][k][0] |= 1LL << (i - 1);//选中第i位
else
idf[j][k][1] |= 1LL << (i - 1 - 50);//选中第i位
}
}
}
}
else
{
cnt_m++;
cnt_m = min(cnt_m, X);
for (int j = cnt_m; j >= 1; j--)
{
for (int k = sum_s; k >= S; k--)
{
if (dpm[j - 1][k - S] < 0)
continue;
if (dpm[j - 1][k - S] + V > dpm[j][k])
{
dpm[j][k] = dpm[j - 1][k - S] + V;
idm[j][k][0] = idm[j - 1][k - S][0];
idm[j][k][1] = idm[j - 1][k - S][1];
if (i <= 50)
idm[j][k][0] |= 1LL << (i - 1);
else
idm[j][k][1] |= 1LL << (i - 1 - 50);
}
}
}
}
}
}
void Match()
{
for (int i = 0; i <= B; i++)
{
if (dpf[Y][i] == -1)
continue;
for (int j = 0; j + i <= B; j++)
{
if (dpm[X][j] == -1)
continue;
if (dpf[Y][i] + dpm[X][j] > ans_v)//能力更强
{
ans_v = dpf[Y][i] + dpm[X][j];
ans_s = i + j;
ans_id[0] = idf[Y][i][0] | idm[X][j][0];
ans_id[1] = idf[Y][i][1] | idm[X][j][1];
}
else if (dpf[Y][i] + dpm[X][j] == ans_v && (i + j) < ans_s)//能力相同，但工资更少
{
ans_s = i + j;
ans_id[0] = idf[Y][i][0] | idm[X][j][0];
ans_id[1] = idf[Y][i][1] | idm[X][j][1];
}
else if (dpf[Y][i] + dpm[X][j] == ans_v && (i + j) == ans_s)//能力和工资都相同
{
int id0 = idf[Y][i][0] | idm[X][j][0];
int id1 = idf[Y][i][1] | idm[X][j][1];
if (ans_id[0] > id0)//排序靠前
{
ans_id[0] = id0;
ans_id[1] = id1;
}
else if (ans_id[1] > id1)//排序靠前
{
ans_id[0] = id0;
ans_id[1] = id1;
}
}
}
}
}
void FormatOut()
{
printf("%d %d\n", ans_v, ans_s);
for (int i = 1; i <= 50; i++)
{
if (ans_id[0] & 1)
printf("%d ", i);
ans_id[0] >>= 1;
}
for (int i = 51; i <= 100; i++)
{
if (ans_id[1] & 1)
printf("%d ", i);
ans_id[1] >>= 1;
}
}
int main()
{
memset(dpf, -1, sizeof(dpf));
memset(dpm, -1, sizeof(dpm));
memset(idf, 0, sizeof(idf));
memset(idm, 0, sizeof(idm));
scanf("%d %d %d %d", &N, &X, &Y, &B);
DP();
Match();
FormatOut();
return 0;
}

# POJ 1837-Balance

POJ 1837-Balance
Balance
Time Limit: 1000MS Memory Limit: 30000K
Total Submissions: 10845 Accepted: 6742
Description
Gigel has a strange "balance" and he wants to poise it. Actually, the device is different from any other ordinary balance.
It orders two arms of negligible weight and each arm's length is 15. Some hooks are attached to these arms and Gigel wants to hang up some weights from his collection of G weights (1 <= G <= 20) knowing that these weights have distinct values in the range 1..25. Gigel may droop any weight of any hook but he is forced to use all the weights.
Finally, Gigel managed to balance the device using the experience he gained at the National Olympiad in Informatics. Now he would like to know in how many ways the device can be balanced.
Knowing the repartition of the hooks and the set of the weights write a program that calculates the number of possibilities to balance the device.
It is guaranteed that will exist at least one solution for each test case at the evaluation.
Input
The input has the following structure:
• the first line contains the number C (2 <= C <= 20) and the number G (2 <= G <= 20);
• the next line contains C integer numbers (these numbers are also distinct and sorted in ascending order) in the range -15..15 representing the repartition of the hooks; each number represents the position relative to the center of the balance on the X axis (when no weights are attached the device is balanced and lined up to the X axis; the absolute value of the distances represents the distance between the hook and the balance center and the sign of the numbers determines the arm of the balance to which the hook is attached: '-' for the left arm and '+' for the right arm);
• on the next line there are G natural, distinct and sorted in ascending order numbers in the range 1..25 representing the weights' values.
Output
The output contains the number M representing the number of possibilities to poise the balance.
Sample Input
2 4
-2 3
3 4 5 8
Sample Output
2
Source
Romania OI 2002

#include<iostream>
using namespace std;
int c[21];
int w[21];
int dp[21][15001];
int main()
{
int n,g;
cin>>n>>g;
for(int i=1;i<=n;i++)
cin>>c[i];
for(int i=1;i<=g;i++)
cin>>w[i];
dp[0][7500]=1;//不挂任何砝码的时候它本身就平衡了，所以是一种“挂法”
for(int i=1;i<=g;i++)//对于每一个砝码
{
for(int j=0;j<=15000;j++)//挂上去之后可能使天平出现0-15000中的任意一种状态
{
if(dp[i-1][j])//如果这个状态之前出现过，则直接用
{
for(int k=1;k<=n;k++)
{
dp[i][j+w[i]*c[k]]+=dp[i-1][j];
}
}
}
}
cout<<dp[g][7500]<<endl;
return 0;
}

# hihoCoder 1043-完全背包

hihoCoder 1043-完全背包
#1043 : 完全背包

5 1000
144 990
487 436
210 673
567 58
1056 897

5940

#include <iostream>
#include<vector>
using namespace std;
int main()
{
int n,m;
cin>>n>>m;
vector<int> need_vi(n),value_vi(n);
for(int i=0;i<n;i++)
cin>>need_vi[i]>>value_vi[i];
vector<int> V(m+1,0);//V[j]表示有j张奖券，装前i个奖品获得的最大评分
for(int i=0;i<n;i++)//V[j]表示有j张奖券，装前i个奖品获得的最大评分，每个奖品可以装多个
{
for(int j=need_vi[i];j<=m;j++)//从前往后填表，因为这是完全背包
{
V[j]=(V[j-need_vi[i]]+value_vi[i]>V[j])?(V[j-need_vi[i]]+value_vi[i]):V[j];
}
}
cout<<V[m];
return 0;
}

# hihoCoder 1038-01背包

hihoCoder 1038-01背包
#1038 : 01背包

5 1000
144 990
487 436
210 673
567 58
1056 897

2099

#include<iostream>
#include<vector>
using namespace std;
int main()
{
int n,m;
cin>>n>>m;
vector<int> need_vi(n);//所需奖券
vector<int> value_vi(n);//评分值
for(int i=0;i<n;i++)
cin>>need_vi[i]>>value_vi[i];
vector<int> V(m+1,0);//V[j]表示有j张奖券，装前i个奖品获得的最大评分
for(int i=0;i<n;i++)//V[j]表示有j张奖券，装前i个奖品获得的最大评分
{
for(int j=m;j>=need_vi[i];j--)//从后往前填表，能减少空间
{
V[j]=(V[j-need_vi[i]]+value_vi[i]>V[j])?(V[j-need_vi[i]]+value_vi[i]):V[j];//要这件奖品和不要的对比
}
}
cout<<V[m];
return 0;
}