벼락치기

ChAOS(Chung-ang Algorithm Organization and Study) 회장을 맡은 뒤로 일이 많아진 준석이는 시험 기간에도 일에 밀려 공부를 못 하다가 시험 전날을 맞았다. 다행히 교수님이 시험 전에 다음 두 가지를 공지했다.

1. 여러 단원을 융합한 문제는 출제하지 않는다.
2. 한 단원에서 한 문제를 출제한다. 단, 그 단원의 내용을 모두 알아야 풀 수 있는 문제를 낸다.

교수님은 이 힌트와 함께 단원별 배점도 적어 두었다. 어떤 단원의 문제를 맞히려면 그 단원의 예상 공부 시간만큼, 또는 그보다 더 오래 공부해야 한다고 하자. 각 단원은 공부하거나 공부하지 않거나 둘 중 하나이고, 부분 점수는 없다.

남은 시간 동안 공부해서 준석이가 얻을 수 있는 최대 점수를 구하라.

첫째 줄에 이번 시험의 단원 개수 $N$($1 \le N \le 100$)과 시험까지 공부할 수 있는 총 시간 $T$($1 \le T \le 10000$)가 공백을 사이에 두고 주어진다.

둘째 줄부터 $N$개 줄에 걸쳐 각 단원의 예상 공부 시간 $K$($1 \le K \le 1000$)와 그 단원 문제의 배점 $S$($1 \le S \le 1000$)가 공백을 사이에 두고 주어진다.

첫째 줄에 준석이가 얻을 수 있는 최대 점수를 출력한다.