P6785 "EZEC-3" Permutation

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.

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 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}$.**

**[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