← 返回题目列表

Codeforces · 810/B

B. 夏季抛售

中文机器翻译题面 查看原题

暑假!有人去旅行,有人去看望祖父母,有人想找一份兼职工作。今年夏天,努拉决定要赚点钱,于是在一家商店找到了一份助理的工作。

Noora 工作的商店有接下来 n 天的计划。对于每一天,销售经理都确切地知道,在第 i 天,ki 产品将被出售,并且当天将有 li 个客户来到商店。此外,经理还确信,每个来到商店的人都会只购买一种产品,或者如果没有剩余的,则不买任何东西就离开商店。此外,由于产品的保质期很短,经理制定了以下规则:如果当天结束时有部分产品留在货架上,则该产品不会保留到第二天,而是被送往垃圾场。

出于广告目的,经理提出在商店内开始售空。他要求 Noora 从接下来的 n 天内选择任意 f 天进行售空。在选定的每一天,出售的产品数量都会增加一倍。因此,如果商店计划在第 i 天出售 ki 产品,并且 Noora 选择这一天进行售空,则商店的货架上将保留 2·ki 产品。因此,在售完的日子里,有机会销售两倍的产品。

Noora 的任务是选择 f 天来最大化已售产品总数。她请求你帮助她解决如此困难的问题。

输入

第一行包含两个整数 n 和 f (1 ≤ n ≤ 105, 0 ≤ f ≤ n),表示商店计划中的天数和 Noora 必须选择售空的天数。

接下来n行中的每一行包含两个整数ki,li(0≤ki,li≤109),分别表示第i天商店货架上的产品数量和第i天来到商店的顾客数量。

输出

打印一个整数,表示商店可以销售的最大产品数量。

示例

输入 #1

4 2
2 1
3 5
2 3
1 5

输出 #1

10

输入 #2

4 1
0 2
0 3
3 5
0 6

输出 #2

5

注意

在第一个示例中,我们可以选择数字 2 和 4 的日期进行售罄。在这种情况下,待售产品的新数量将分别等于 [2, 6, 2, 2]。因此,第一天商店将销售 1 个产品,第二天 - 5 个,第三天 - 2 个,第四天 - 2 个。总共 1 + 5 + 2 + 2 = 10 个产品单位。

在第二个示例中,如果您选择第三天售空,则可以销售 5 种产品。