AT_code_thanks_festival_2017_c Factory

工厂里有 $N$ 台制造礼物的机器。第 $i$ 台机器（$1 \leq i \leq N$）最开始制造 $1$ 个礼物需要 $a_i$ 秒。 但是，每当某台机器制造一个礼物后，只有该台机器会劣化，下一次制造相同的礼物所需的时间会增加 $b_i$ 秒。 因此，第 $i$ 台机器在制造第 $s_i$ 个礼物时需要 $a_i + (s_i - 1) \times b_i$ 秒。 此外，由于工厂的电力供应有限，不能同时让多台机器运行。 现在，"イルカ" 想以尽可能短的时间制造 $K$ 个礼物。 请你求出制造这些礼物所需的最少总时间。

输入以如下格式从标准输入给出。 > $N \ K \ a_1 \ b_1 \ a_2 \ b_2 \ldots a_N \ b_N$

请输出制造所有礼物所需的最小总时间。

### 限制条件 - $1 \leq N \leq 10^5$ - $1 \leq K \leq 10^5$ - $1 \leq a_i \leq 10^9$ - $0 \leq b_i \leq 10^9$ - 所有输入均为整数。 ### 样例说明 1 当让工厂中的每台机器运行如下次数时，可以在 $5$ 秒内制造出 $3$ 个礼物。 - 第 $1$ 台机器：$1$ 次 - 第 $2$ 台机器：$2$ 次 - 第 $3$ 台机器：$0$ 次 ### 样例说明 2 请注意防止溢出。 由 ChatGPT 5 翻译