{"problem":{"name":"C. Dishonest Sellers","description":{"content":"Igor found out discounts in a shop and decided to buy _n_ items. Discounts at the store will last for a week and Igor knows about each item that its price now is _a__i_, and after a week of discounts ","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF779C"},"statements":[{"statement_type":"Markdown","content":"Igor found out discounts in a shop and decided to buy _n_ items. Discounts at the store will last for a week and Igor knows about each item that its price now is _a__i_, and after a week of discounts its price will be _b__i_.\n\nNot all of sellers are honest, so now some products could be more expensive than after a week of discounts.\n\nIgor decided that buy **at least** _k_ of items now, but wait with the rest of the week in order to save money as much as possible. Your task is to determine the minimum money that Igor can spend to buy all _n_ items.\n\n## Input\n\nIn the first line there are two positive integer numbers _n_ and _k_ (1 ≤ _n_ ≤ 2·105, 0 ≤ _k_ ≤ _n_) — total number of items to buy and minimal number of items Igor wants to by right now.\n\nThe second line contains sequence of integers _a_1, _a_2, ..., _a__n_ (1 ≤ _a__i_ ≤ 104) — prices of items during discounts (i.e. right now).\n\nThe third line contains sequence of integers _b_1, _b_2, ..., _b__n_ (1 ≤ _b__i_ ≤ 104) — prices of items after discounts (i.e. after a week).\n\n## Output\n\nPrint the minimal amount of money Igor will spend to buy all _n_ items. Remember, he should buy at least _k_ items right now.\n\n[samples]\n\n## Note\n\nIn the first example Igor should buy item 3 paying 6. But items 1 and 2 he should buy after a week. He will pay 3 and 1 for them. So in total he will pay 6 + 3 + 1 = 10.\n\nIn the second example Igor should buy right now items 1, 2, 4 and 5, paying for them 3, 4, 10 and 3, respectively. Item 3 he should buy after a week of discounts, he will pay 5 for it. In total he will spend 3 + 4 + 10 + 3 + 5 = 25.","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"Igor 在商店发现了折扣活动，决定购买 #cf_span[n] 件商品。商店的折扣将持续一周，Igor 知道每件商品当前的价格为 #cf_span[ai]，一周后价格将变为 #cf_span[bi]。\n\n并非所有商家都诚实，因此现在有些商品的价格可能高于一周后的价格。\n\nIgor 决定至少购买 *#cf_span[k]* 件商品现在，其余商品则等待一周以尽可能节省开支。你的任务是确定 Igor 购买所有 #cf_span[n] 件商品所需的最少花费。\n\n第一行包含两个正整数 #cf_span[n] 和 #cf_span[k]（#cf_span[1 ≤ n ≤ 2·105]，#cf_span[0 ≤ k ≤ n]）——需购买的商品总数和 Igor 希望现在购买的最少商品数。\n\n第二行包含整数序列 #cf_span[a1, a2, ..., an]（#cf_span[1 ≤ ai ≤ 104]）——商品在折扣期间的价格（即现在）。\n\n第三行包含整数序列 #cf_span[b1, b2, ..., bn]（#cf_span[1 ≤ bi ≤ 104]）——商品在折扣后的价格（即一周后）。\n\n请输出 Igor 购买所有 #cf_span[n] 件商品所需的最少金额。记住，他必须至少现在购买 #cf_span[k] 件商品。\n\n在第一个例子中，Igor 应购买第 3 件商品，支付 6。但第 1 和第 2 件商品他应等待一周后购买，分别支付 3 和 1。因此总共支付 #cf_span[6 + 3 + 1 = 10]。\n\n在第二个例子中，Igor 应现在购买第 1、2、4 和 5 件商品，分别支付 3、4、10 和 3。第 3 件商品他应等待一周后购买，支付 5。总共花费 #cf_span[3 + 4 + 10 + 3 + 5 = 25]。\n\n## Input\n\n在第一行包含两个正整数 #cf_span[n] 和 #cf_span[k]（#cf_span[1 ≤ n ≤ 2·105]，#cf_span[0 ≤ k ≤ n]）——需购买的商品总数和 Igor 希望现在购买的最少商品数。第二行包含整数序列 #cf_span[a1, a2, ..., an]（#cf_span[1 ≤ ai ≤ 104]）——商品在折扣期间的价格（即现在）。第三行包含整数序列 #cf_span[b1, b2, ..., bn]（#cf_span[1 ≤ bi ≤ 104]）——商品在折扣后的价格（即一周后）。\n\n## Output\n\n请输出 Igor 购买所有 #cf_span[n] 件商品所需的最少金额。记住，他必须至少现在购买 #cf_span[k] 件商品。\n\n[samples]\n\n## Note\n\n在第一个例子中，Igor 应购买第 3 件商品，支付 6。但第 1 和第 2 件商品他应等待一周后购买，分别支付 3 和 1。因此总共支付 #cf_span[6 + 3 + 1 = 10]。\n\n在第二个例子中，Igor 应现在购买第 1、2、4 和 5 件商品，分别支付 3、4、10 和 3。第 3 件商品他应等待一周后购买，支付 5。总共花费 #cf_span[3 + 4 + 10 + 3 + 5 = 25]。","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ n, k \\in \\mathbb{Z} $ with $ 1 \\leq n \\leq 2 \\cdot 10^5 $ and $ 0 \\leq k \\leq n $.  \nLet $ A = (a_1, a_2, \\dots, a_n) $ and $ B = (b_1, b_2, \\dots, b_n) $ be sequences of positive integers representing current and future prices of $ n $ items, respectively.\n\n**Constraints**  \n1. $ 1 \\leq a_i, b_i \\leq 10^4 $ for all $ i \\in \\{1, \\dots, n\\} $  \n2. Igor must buy **at least** $ k $ items at current price $ a_i $, and the remaining $ n - k $ items may be bought at future price $ b_i $.\n\n**Objective**  \nMinimize the total cost:  \n$$\n\\min \\sum_{i=1}^{n} \n\\begin{cases}\na_i & \\text{if item } i \\text{ is bought now} \\\\\nb_i & \\text{if item } i \\text{ is bought later}\n\\end{cases}\n$$  \nsubject to: exactly $ x $ items are bought now, where $ k \\leq x \\leq n $, and $ x $ is chosen optimally.\n\nEquivalently, define for each item $ i $ the savings from buying now: $ d_i = a_i - b_i $.  \nTo minimize cost, Igor should buy now the $ k $ items with the **largest** $ d_i $ (i.e., greatest savings or least loss), and for the remaining $ n - k $ items, buy later if beneficial. But since he must buy **at least** $ k $ now, the optimal strategy is:\n\n- Buy now the $ k $ items with the **smallest** $ b_i - a_i $ (i.e., largest $ a_i - b_i $) — i.e., those where buying now is *least worse* or *most beneficial*.\n- For the remaining $ n - k $ items, buy at the cheaper of $ a_i $ or $ b_i $, but since we are forced to buy at least $ k $ now, we must buy exactly $ k $ now, and the rest later — **but** we can choose which $ k $ to buy now to minimize total cost.\n\nActually, optimal strategy:\n\nLet $ S $ be the set of items bought now ($ |S| \\geq k $).  \nTotal cost = $ \\sum_{i \\in S} a_i + \\sum_{i \\notin S} b_i $\n\nThis equals:  \n$$\n\\sum_{i=1}^n b_i + \\sum_{i \\in S} (a_i - b_i)\n$$\n\nSo to minimize total cost, we must **minimize** $ \\sum_{i \\in S} (a_i - b_i) $, subject to $ |S| \\geq k $.\n\nWait — no: since we are **adding** $ \\sum_{i \\in S} (a_i - b_i) $ to the base $ \\sum b_i $, to **minimize** total cost, we want to **minimize** the sum of $ (a_i - b_i) $ over the chosen $ S $, i.e., pick the $ k $ items with the **smallest** $ a_i - b_i $ (i.e., most negative or smallest difference).\n\nBut actually: if $ a_i - b_i $ is negative, buying now is *more expensive* — so we want to avoid that. So to minimize the *extra* cost over buying all later, we should choose the $ k $ items for which $ a_i - b_i $ is **as small as possible** (i.e., most negative or least positive).\n\nThus:\n\nLet $ d_i = a_i - b_i $.  \nWe must choose a set $ S \\subseteq \\{1, \\dots, n\\} $ with $ |S| = k $ (we can assume exactly $ k $, since buying more than $ k $ now can only increase cost if $ a_i > b_i $) to minimize $ \\sum_{i \\in S} d_i $.\n\nThen total cost = $ \\sum_{i=1}^n b_i + \\sum_{i \\in S} d_i $\n\nSo:\n\n**Objective**  \nCompute:\n$$\n\\min_{\\substack{S \\subseteq \\{1,\\dots,n\\} \\\\ |S| = k}} \\left( \\sum_{i=1}^n b_i + \\sum_{i \\in S} (a_i - b_i) \\right) = \\sum_{i=1}^n b_i + \\min_{\\substack{S \\subseteq \\{1,\\dots,n\\} \\\\ |S| = k}} \\sum_{i \\in S} (a_i - b_i)\n$$\n\nWhich is equivalent to:  \nSort $ d_i = a_i - b_i $ in ascending order, take the first $ k $, sum them, and add to $ \\sum b_i $.\n\nBut note: what if $ k = 0 $? Then we buy nothing now — cost = $ \\sum b_i $.\n\nSo final formalization:\n\n**Definitions**  \nLet $ n, k \\in \\mathbb{Z} $, $ 1 \\leq n \\leq 2 \\cdot 10^5 $, $ 0 \\leq k \\leq n $.  \nLet $ A = (a_1, \\dots, a_n) $, $ B = (b_1, \\dots, b_n) $ be sequences of positive integers.\n\n**Constraints**  \n- Igor must buy **at least** $ k $ items at current price $ a_i $.  \n- He may buy more than $ k $, but it is never beneficial to do so if $ a_i > b_i $.\n\n**Objective**  \nCompute the minimal total cost:\n$$\n\\min_{\\substack{S \\subseteq \\{1,\\dots,n\\} \\\\ |S| \\geq k}} \\left( \\sum_{i \\in S} a_i + \\sum_{i \\notin S} b_i \\right)\n$$\n\nThis is minimized when $ |S| = k $, and $ S $ consists of the $ k $ indices $ i $ for which $ a_i - b_i $ is **smallest**.\n\nLet $ d_i = a_i - b_i $.  \nSort $ d_1, d_2, \\dots, d_n $ in non-decreasing order: $ d_{(1)} \\leq d_{(2)} \\leq \\dots \\leq d_{(n)} $.  \nThen:\n$$\n\\text{Minimal cost} = \\sum_{i=1}^n b_i + \\sum_{j=1}^k d_{(j)}\n$$","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF779C","tags":["constructive algorithms","greedy","sortings"],"sample_group":[["3 1\n5 4 6\n3 1 5","10"],["5 3\n3 4 7 10 3\n4 5 5 12 5","25"]],"created_at":"2026-03-03 11:00:39"}}