{"problem":{"name":"B. Summer sell-off","description":{"content":"Summer holidays! Someone is going on trips, someone is visiting grandparents, but someone is trying to get a part-time job. This summer Noora decided that she wants to earn some money, and took a job ","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":1000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF810B"},"statements":[{"statement_type":"Markdown","content":"Summer holidays! Someone is going on trips, someone is visiting grandparents, but someone is trying to get a part-time job. This summer Noora decided that she wants to earn some money, and took a job in a shop as an assistant.\n\nShop, where Noora is working, has a plan on the following _n_ days. For each day sales manager knows exactly, that in _i_\\-th day _k__i_ products will be put up for sale and exactly _l__i_ clients will come to the shop that day. Also, the manager is sure, that everyone, who comes to the shop, buys exactly one product or, if there aren't any left, leaves the shop without buying anything. Moreover, due to the short shelf-life of the products, manager established the following rule: if some part of the products left on the shelves at the end of the day, that products aren't kept on the next day and are sent to the dump.\n\nFor advertising purposes manager offered to start a sell-out in the shop. He asked Noora to choose any _f_ days from _n_ next for sell-outs. On each of _f_ chosen days the number of products were put up for sale would be doubled. Thus, if on _i_\\-th day shop planned to put up for sale _k__i_ products and Noora has chosen this day for sell-out, shelves of the shop would keep 2·_k__i_ products. Consequently, there is an opportunity to sell two times more products on days of sell-out.\n\nNoora's task is to choose _f_ days to maximize total number of sold products. She asks you to help her with such a difficult problem.\n\n## Input\n\nThe first line contains two integers _n_ and _f_ (1 ≤ _n_ ≤ 105, 0 ≤ _f_ ≤ _n_) denoting the number of days in shop's plan and the number of days that Noora has to choose for sell-out.\n\nEach line of the following _n_ subsequent lines contains two integers _k__i_, _l__i_ (0 ≤ _k__i_, _l__i_ ≤ 109) denoting the number of products on the shelves of the shop on the _i_\\-th day and the number of clients that will come to the shop on _i_\\-th day.\n\n## Output\n\nPrint a single integer denoting the maximal number of products that shop can sell.\n\n[samples]\n\n## Note\n\nIn the first example we can choose days with numbers 2 and 4 for sell-out. In this case new numbers of products for sale would be equal to \\[2, 6, 2, 2\\] respectively. So on the first day shop will sell 1 product, on the second — 5, on the third — 2, on the fourth — 2. In total 1 + 5 + 2 + 2 = 10 product units.\n\nIn the second example it is possible to sell 5 products, if you choose third day for sell-out.","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"暑假到了！有人去旅行，有人探望祖父母，但有人在寻找兼职工作。今年夏天，Noora 决定赚点钱，于是在一家商店当上了助手。\n\nNoora 工作的商店计划在接下来的 #cf_span[n] 天内运营。对于每一天，销售经理都清楚地知道：在第 #cf_span[i] 天，将有 #cf_span[ki] 件商品上架，同时会有 #cf_span[li] 位顾客光顾商店。此外，经理确信，每一位到店的顾客都会恰好购买一件商品，或者如果商品已售罄，则空手离开。此外，由于商品保质期短，经理制定了以下规则：如果某天结束时货架上仍有剩余商品，这些商品不会留到第二天，而是被丢弃。\n\n为了宣传推广，经理决定开展一次清仓促销活动。他请 Noora 从接下来的 #cf_span[n] 天中选出 #cf_span[f] 天作为清仓日。在每个被选中的清仓日，上架商品数量将翻倍。也就是说，如果第 #cf_span[i] 天原计划上架 #cf_span[ki] 件商品，而 Noora 选择了这一天作为清仓日，则货架上将有 #cf_span[2·ki] 件商品。因此，在清仓日可以卖出两倍的商品。\n\nNoora 的任务是选择 #cf_span[f] 天，以最大化总销售量。她请你帮助解决这个难题。\n\n第一行包含两个整数 #cf_span[n] 和 #cf_span[f] #cf_span[(1 ≤ n ≤ 10^5, 0 ≤ f ≤ n)]，分别表示商店计划的天数和 Noora 必须选择作为清仓日的天数。\n\n接下来的 #cf_span[n] 行，每行包含两个整数 #cf_span[ki, li] #cf_span[(0 ≤ ki, li ≤ 10^9)]，表示第 #cf_span[i] 天货架上的商品数量和当天到店的顾客数量。\n\n请输出一个整数，表示商店能卖出的最大商品数量。\n\n在第一个例子中，我们可以选择第 #cf_span[2] 天和第 #cf_span[4] 天作为清仓日。此时，新的商品上架数量分别为 #cf_span[[2, 6, 2, 2]]。因此，第一天商店卖出 #cf_span[1] 件商品，第二天卖出 #cf_span[5] 件，第三天卖出 #cf_span[2] 件，第四天卖出 #cf_span[2] 件，总计 #cf_span[1 + 5 + 2 + 2 = 10] 件商品。\n\n在第二个例子中，如果选择第三天作为清仓日，则最多可以卖出 #cf_span[5] 件商品。\n\n## Input\n\n第一行包含两个整数 #cf_span[n] 和 #cf_span[f] #cf_span[(1 ≤ n ≤ 10^5, 0 ≤ f ≤ n)]，分别表示商店计划的天数和 Noora 必须选择作为清仓日的天数。接下来的 #cf_span[n] 行，每行包含两个整数 #cf_span[ki, li] #cf_span[(0 ≤ ki, li ≤ 10^9)]，表示第 #cf_span[i] 天货架上的商品数量和当天到店的顾客数量。\n\n## Output\n\n请输出一个整数，表示商店能卖出的最大商品数量。\n\n[samples]\n\n## Note\n\n在第一个例子中，我们可以选择第 #cf_span[2] 天和第 #cf_span[4] 天作为清仓日。此时，新的商品上架数量分别为 #cf_span[[2, 6, 2, 2]]。因此，第一天商店卖出 #cf_span[1] 件商品，第二天卖出 #cf_span[5] 件，第三天卖出 #cf_span[2] 件，第四天卖出 #cf_span[2] 件，总计 #cf_span[1 + 5 + 2 + 2 = 10] 件商品。\n\n在第二个例子中，如果选择第三天作为清仓日，则最多可以卖出 #cf_span[5] 件商品。","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ n, f \\in \\mathbb{Z} $ with $ 1 \\leq n \\leq 10^5 $, $ 0 \\leq f \\leq n $.  \nFor each day $ i \\in \\{1, \\dots, n\\} $, let $ k_i \\in \\mathbb{Z}_{\\geq 0} $ be the number of products available, and $ l_i \\in \\mathbb{Z}_{\\geq 0} $ be the number of clients.  \n\nLet $ S \\subseteq \\{1, \\dots, n\\} $ with $ |S| = f $ be the set of days chosen for sell-out.  \n\n**Constraints**  \nFor each day $ i $:  \n- Without sell-out: products sold = $ \\min(k_i, l_i) $  \n- With sell-out: products available = $ 2k_i $, so products sold = $ \\min(2k_i, l_i) $  \n\n**Objective**  \nMaximize total sales:  \n$$\n\\max_{\\substack{S \\subseteq \\{1,\\dots,n\\} \\\\ |S| = f}} \\left( \\sum_{i=1}^{n} \\begin{cases} \n\\min(2k_i, l_i) & \\text{if } i \\in S \\\\\n\\min(k_i, l_i) & \\text{if } i \\notin S \n\\end{cases} \\right)\n$$","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF810B","tags":["greedy","sortings"],"sample_group":[["4 2\n2 1\n3 5\n2 3\n1 5","10"],["4 1\n0 2\n0 3\n3 5\n0 6","5"]],"created_at":"2026-03-03 11:00:39"}}