题目描述

清明节期间，小 C 参加了社区组织的踏青插柳活动。活动场地被划分为 $n$ 个连续的区域，每个区域需要 $x_i$ 的时间布置场地和准备柳枝，之后每次在该区域插柳需要 $y_i$ 的时间。如果多次在某个区域插柳，则只需在第一次布置场地，后续插柳无需重复布置（即如果想在第 $i$ 区域插柳 $t$ 次，所需时间为 $x_i+ t \times y_i$）。

小 C 必须按照区域的顺序依次进行布置和插柳（即只有完成第一个区域后，才能进入第二个区域，以此类推）。她需要完成总计 $m$ 次插柳任务（可以重复选择某些区域），求她完成所有任务所需的最少时间。

输入格式

第一行，两个整数 $n, m$，分别表示区域的数量和需要完成的插柳总次数。

接下来 $n$ 行，每行两个整数 $x_i, y_i$，别表示第 $i$ 个区的布置时间和单次插柳时间。

输出格式

输出完成 $m$ 次插柳任务所需的最少时间。

样例

3 4
3 4
2 3
4 2

18

样例 1 解释

• 第一次完成第一个区域：布置 $3$ 分钟，插柳 $4$ 分钟，总计 $7$ 分钟。
• 第二次完成第二个区域：布置 $2$ 分钟，插柳 $3$ 分钟，总计 $5$ 分钟（累计时间 $12$ 分钟）。
• 第三次继续选择第二个区域：插柳 $3$ 分钟（无需重新布置），总计 $3$ 分钟（累计时间 $15$ 分钟）。
• 第四次继续选择第二个区域：插柳 $3$ 分钟（无需重新布置），总计 $3$ 分钟（累计时间 $18$ 分钟）。

为了最小化总时间，小 C 选择在完成第一个区域后，多次在第二个区域插柳。

数据范围

对于 $50\%$ 的数据，$1 \leq n, m \leq 10^4$。

对于 $100\%$ 的数据，$1 \leq n, m \leq 2 \times 10^5 \\$，$1 \leq x_i, y_i \leq 10^9$。