分数: 366 分
问题陈述
高桥来到了节日摊位街。有 N 街上的摊位,每个摊位出售一种食品。
高桥有 M 日元。摊位上的食物 i (1 \leq i \leq N)成本 T_i 日元,购买它会带来满足感 P_i。对于每个摊位,高桥都会选择购买或不购买食物。他不能从同一个摊位购买多于一件商品。也允许根本不从任何摊位购买食物。在这种情况下,总满意度为 0.
高桥想要选择摊位组合,使得所购买食品的总成本不超过他的预算 M 日元,他想要最大化总满意度。
找到最大的总满意度。
约束
- 1 \leq N \leq 15
- 1 \leq M \leq 10^4
- 1 \leq T_i \leq 10^4 (1 \leq i \leq N)
- 1 \leq P_i \leq 10^4 (1 \leq i \leq N)
- 所有输入值均为整数。
输入
N M T_1 P_1 T_2 P_2 \vdots T_N P_N
- 第一行包含一个整数 N 代表档位数量和一个整数 M 代表金额(日元),以空格分隔。
- 以下 N 行每行描述一个档位。的 i这些行中的第 (1 \leq i \leq N) 包含价格 摊位食物的 T_i (日元) i 和满意度 P_i 通过购买获得,中间用空格分隔。
输出
在一行上打印高桥在其预算范围内可以获得的最大总满意度。
示例输入 1
3 10 3 5 4 6 5 8
示例输出 1
14
示例输入 2
4 5 3 4 3 5 6 10 2 3
示例输出 2
8
示例输入 3
8 50 12 20 15 25 10 18 8 12 20 35 5 8 18 30 7 10
示例输出 3
86
示例输入 4
15 5000 300 450 1200 1800 450 700 800 1100 150 200 2000 3500 600 950 350 500 900 1400 1100 1600 250 380 700 1050 500 780 400 620 1500 2200
示例输出 4
8160
示例输入 5
1 1 2 100
示例输出 5
0