← 返回题目列表

AtCoder · abc228_h

H. 直方图

中文机器翻译题面 查看原题

分数: 600 点

问题陈述

给定长度的整数序列 N 每个: A = (A_1, \dots, A_N) 和 C = (C_1, \dots, C_N).

您可以执行以下操作任意次数,可能为零。

  • 选择一个整数 i 这样 1 \leq i \leq N 并添加 1 的值 A_i,费用为 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

添加后 1 to A_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