Informatica Online Judge

  샙낵 문제 (Sackknap Problem) [1935 / 078F]

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


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

[koistudy.net (34th 김한빈)]
Writer ID : [gs16023]

Background

Robbery 영건은 젊은시절 이름을 날린 Robbery 이다.
하지만 자신의 인생에 회의를 느낀 영건은, Robbery 생활을 접고 귀농하기 직전, 마지막 의뢰를 받게 된다.

마지막 의뢰는 거인 TaeJu에게서 온 의뢰였다.
거인 TaeJu는 자신의 게으른 생활을 영위하기 위해, Robbery 영건에게 백화점에서 보석을 Robbery하라고 의뢰한 것이다.
이를 괘씸히 여긴 Robbery 영건은 거인 TaeJu를 골탕먹일 궁리를 해냈다.
다행히 백화점 안에는 식품매장도 함께 있기 때문에, Robbery 영건은 보석 대신 값싼 식료품을 Robbery하기로 했다.
거인 TaeJu는 매우 게으르기 때문에, 가방 안에 무엇이 들었는지 잘 확인하지 않기 때문이다.
거인 Taeju에게 줄 가방을 매우 값싼 식료품들로 채운다면 거인 TaeJu를 멋지게 골탕먹일 수 있을 것이다.

다만 가방의 무게가 너무 가벼우면 TaeJu의 의심이 귀찮음을 이겨 가방 안을 확인하게 된다.
거인 TaeJu는 거인이므로 매우 힘이 세서, 가방 안의 내용물을 확인한다면 복수로 무슨 짓을 할지 모른다.
Robbery 영건이 거인 TaeJu의 복수에 당하지 않고 안전히 골탕먹일 수 있도록 도와주도록 하자.
Robbery 영건은 젊은 시절 이름을 날렸기 때문에, 총 가격만 알려주면 그에 맞게 훔칠 수 있다.

단, Robbery 영건은 마음씨가 착해 식료품 한 가지당 한 개밖에 훔치지 않는다.

Input

첫 줄에 식료품의 가짓수 n과 거인 TaeJu가 의심하지 않는 가장 가벼운 무게 V가 주어진다.(1<=n<=1000,1<=V<=1000)

둘째 줄 부터 n+1번째 줄 까지 식료품 각각의 무게 w와 가격 c이 차례대로 주어진다.(1<=w,c<=10000)

Output

첫 줄에 거인 TaeJu가 의심하지 않으면서, 가장 가격이 싸게 담았을 때의 가격을 출력한다.

IO Example

입력
4 10
7 3
4 2
3 6
1 10

출력
5

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