{"trustable":false,"prependHtml":"\u003cstyle type\u003d\u0027text/css\u0027\u003e\n .input, .output {\n border: 1px solid #888888;\n }\n .output {\n margin-bottom: 1em;\n position: relative;\n top: -1px;\n }\n .output pre, .input pre {\n background-color: #EFEFEF;\n line-height: 1.25em;\n margin: 0;\n padding: 0.25em;\n }\n \u003c/style\u003e\n \u003clink rel\u003d\"stylesheet\" href\u003d\"//codeforces.org/s/96598/css/problem-statement.css\" type\u003d\"text/css\" /\u003e\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript type\u003d\"text/javascript\" async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS_HTML-full\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"MD","content":"Летом у школьников каникулы. Кто-то уезжает на отдых, кто-то — к бабушке или дедушке, а кто-то устраивается на подработку. Этим летом Нура решила, что хочет немного заработать, и устроилась в магазин продавцом-консультантом.\n\nУ магазина, где работает Нура, есть план на ближайшие n дней. Для каждого дня менеджер по продажам точно знает, что в i-й день будет выставлено на продажу ki единиц товара, и что ровно li покупателей придет за покупками в магазин в этот день. Кроме того, менеджер уверен, что каждый из пришедших покупателей покупает ровно одну единицу товара либо, если товаров в магазине не осталось, уходит из магазина без покупок. Более того, в связи с тем, что товары в магазине быстро портятся, менеджер установил следующее правило: если в какой-то из дней в магазине часть товаров осталась не купленной, то эти товары отправляются на свалку, а не остаются на следующий день.\n\nВ целях рекламы магазина менеджер предложил провести распродажу. Он дал Нуре задание выбрать из ближайших n дней любые f дней, в каждый из которых будет проведена распродажа. В каждый из этих f выбранных дней количество единиц товара, которое будет выставлено на продажу, будет удвоено. Таким образом, если в i-й день по плану магазин должен был выставить на продажу ki единиц товара, то, если сделать распродажу в этот день, на витрины магазина будет поставлено 2·ki единиц товара. Следовательно, в дни распродажи существует возможность продать большее количество товара.\n\nЗадача Нуры — выбрать ровно f дней так, чтобы максимизировать суммарное количество проданных единиц товара. Она просит вас помочь ей с этой нелегкой задачей!"}},{"title":"Input","value":{"format":"MD","content":"В первой строке следуют два целых числа n и f (1 ≤ n ≤ 100000, 0 ≤ f ≤ n) — количество дней, на которые составлен план, а также количество дней, в которые будет проведена распродажа.\n\nВ следующих n строках следуют пары целых чисел ki, li (0 ≤ ki, li ≤ 1 000 000 000) — количество единиц товара, которое было запланировано выставить на продажу в i-й день, и количество покупателей, которые придут в магазин в i-й день."}},{"title":"Output","value":{"format":"MD","content":"Выведите единственное число — максимальное количество единиц товара, которое сможет продать магазин."}},{"title":"Examples","value":{"format":"MD","content":"\u003cdiv class\u003d\"sample-test\"\u003e\n \u003cdiv class\u003d\"input\"\u003e\n \u003cdiv class\u003d\"title\"\u003e\n Input\n \u003c/div\u003e\n \u003cpre\u003e4 2\u003cbr\u003e2 1\u003cbr\u003e3 5\u003cbr\u003e2 3\u003cbr\u003e1 5\u003cbr\u003e\u003c/pre\u003e\n \u003c/div\u003e\n \u003cdiv class\u003d\"output\"\u003e\n \u003cdiv class\u003d\"title\"\u003e\n Output\n \u003c/div\u003e\n \u003cpre\u003e10\u003c/pre\u003e\n \u003c/div\u003e\n \u003cdiv class\u003d\"input\"\u003e\n \u003cdiv class\u003d\"title\"\u003e\n Input\n \u003c/div\u003e\n \u003cpre\u003e4 1\u003cbr\u003e0 2\u003cbr\u003e0 3\u003cbr\u003e3 5\u003cbr\u003e0 6\u003cbr\u003e\u003c/pre\u003e\n \u003c/div\u003e\n \u003cdiv class\u003d\"output\"\u003e\n \u003cdiv class\u003d\"title\"\u003e\n Output\n \u003c/div\u003e\n \u003cpre\u003e5\u003c/pre\u003e\n \u003c/div\u003e\n\u003c/div\u003e"}},{"title":"Note","value":{"format":"MD","content":"В первом примере можно выбрать для распродажи дни с номерами 2 и 4. В таком случае новые количества единиц товара будут равны [2, 6, 2, 2] соответственно. Тогда в первый день будет продана 1 единица товара, во второй — 5, в третий — 2, в четвертый — 2. Итого 1 + 5 + 2 + 2 \u003d 10 единиц товара.\n\nВо втором примере можно продать 5 единиц товара, если устроить распродажу в третий день."}}]}