Ecstasy of Gold

Dirty Fred and his ferocious gang successfully broke into the treasury of Goliath Multicontinental Bank at last! Inside the treasury they found a deposit of gold bars. The bars have similar (though not necessarily equal) weights, but at the same time their respective values can differ a lot, based on how fine the gold is. Formally, every gold bar has two characteristics: its weight w_i and its value v_i, where the difference between the weights of the lightest and the heaviest bars does not exceed 3.

Luckily for them, Fred's trained eyes can measure the value of any gold bar immediately. There is a problem though: the members of the gang — even though they trained hard — have a combined strength of W, meaning that they can carry at most W units of weight in total.

This capacity may not be enough to take every gold bar with them, so your task is to help them determine the maximum total value of gold bars they can steal, provided the total weight of the stolen bars does not exceed W.

Input Specification

The first line of the input contains the number of gold bars N (1 ≤ N ≤ 100) and the combined strength of the gang W (1 ≤ W ≤ 10⁹).

Each of the next N lines contains two integers w_i and v_i, describing one of the gold bars (1 ≤ w_i ≤ 10⁹, 1 ≤ v_i ≤ 10⁷). The difference between the highest and lowest weights w_max and w_min is at most 3, i.e., w_max ≤ w_min + 3.

Output Specification

Print a single line containing the highest total value of gold bars they can steal, provided the total weight of the stolen bars does not exceed W.

Sample Input 1

1. 4 6
2. 2 1
3. 3 4
4. 4 10
5. 3 4

download as text file

Output for Sample Input 1

1. 11

download as text file

Sample Input 2

1. 4 6
2. 2 1
3. 3 7
4. 4 10
5. 3 6

download as text file

Output for Sample Input 2

1. 13

download as text file

Sample Input 3

1. 1 10
2. 20 100
3. 15 200

download as text file

Output for Sample Input 3

1. 0

download as text file

In the first example, they can steal the first and the third bar, as their total weight is 2 + 4 = 6. In this case, the total value of the stolen bars is 1 + 10 = 11.