문제 설명
여름방학을 맞이한 루루는 평소 관심있던 프로그래밍을 공부하기 위해 인터넷 강의 사이트에 접속했다. 인터넷 강의 사이트에는 총 N개의 강좌가 개설되어 있으며, 각각의 강좌에는 수강에 필요한 비용(포인트)과 수료 시 얻게 되는 경험치가 제시되어 있다. 루루는 N개의 강좌 중 가지고 있는 포인트 한도 내에서 자유롭게 강좌를 선택해서 수강할 예정이며, 여름방학이 끝나기 전까지 경험치를 최대한 많이 쌓아보려고 한다.
예를 들어, 5개의 강좌가 다음과 같이 개설되었으며, 루루에게 현재 300 포인트가 있다고 가정해보자.
이 경우, 세종이는 285포인트을 사용해서 B, C, E 강좌를 수강하여 700만큼의 경험치를 얻을 수 있다. 또한, 265포인트을 사용하여 A, C, E 강좌를 수강할 수 있으며 940만큼의 경험치를 얻을 수 있고, 이 경우 루루가 여름방학 동안 얻을 수 있는 경험치의 최댓값이다. N개의 강좌와 루루가 지닌 포인트가 주어질 때, 루루가 얻을 수 있는 경험치의 최댓값을 출력하시오.
예를 들어, 5개의 강좌가 다음과 같이 개설되었으며, 루루에게 현재 300 포인트가 있다고 가정해보자.
| 강좌 | A | B | C | D | E |
| 비용(포인트) | 180 | 200 | 50 | 40 | 35 |
| 경험치 | 540 | 300 | 200 | 40 | 200 |
이 경우, 세종이는 285포인트을 사용해서 B, C, E 강좌를 수강하여 700만큼의 경험치를 얻을 수 있다. 또한, 265포인트을 사용하여 A, C, E 강좌를 수강할 수 있으며 940만큼의 경험치를 얻을 수 있고, 이 경우 루루가 여름방학 동안 얻을 수 있는 경험치의 최댓값이다. N개의 강좌와 루루가 지닌 포인트가 주어질 때, 루루가 얻을 수 있는 경험치의 최댓값을 출력하시오.
입력 설명
첫째 줄에는 강좌의 수 n과 루루가 가지고 있는 포인트 p가 주어진다.
둘째 줄부터 (n+1)째 줄까지 강좌에 해당하는 포인트와 경험치가 주어진다.
(1<=n<=40)
(1<=P<=100,000,000)
(1<=Pi, Ci<=2,000,000)
둘째 줄부터 (n+1)째 줄까지 강좌에 해당하는 포인트와 경험치가 주어진다.
(1<=n<=40)
(1<=P<=100,000,000)
(1<=Pi, Ci<=2,000,000)
출력 설명
루루가 얻을 수 있는 경험치의 최댓값을 출력한다.
입력 예시 Copy
5 300
180 540
200 300
50 200
40 40
35 200
출력 예시 Copy
940