题目描述

pigstd 有一堆数，他想在这么多数中选出若干个数排成一列，记为 $x_{1},x_{2},\cdots,x_{p}$（$p$ 为数的个数）。

这一列数合法当且仅当满足以下条件：

• $p \ge 2$。
• 令 $y_{i} = x_{i + 1} - x_{i}$（特别的，$y_{p}=x_{1}-x_{p}$），如果把 $y_{1}$ 到 $y_{p}$ 按 $y_1,y_2,\cdots,y_p$ 的顺序排成一圈，那么每两个相邻的数互为相反数且绝对值都为 $k$。

pigstd 想知道，在所有合法的数列中，所有在这个数列中的数之和最大是多少。

输入格式

第一行两个整数 $n,k$。

接下来 $n$ 行，每行两个整数 $a_{i},b_{i}$，表示 pigstd 有 $b_{i}$ 个 $a_{i}$。

不保证 $a_{i}$ 互不相同，若有 $a_{i}$ 相同则累加其个数计算。

输出格式

一行一个整数，表示在每一种排列中，所有在这个排列中的数的最大的和。

若没有合法的排列，则只输出 $\texttt{NO}$。

4 3 
1 5
2 4
3 3
0 2

6

提示

【样例 1 说明】

当 pigstd 的排列为：$0,3,0,3$ 或 $3,0,3,0$ 时，总和最大，为 $6$。

【数据规模与约定】

对于 $100\%$ 的数据，$1 \le n \le 10^6$，$0 \le k,a_{i} \le 10^6$，$1 \le b_{i} \le 10^6$。

本题采用捆绑测试。

• Subtask 1（5 points）：保证无合法的数列；
• 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）：无特殊限制。