题目描述

長さ $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$

输出格式

答えを表す数値を出力せよ。

题目大意

给定两个正整数序列 $A$ 与 $C$ , 你可以做任意次操作, 每次操作你可以花费 $C_i$ 的代价给 $A_i$ 加上 $1$ .

设操作完后的序列 $A$ 有 $K$ 个不同的元素, 这会造成 $K\times X$ 的代价, 其中 $X$ 为给定常数.

最小化总代价.

3 5
3 2
2 4
4 3

12

1 1
1 1

1

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

29

提示

制約

• $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) $
• 入力は全て整数である。

Sample Explanation 1

$A_1$ に $1$ 加算すると $A$ の要素の種類数は $2$ になり、支払う金額の合計は $C_1\ +\ 2\ \times\ X\ =\ 12$ 円となります。支払う金額をこれより少なくすることはできません。