Herb Collection Optimization

Chencheng is a gifted child whose dream is to become the greatest physician in the world. To test his abilities, a renowned doctor presents him with a challenge in a herb-filled cave. In this cave, there are several different herbs; each herb requires a certain amount of time to collect and has its own value. You are given a total available time, and your task is to collect a subset of herbs such that their total value is maximized while the total collection time does not exceed the given time.

Formally, you are given a total time T and a list of N herbs. Each herb i requires a time t_i to collect and has a value v_i. You must choose a subset of these herbs such that:

[ \sum_{i \in S} t_i \le T ]

and the sum of their values is maximized:

[ \text{Maximize } \sum_{i \in S} v_i ]

inputFormat

The first line contains two integers N and T (1 ≤ N ≤ 1000, 1 ≤ T ≤ 10⁵), representing the number of herbs and the total available time, respectively.

Each of the next N lines contains two integers t_i and v_i (1 ≤ t_i ≤ T, 1 ≤ v_i ≤ 10⁵), representing the time required to collect the i-th herb and its corresponding value.

outputFormat

Output a single integer, the maximum total value of herbs that can be collected without exceeding the total available time T.

sample

3 7
2 10
3 15
4 20

35