题目描述

小慧在玩一个智力通关游戏，这个游戏有 $n$ 个关卡，每个关卡需要 $x_i$ 的时间看说明书，需要 $y_i$ 的时间通关。但如果想多次通过某个关卡，则只需第一次看说明书，后面不用再看（即如果想打通第 $i$ 关 $t$ 次，则所需时间为 $x_i + t \times y_i$）。

游戏时，必须按次序通关（即只有打通第一关，才能进行第二关，如此类推），求小慧要通 $m$ 次关的最少时间（可以重复通关）。

输入格式

第一行，两个整数 $n, m$。

接下来 $n$ 行，每行两个整数 $x_i, y_i$。

输出格式

输出一个整数，表示通关 $m$ 次所需的最少时间。

样例

3 4
3 4
2 3
4 2

18

提示

第一次通第一关用 $7$ 分钟（看说明 $3$ + 通关 $4$），

第二次通第二关用 $5$ 分钟（看说明 $2$ + 通关 $3$），

第三次继续通第二关用 $3$ 分钟（不需再看说明），

第四次继续通第二关用 $3$ 分钟。

总时间 $7+5+3+3=18$。

数据范围

• 对于 $50\%$ 的数据：$1 \le n, m \le 10^4$
• 对于 $100\%$ 的数据：$1 \le n, m \le 2 \times 10^5$，$1 \le x_i, y_i \le 10^9$
• 注意：答案可能超出 $32$ 位整数范围，请使用 $64$ 位整数类型