Cramming

Junseok became the president of ChAOS (Chung-ang Algorithm Organization and Study), the work piled up, and he never got around to studying during the exam period. Now it is the night before the exam. The professor did post two hints beforehand.

1. No question mixes several chapters.
2. Each chapter gets exactly one question. That question can only be solved by someone who knows everything in the chapter.

The professor also wrote down the score of each chapter next to the hints. Assume Junseok gets a chapter's question right if he studies that chapter for its estimated study time or longer. A chapter is either studied or not studied, and there is no partial credit.

Find the highest total score Junseok can reach with the time he has left.

The first line contains the number of chapters on the exam $N$ ($1 \le N \le 100$) and the total time available before the exam $T$ ($1 \le T \le 10000$), separated by a space.

Each of the next $N$ lines contains the estimated study time $K$ ($1 \le K \le 1000$) of one chapter and the score $S$ ($1 \le S \le 1000$) of that chapter's question, separated by a space.

Print the highest score Junseok can get on the first line.