평범한 배낭

준서는 한 달 뒤에 입대한다. 그 전에 여행을 다녀오려고 하는데, 세상과 잠시 떨어지는 만큼 최대한 즐기고 싶어서 배낭도 최대한 가치 있게 싸려고 한다.

준서가 여행에 필요하다고 생각하는 물건은 $N$개다. 각 물건에는 무게 $W$와 가치 $V$가 정해져 있고, 그 물건을 배낭에 넣어서 가면 준서는 $V$만큼 즐길 수 있다. 아직 행군을 해본 적이 없는 준서는 담은 무게의 합이 $K$를 넘지 않는 배낭만 들고 다닐 수 있다.

물건은 하나씩만 있으므로 각 물건을 넣거나 넣지 않는 선택만 한다. 준서가 최대한 즐거운 여행을 하도록, 배낭에 넣을 수 있는 물건의 가치 합의 최댓값을 구하라.

첫 줄에 물건의 수 $N$과 준서가 버틸 수 있는 무게 $K$가 주어진다. ($1 \le N \le 100$, $1 \le K \le 100{,}000$)

둘째 줄부터 $N$개의 줄에 각 물건의 무게 $W$와 가치 $V$가 한 줄에 하나씩 주어진다. ($1 \le W \le 100{,}000$, $0 \le V \le 1{,}000$)

입력으로 주어지는 모든 수는 정수다.

배낭에 넣을 수 있는 물건의 가치 합의 최댓값을 한 줄에 출력한다.