2779. [Codeforces 810B] 夏季大甩卖

【题目描述】

暑假！有人正在旅行，有人正在拜访祖父母，但有人正在尝试兼职。今年夏天，诺拉决定要赚一笔钱，并在一家商店里担任助理工作。

在诺拉正在工作的商店，在以下n天有计划。每一天的销售经理确切地知道，在在第i天有k个商品将被挂牌出售，而在当天会有 li 个顾客来到店里。另外，经理也确定，每个人来到这个商店，都会购买一个商品（而且只买一个），如果没有任何商品，就不必购买任何商品。此外，由于产品的保质期较短，经理确定了以下规定：如果某些商品在一天结束时搁置在货架上，则该商品不会在第二天保存，并被发送到垃圾站（浪费？，没办法，有钱就是任性）。

为的到最大收益经理要求诺拉选在这n天中任意选择f天去甩卖。在被选中的f天里商品数量分别挂牌出售将增加一倍。因此，如果在第i天商店计划出售k i 件商品（i是属于f中的一天），商店的货架将摆放2· k i的商品。因此，有机会在一天日子卖出两倍的商品。

诺拉的任务是选择f天来使销售商品的总数最大化。她要求你帮忙解决这个困难的问题。

【输入格式】

第一行包含两个整数n和f （1≤n ≤10^5 0≤f ≤n）表示诺拉在店的天数和诺拉有权选择甩卖计划的天数。

下面的n行中包含两个整数k和?li（0≤ki，li≤10^9）表示当天商店的货架产品数量和第i天会来的顾客数量。

【输出格式】

输出一个整数，表示商店可以销售商品的最大数量。

【样例输入】

4 2
2 1
3 5
2 3
1 5

【样例输出】

10

【提示】

    在第一个例子中，我们可以选择第2天和第四天。在这种情况下，改变后的商品数量将分别等于[2,6,2,2]。所以在第一天商店会卖1个商品，在第二天5个，第三天2个，第四天2个。总共1 + 5 + 2 + 2 = 10个商品。

【来源】

http://codeforces.com/contest/810/problem/B