Knapsack3
Xem dạng PDF
Gửi bài giải
Điểm:
35,00 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
256M
Input:
stdin
Output:
stdout
Tác giả:
Người đăng:
Dạng bài
Ngôn ngữ cho phép
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch
There are N items, numbered ~1, 2,..., N~. For each ~i~ (~1 ≤ i ≤ N)~, Item ~i~ has a weight of ~w_i~ and a value of ~v_i~ Taro has decided to choose some of the ~N~ items and carry them home in a knapsack. The capacity of the knapsack is ~W~, which means that the sum of the weights of items taken must be at most ~W~. Find the maximum possible sum of the values of items that Taro takes home.
Constraints
• All values in input are integers.
• ~1 ≤ N ≤ 18~
• ~1 ≤ W ≤ 5*10^9~
• ~1≤ w_i≤ 10^9~
• ~1 ≤ v_i ≤ 10^9~
Input
Input is given from Standard Input in the following format:
~N~ ~W~
~w_1 v_I~
~w_2 v_2~
:
~w_N v_N~
Output
Print the maximum possible sum of the values of items that Taro takes home.
Example 1
Input
3 8
3 30
4 50
5 60
Output
90
Example 2
Input
1 1000000000
1000000000 10
Output
10
Example 3
Input
6 15
6 5
5 6
6 4
6 6
3 5
7 2
Output
17
Bình luận
where tên tác giả :))))
hic, quay lui thật à ;-;
qlui ez
:)
:)) chịu thôi chứ sao