← 返回题目列表

AtCoder · awc0085_c

C. 购物计划

中文机器翻译题面 查看原题

分数: 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