Description

Jinming is very unhappy today. The family is about to get the keys to a second-hand apartment, but there is no spacious room exclusively for him. What makes him even more upset is that his mom told him yesterday: "Which items to buy and how to arrange them is not up to you (there are many restrictions), and moreover the total must not exceed $W$ yuan." Early this morning, Jinming started budgeting, but there are so many things he wants to buy that he will surely exceed the $W$ yuan limit. So, he assigns to each item an integer importance $p_i$. He also looked up the price $v_i$ of each item on the Internet (all in integer yuan).

After reviewing the shopping list, his mom requires that the range of the prices of all items on the list (the most expensive minus the cheapest) must not exceed $3$ (of course Jinming still does not know why). He hopes, under the constraint that the total cost does not exceed $W$ yuan (it can be equal to $W$), to maximize the total importance $\sum p_i$.

Please help Jinming design a shopping list that meets the requirements. You only need to tell us the maximum possible sum of importance.

Input Format

The first line contains two positive integers, separated by a space: $N, W$ (where $W$ is the total amount of money, and $N$ is the number of items he wants to buy).

From line $2$ to line $N + 1$, the $j$-th line gives the basic data of the item with ID $j - 1$. Each line contains $2$ non-negative integers $v, p$ (where $v$ is the price of that item, and $p$ is its importance).

Output Format

Output a single positive integer: the maximum possible sum of importance of items whose total cost does not exceed the total amount of money.

5 10
2 800
5 400
5 300
3 400
2 200

1600

Hint

$1 \le N \le 100$.

$1 \le W \le 10^9$.

$1 \le v_i \le 10^9$.

For all $i = 1, 2, 3, \dots, N$, $\min(v_i) \le v_i \le \min(v_i) + 3$.

$1 \le p_i \le 10^7$.

Translated by ChatGPT 5