直方图

题目描述

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

你可以进行以下操作任意多次（也可以是 $0$ 次）：

• 选择满足 $1 \le i \le N$ 的整数 $i$，把 $A_i$ 的值增加 $1$。此时需要支付 $C_i$ 日元。

在进行完任意次操作之后，设 $A$ 的元素中不同值的个数为 $K$，你还需要支付 $K \times X$ 日元。

支付的总金额最小是多少日元？

输入格式

输入按以下格式从标准输入给出：

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

输出格式

输出表示答案的数值。

样例

3 5
3 2
2 4
4 3

12

把 $A_1$ 加 $1$ 后，$A$ 的元素中不同值的个数变为 $2$，支付的总金额是 $C_1 + 2 \times X = 12$ 日元。无法让支付金额比这更少。

1 1
1 1

1

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

29

数据范围

• $1 \le N \le 2 \times 10^5$
• $1 \le X \le 10^6$
• $1 \le A_i, C_i \le 10^6 \, (1 \le i \le N)$
• 输入均为整数