You are given n ad impressions. Each impression has a value and a cost (floor price). You have a fixed budget B.

Your task is to select a subset of impressions such that the total cost does not exceed B, while maximizing the total value of the selected impressions.

Input Format

The first line contains two integers n and B — the number of impressions and the available budget.

The next n lines each contain two integers:

value — the value of the impression.

cost — the cost (floor price) of the impression.

Output Format

Print a single integer — the maximum total value that can be obtained without exceeding the budget.

Constraints

1 ≤ n ≤ 1000

1 ≤ B ≤ 10^5

1 ≤ value ≤ 10^9

1 ≤ cost ≤ 10^5

Sample Input

4 10 10 5 40 4 30 6 50 3

Sample Output

90

Explanation

Select the 2nd and 4th impressions:

Total Cost = 4 + 3 = 7 (within the budget of 10)

Total Value = 40 + 50 = 90

No other valid selection yields a higher total value.