Informatica Online Judge

  가방 채우기 [1242 / 04DA]

Time Limit(Test case) : 1000 (ms)
Number of users who solved : 84   Total Tried : 323


The Champion of this Problem (C++) : gs18012 - 0ms / 303byte
My Best Submission (C++) : N/A

[JeongHJ]

Background

동규는 정올 예선대회 참가를 위해 일찍 일어나 무엇을 준비해야 할까 고민하다가 일찍 시험장에 도착해서 공부를 하기로 마음먹었다.

어떤 책을 가져가는가에 따라 성적에 차이가 있을것이라고 생각하고 책별 가치를 정하였다. 모든 책을 가져가는 것이 가장 좋겠지만 가방에 넣을 수 있는 책의 무게는 정해져 있다.

가방의 책의 가치가 최대가 되도록 가방을 채우는 것이 목적이다. 단, 모든 책은 한 권씩만 있다.

Input

첫번째 줄에는 책의 수 n과 가방의 무게 w가 입력된다.
두번째 줄부터는 각 책의 무게 ni와 가치가 pi가 입력된다.

[입력값의 정의역]
1 <= n <= 20
1 <= w <= 100
1 <= ni, pi <= 100

Output

가방의 무게가 w를 초과하지 않으면서 책의 가치의 총합의 최대값을 출력한다.

IO Example

입력
4 5
2 3
1 2
3 3
2 2

출력
7

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]