UOJ Logo

NOI.AC

1S 512MB

#12. B

统计

小w是一个热心肠的少年,这天,他来到了肥宅聚集地,用吸脂手术帮助肥宅减肥。

这里聚集着 $n$ 个肥宅,第 $i$ 个肥宅的体重为 $b_i$,每过一天,每个肥宅的体重就会增加 $a_i$。小w每天只能进行一场手术,为一个体重为 $c$ 的肥宅做手术,小w的成本也为 $c$。

因为时间有限,小w准备只帮助 $k$ 个肥宅,请问小w最小需要花费多少成本呢?

输入格式

第一行两个整数,$n$ 和 $k$。

接下来 $n$ 行,每行两个整数 $a_i$ 和 $b_i$,表示第 $i$ 个肥宅的身体指标。

输出格式

一行一个整数,表示小w最小要花费的成本。

样例一

input

3 3
1 0
2 1
3 2

output

7

样例二

input

3 3
5 4
2 3
6 1

output

17

数据范围

时间限制1s,空间限制512MB

测试点编号 $n$的规模 $a_i, b_i$的规模
1,2$n \leq 20$$a_i \leq 10^6, b_i \leq 10^{11}$
3,4$n \leq 2000$
5,6$n \leq 10^5$
7,8,9,10$n \leq 10^6$