题目描述

给定两个长度为 $N$ 的整数序列: $A = (A_1, \ldots, A_N)$ 和 $C = (C_1, \ldots, C_N)$。

你可以任意多次（包括零次）地进行以下操作：

• 选择一个整数 $i$ ，满足 $1 \leq i \leq N$，将 $A_i$ 的值加 $1$，花费 $C_i$ 日元（日本货币单位）。

在完成操作后，你必须支付 $K \times X$ 日元，其中 $K$ 是 $A$ 元素中不同值的个数。

你需要支付的最小总金额是多少？

约束条件

• $1 \leq N \leq 2 \times 10^5$
• $1 \leq X \leq 10^6$
• $1 \leq A_i, C_i \leq 10^6 \quad (1 \leq i \leq N)$
• 输入中的所有值都是整数。

输入

输入以以下格式从标准输入给出:

$N$ $X$ $A_1$ $C_1$ $\vdots$ $A_N$ $C_N$

输出

打印表示答案的数字。

示例输入 1

3 5
3 2
2 4
4 3

示例输出 1

12

在将 $A_1$ 加 $1$ 后，$A$ 元素中将有两个不同的值，总花费为 $C_1 + 2 \times X = 12$ 日元。无法使总花费少于此金额。

示例输入 2

1 1
1 1

示例输出 2

1

示例输入 3

7 7
3 2
1 7
4 1
1 8
5 2
9 8
2 1

示例输出 3

29