102287: [AtCoder]ABC228 H - Histogram

Problem Statement

Given are integer sequences of length $N$ each: $A = (A_1, \dots, A_N)$ and $C = (C_1, \dots, C_N)$.

You can do the following operation any number of times, possibly zero.

• Choose an integer $i$ such that $1 \leq i \leq N$ and add $1$ to the value of $A_i$, for a cost of $C_i$ yen (Japanese currency).

After you are done with the operation, you have to pay $K \times X$ yen, where $K$ is the number of different values among the elements of $A$.

What is the minimum total amount of money you have to pay?

Constraints

• $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)$
• All values in input are integers.

Input

Input is given from Standard Input in the following format:

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

Output

Print a number representing the answer.

Sample Input 1

3 5
3 2
2 4
4 3

Sample Output 1

12

After adding $1$ to $A_1$, there will be two different values among the elements of $A$, for a total cost of $C_1 + 2 \times X = 12$ yen. It is impossible to make the total cost less than this.

Sample Input 2

1 1
1 1

Sample Output 2

1

Sample Input 3

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

Sample Output 3

29

问题描述

给定长度为$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