C - ナップサックと宝物 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 366 点

問題文

高橋君は冒険者として、古代遺跡の宝物庫に潜入しました。宝物庫には N 個の宝物が置かれており、高橋君はこれらの宝物をナップサックに詰めて持ち帰ろうとしています。

各宝物 i（1 \leq i \leq N）には、重さ w_i キログラムと価値 v_i が定められています。

高橋君のナップサックには、合計で最大 W キログラムまでの宝物を入れることができます。高橋君は N 個の宝物それぞれについて、ナップサックに入れるか入れないかを選びます。各宝物は最大 1 個しかなく、宝物を分割して一部だけ入れることもできません。

高橋君は、選んだ宝物の重さの合計が W キログラム以下となる範囲で、選んだ宝物の価値の合計を最大化したいと考えています。

価値の合計の最大値を求めてください。

制約

  • 1 \leq N \leq 100
  • 1 \leq W \leq 10^5
  • 1 \leq w_i \leq W
  • 1 \leq v_i \leq 10^9
  • 入力はすべて整数

入力

N W
w_1 v_1
w_2 v_2
\vdots
w_N v_N
  • 1 行目には、宝物の個数 N とナップサックの容量 W が、スペース区切りで与えられる。
  • 続く N 行の i 番目（1 \leq i \leq N）には、宝物 i の重さ w_i と価値 v_i が、スペース区切りで与えられる。

出力

選んだ宝物の価値の合計の最大値を 1 行で出力してください。

入力例 1

3 8
3 30
4 50
5 60

出力例 1

90

入力例 2

5 15
2 10
3 20
5 30
7 40
9 50

出力例 2

90

入力例 3

10 50
12 150
8 90
15 200
6 80
20 250
3 40
10 120
18 220
5 60
25 300

出力例 3

640

Score : 366 pts

Problem Statement

Takahashi, as an adventurer, has infiltrated the treasure vault of ancient ruins. There are N treasures in the vault, and Takahashi is trying to pack them into his knapsack to bring them home.

Each treasure i (1 \leq i \leq N) has a weight of w_i kilograms and a value of v_i.

Takahashi's knapsack can hold treasures with a total weight of at most W kilograms. For each of the N treasures, Takahashi chooses whether or not to put it in the knapsack. There is at most one of each treasure, and it is not possible to split a treasure and put only a part of it in the knapsack.

Takahashi wants to maximize the total value of the chosen treasures, subject to the constraint that the total weight of the chosen treasures is at most W kilograms.

Find the maximum possible total value.

Constraints

  • 1 \leq N \leq 100
  • 1 \leq W \leq 10^5
  • 1 \leq w_i \leq W
  • 1 \leq v_i \leq 10^9
  • All inputs are integers.

Input

N W
w_1 v_1
w_2 v_2
\vdots
w_N v_N
  • The first line contains the number of treasures N and the knapsack capacity W, separated by a space.
  • The i-th of the following N lines (1 \leq i \leq N) contains the weight w_i and value v_i of treasure i, separated by a space.

Output

Print the maximum possible total value of the chosen treasures on a single line.

Sample Input 1

3 8
3 30
4 50
5 60

Sample Output 1

90

Sample Input 2

5 15
2 10
3 20
5 30
7 40
9 50

Sample Output 2

90

Sample Input 3

10 50
12 150
8 90
15 200
6 80
20 250
3 40
10 120
18 220
5 60
25 300

Sample Output 3

640