AT_abc228_h [ABC228H] Histogram

题目描述

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

你可以进行任意次数（可以为 $0$ 次）如下操作：

• 选择一个满足 $1 \leq i \leq N$ 的整数 $i$，将 $A_i$ 的值加 $1$。此时需要支付 $C_i$ 日元的费用。

在进行任意次数操作后，设 $A$ 中元素的种类数为 $K$，你还需要支付 $K \times X$ 日元。

请问你最少需要支付多少日元？

输入格式

输入以以下格式从标准输入读入。

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

输出格式

输出表示答案的数值。

输入输出样例 #1

输入 #1

3 5
3 2
2 4
4 3

输出 #1

12

输入输出样例 #2

输入 #2

1 1
1 1

输出 #2

1

输入输出样例 #3

输入 #3

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

输出 #3

29

说明/提示

限制条件

• $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)$
• 所有输入均为整数。

样例解释 1

将 $A_1$ 加 $1$ 后，$A$ 的元素种类数为 $2$，总支付金额为 $C_1 + 2 \times X = 12$ 日元。无法再减少支付金额。

由 ChatGPT 4.1 翻译