C - Shopping Plan Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 366 点

問題文

高橋君はお祭りの屋台街にやってきました。屋台街には N 個の屋台があり、それぞれの屋台で食べ物が1つずつ売られています。

高橋君の所持金は M 円です。屋台 i（1 \leq i \leq N）の食べ物の値段は T_i 円で、これを購入すると満足度 P_i が得られます。高橋君は各屋台について、食べ物を購入するか購入しないかのいずれかを選びます。同じ屋台の食べ物を2つ以上購入することはできません。また、どの屋台の食べ物も購入しないことも許されます。その場合、満足度の合計は 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
  • 1 行目には、屋台の数を表す整数 N と、所持金（円）を表す整数 M が、スペース区切りで与えられる。
  • 続く N 行の i 行目（1 \leq i \leq N）には、屋台 i の食べ物の値段 T_i（円）と、購入したときに得られる満足度 P_i が、スペース区切りで与えられる。

出力

高橋君が所持金以内で得られる満足度の合計の最大値を 1 行で出力してください。

入力例 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

Score : 366 pts

Problem Statement

Takahashi has come to a street of festival stalls. There are N stalls on the street, and each stall sells one type of food item.

Takahashi has M yen. The food at stall i (1 \leq i \leq N) costs T_i yen, and purchasing it gives a satisfaction of P_i. For each stall, Takahashi chooses either to purchase the food or not. He cannot purchase more than one item from the same stall. It is also allowed to not purchase food from any stall at all. In that case, the total satisfaction is 0.

Takahashi wants to choose a combination of stalls such that the total cost of the purchased food items does not exceed his budget of M yen, and he wants to maximize the total satisfaction.

Find the maximum total satisfaction.

Constraints

  • 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)
  • All input values are integers.

Input

N M
T_1 P_1
T_2 P_2
\vdots
T_N P_N
  • The first line contains an integer N representing the number of stalls and an integer M representing the amount of money (in yen), separated by a space.
  • The following N lines each describe a stall. The i-th of these lines (1 \leq i \leq N) contains the price T_i (in yen) of the food at stall i and the satisfaction P_i obtained by purchasing it, separated by a space.

Output

Print the maximum total satisfaction that Takahashi can obtain within his budget, on a single line.

Sample Input 1

3 10
3 5
4 6
5 8

Sample Output 1

14

Sample Input 2

4 5
3 4
3 5
6 10
2 3

Sample Output 2

8

Sample Input 3

8 50
12 20
15 25
10 18
8 12
20 35
5 8
18 30
7 10

Sample Output 3

86

Sample Input 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

Sample Output 4

8160

Sample Input 5

1 1
2 100

Sample Output 5

0