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