Maximum Satisfaction

You are given N dishes, each with a satisfaction value S_i and a preparation time t_i. You have a total available time of T units. Your task is to select a subset of dishes such that the total preparation time does not exceed T while the total satisfaction is maximized.

The problem can be formulated as follows:

Maximize \(\sum S_i\)

subject to \(\sum t_i \le T\).

Read the input from standard input and output the maximum satisfaction to standard output.

inputFormat

The first line contains two integers N and T, where:

• N is the number of dishes.
• T is the total available time.

Each of the following N lines contains two integers: S (the satisfaction value of a dish) and t (the preparation time for that dish).

Input is read from standard input.

outputFormat

Output a single integer which is the maximum total satisfaction that can be achieved without exceeding the total available time T.

Output is written to standard output.

## sample

4 5
10 2
20 2
30 3
40 4

50