Description

pigstd has a set of numbers. He wants to choose some of them and arrange them into a sequence, denoted as $x_{1},x_{2},\cdots,x_{p}$ (where $p$ is the number of chosen elements).

This sequence is valid if and only if it satisfies the following conditions:

• $p \ge 2$.
• Let $y_{i} = x_{i + 1} - x_{i}$ (in particular, $y_{p}=x_{1}-x_{p}$). If we arrange $y_{1}$ to $y_{p}$ into a cycle in the order $y_1,y_2,\cdots,y_p$, then every two adjacent numbers are opposite to each other, and their absolute values are all $k$.

pigstd wants to know, among all valid sequences, what the maximum possible sum of all numbers in the sequence is.

Input Format

The first line contains two integers $n,k$.

The next $n$ lines each contain two integers $a_{i},b_{i}$, meaning pigstd has $b_{i}$ copies of $a_{i}$.

It is not guaranteed that the $a_{i}$ are distinct. If some $a_{i}$ are the same, their counts should be added together.

Output Format

Output one integer in one line, representing the maximum sum of all numbers in a valid permutation.

If there is no valid permutation, output only $\texttt{NO}$.

4 3 
1 5
2 4
3 3
0 2

6

Hint

[Sample 1 Explanation]

When pigstd's permutation is $0,3,0,3$ or $3,0,3,0$, the sum is maximized and equals $6$.

[Constraints]

For $100\%$ of the testdata, $1 \le n \le 10^6$, $0 \le k,a_{i} \le 10^6$, $1 \le b_{i} \le 10^6$.

This problem uses bundled testcases.

• Subtask 1 (5 points): It is guaranteed that there is no valid sequence.
• Subtask 2 (15 points): $k = 0$.
• Subtask 3 (5 points): $n = 1$.
• Subtask 4 (5 points): $n = 2$.
• Subtask 5 (30 points): $n,k,a_i,b_i \le 10^3$.
• Subtask 6 (40 points): No special restrictions apply.

Translated by ChatGPT 5