当前没有测试数据。

H - 直方图

得分：600 分

问题描述

给定长度为 $N$ 的整数序列：$A = (A_1, \dots, A_N)$ 和 $C = (C_1, \dots, 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 \ (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