小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