Meal

Interview

Time limit1sMemory limit256 MB

Summary

Pick one of two daily menu items for N days, staying within a total budget X, to maximize the sum of tastiness ratings.

Level: Medium5 of 10
Topics: Greedy, Sorting, Implementation, Prefix sum
Solved: No attempts yet

Problem

The cafeteria in the student union building at Jeju National University has two menus. Going to corner A lets you eat a 5,000-won menu, and going to corner B lets you eat a 1,000-won menu.

Because in-person classes have started, Junwon must eat exactly one of the two cafeteria menus every day for the remaining $N$ days of the semester. The two menus for the $N$ days are already announced, and Junwon has already rated how tasty each menu is on each day.

Junwon may spend at most $X$ won in total on the cafeteria over the $N$ days.

Choose Junwon's menus over the $N$ days so that the sum of the tastiness of the chosen menus is maximized.

Input

The first line gives two integers $N$ and $X$ .

Each of the next $N$ lines gives the tastiness $A$ of the 5,000-won menu available on that day and the tastiness $B$ of the 1,000-won menu available on that day, separated by a space.

Output

Print the maximum possible sum of the tastiness of the menus Junwon chooses.

Constraints

$1 \le N \le 100\,000$
$1\,000N \le X \le 5\,000N$
$1 \le A \le 10,000$ , $1 \le B \le 10,000$

Examples3

Example 1
Input
```
3 9000
40 10
20 5
30 20
```
Expected output
```
65
```
Example 2
Input
```
1 1000
30 10
```
Expected output
```
10
```
Example 3
Input
```
1 5000
10 30
```
Expected output
```
30
```