题目描述

商店在 $n$ 天中出售商品。对于第 $i$ 天，出售 $k_i$ 件商品，会有有 $l_i$ 个顾客购买商品。每个顾客买且只买一件商品。

商店的老板会选择 $f$ 天。在这 $f$ 天中，每天出售的商品数量为原来出售商品数量的两倍。老板想知道，如何选择这 $f$ 天，能使出售的商品最多。

输入格式

第一行两个整数 $n$ 和 $f\ (1\le n\le 10^5,0\le f\le n)$。

接下来的 $n$ 行，每行两个整数 $k_i$ 和 $l_i\ (0\le ki,li\le 10^9)$，表示每天出售的商品数量和顾客人数。

输出格式

一行一个整数，表示商店在选择 $f$ 天后，可销售产品的最大数量。

4 2
2 1
3 5
2 3
1 5

10

4 1
0 2
0 3
3 5
0 6

5