暑假！有人去旅行，有人去看望祖父母，但有人想找份兼职工作。今年夏天，努拉决定要挣点钱，于是在一家商店做了一份店员。
    努拉工作的商店在接下来的 n 天里有一个计划。每一天，销售经理都确切地知道，在第 i 天，ki 的产品将被出售，而 li 的客户也将在那天来到商店。此外，经理确信，每个来到商店的人都只买了一种产品，或者，如果没有剩余的产品，就什么也不买就离开了商店。此外，由于产品的保质期较短，经理制定了以下规则：如果一天结束时部分产品留在货架上，则第二天不保存该产品，并将其送到垃圾场。
    为了做广告，经理主动提出在商店里开始销售。他让努拉从 n 中选择任意 f 天进行销售。在选定的 f 天中，出售的产品数量都将增加一倍。因此，如果第i天商店计划出售 ki 产品，而努拉选择在这一天，商店的货架上会有 2 × ki 个产品。因此，在这些天数中，有机会卖出两倍的产品。
    努拉的任务是选择 f 天数，以最大限度地增加售出产品的总数。

第一行两个整数n和f (1<=n<=10⁵, 0<=f<=n)。

接下来的n行，每行两个整数ki和li (0<=ki, li<=10⁹ )，表示每天出售的商品数量和顾客人数。

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

【样例说明】 我们可以选择第2天和第4天，在这种情况下，新的销售产品数量将分别等于[2,6,2,2]。所以在第一天，商店将销售1种产品，第二天销售5种，第三天销售2种，第四天销售2种。总共1+5+2+2=10个产品。

【数据范围】

30%的数据，1≤n≤100，0<=f<=n ，0<=ki, li<=1000。

70%的数据，1≤n≤10000，0<=f<=n ，0<=ki, li<=10⁶

100%的数据， 1≤n≤10⁵，0<=f<=n ，0<=ki, li<=10⁹。