Shopping List Optimization

Today, Jinming is upset because he is not allowed to design his own spacious room in his new second-hand house. His mom has imposed two restrictions on his shopping: (1) the total cost must not exceed \(W\) yuan, and (2) the difference between the most expensive and the cheapest items in his shopping list must not exceed \(3\) yuan. Each item has an importance value \(p_i\) and a price \(v_i\) (both integers). Jinming wants to choose a subset of items that satisfies these restrictions while maximizing the total importance \(\sum p_i\). Your task is to determine the maximum total importance Jinming can achieve under these conditions.

Note: All formulas are written in \(\LaTeX\) format. The chosen items must have their maximum price minus minimum price \(\le 3\), and the total price cannot exceed \(W\) (it can equal \(W\)).

inputFormat

The first line contains two integers \(N\) and \(W\): the number of available items and the maximum budget respectively.

Then follow \(N\) lines, each containing two integers \(p_i\) and \(v_i\), where \(p_i\) is the importance of the \(i\)-th item, and \(v_i\) is its price.

outputFormat

Output a single integer, the maximum total importance that can be achieved while selecting a valid subset of items.

sample

4 10
5 3
3 4
7 5
4 3

12