{"problem":{"name":"J. Bottles","description":{"content":"Nick has _n_ bottles of soda left after his birthday. Each bottle is described by two values: remaining amount of soda _a__i_ and bottle volume _b__i_ (_a__i_ ≤ _b__i_). Nick has decided to pour all ","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":524288},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF730J"},"statements":[{"statement_type":"Markdown","content":"Nick has _n_ bottles of soda left after his birthday. Each bottle is described by two values: remaining amount of soda _a__i_ and bottle volume _b__i_ (_a__i_ ≤ _b__i_).\n\nNick has decided to pour all remaining soda into minimal number of bottles, moreover he has to do it as soon as possible. Nick spends _x_ seconds to pour _x_ units of soda from one bottle to another.\n\nNick asks you to help him to determine _k_ — the minimal number of bottles to store all remaining soda and _t_ — the minimal time to pour soda into _k_ bottles. A bottle can't store more soda than its volume. All remaining soda should be saved.\n\n## Input\n\nThe first line contains positive integer _n_ (1 ≤ _n_ ≤ 100) — the number of bottles.\n\nThe second line contains _n_ positive integers _a_1, _a_2, ..., _a__n_ (1 ≤ _a__i_ ≤ 100), where _a__i_ is the amount of soda remaining in the _i_\\-th bottle.\n\nThe third line contains _n_ positive integers _b_1, _b_2, ..., _b__n_ (1 ≤ _b__i_ ≤ 100), where _b__i_ is the volume of the _i_\\-th bottle.\n\nIt is guaranteed that _a__i_ ≤ _b__i_ for any _i_.\n\n## Output\n\nThe only line should contain two integers _k_ and _t_, where _k_ is the minimal number of bottles that can store all the soda and _t_ is the minimal time to pour the soda into _k_ bottles.\n\n[samples]\n\n## Note\n\nIn the first example Nick can pour soda from the first bottle to the second bottle. It will take 3 seconds. After it the second bottle will contain 3 + 3 = 6 units of soda. Then he can pour soda from the fourth bottle to the second bottle and to the third bottle: one unit to the second and two units to the third. It will take 1 + 2 = 3 seconds. So, all the soda will be in two bottles and he will spend 3 + 3 = 6 seconds to do it.","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"Nick 在生日后还剩下 #cf_span[n] 瓶苏打水。每瓶苏打水由两个值描述：剩余的苏打水量 #cf_span[ai] 和瓶子的容积 #cf_span[bi]（#cf_span[ai ≤ bi]）。\n\nNick 决定将所有剩余的苏打水倒入最少数量的瓶子中，并且他希望尽快完成。Nick 花费 #cf_span[x] 秒将 #cf_span[x] 单位的苏打水从一个瓶子倒入另一个瓶子。\n\nNick 请你帮他确定 #cf_span[k] —— 存储所有剩余苏打水所需的最少瓶子数，以及 #cf_span[t] —— 将苏打水倒入 #cf_span[k] 个瓶子所需的最少时间。每个瓶子的容量不能超过其容积。所有剩余的苏打水都必须被保存下来。\n\n第一行包含一个正整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 100]）—— 瓶子的数量。\n\n第二行包含 #cf_span[n] 个正整数 #cf_span[a1, a2, ..., an]（#cf_span[1 ≤ ai ≤ 100]），其中 #cf_span[ai] 表示第 #cf_span[i] 瓶中剩余的苏打水量。\n\n第三行包含 #cf_span[n] 个正整数 #cf_span[b1, b2, ..., bn]（#cf_span[1 ≤ bi ≤ 100]），其中 #cf_span[bi] 表示第 #cf_span[i] 瓶的容积。\n\n保证对于任意 #cf_span[i]，都有 #cf_span[ai ≤ bi]。\n\n仅输出一行，包含两个整数 #cf_span[k] 和 #cf_span[t]，其中 #cf_span[k] 是能存储所有苏打水的最少瓶子数，#cf_span[t] 是将苏打水倒入 #cf_span[k] 个瓶子所需的最少时间。\n\n在第一个例子中，Nick 可以将第一个瓶子中的苏打水倒入第二个瓶子。这需要 3 秒。之后，第二个瓶子将含有 #cf_span[3 + 3 = 6] 单位的苏打水。然后他可以将第四个瓶子中的苏打水倒入第二个和第三个瓶子：1 单位倒入第二个，2 单位倒入第三个。这需要 #cf_span[1 + 2 = 3] 秒。因此，所有苏打水将被存入两个瓶子中，总共花费 #cf_span[3 + 3 = 6] 秒。\n\n## Input\n\n第一行包含一个正整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 100]）—— 瓶子的数量。第二行包含 #cf_span[n] 个正整数 #cf_span[a1, a2, ..., an]（#cf_span[1 ≤ ai ≤ 100]），其中 #cf_span[ai] 表示第 #cf_span[i] 瓶中剩余的苏打水量。第三行包含 #cf_span[n] 个正整数 #cf_span[b1, b2, ..., bn]（#cf_span[1 ≤ bi ≤ 100]），其中 #cf_span[bi] 表示第 #cf_span[i] 瓶的容积。保证对于任意 #cf_span[i]，都有 #cf_span[ai ≤ bi]。\n\n## Output\n\n仅输出一行，包含两个整数 #cf_span[k] 和 #cf_span[t]，其中 #cf_span[k] 是能存储所有苏打水的最少瓶子数，#cf_span[t] 是将苏打水倒入 #cf_span[k] 个瓶子所需的最少时间。\n\n[samples]\n\n## Note\n\n在第一个例子中，Nick 可以将第一个瓶子中的苏打水倒入第二个瓶子。这需要 3 秒。之后，第二个瓶子将含有 #cf_span[3 + 3 = 6] 单位的苏打水。然后他可以将第四个瓶子中的苏打水倒入第二个和第三个瓶子：1 单位倒入第二个，2 单位倒入第三个。这需要 #cf_span[1 + 2 = 3] 秒。因此，所有苏打水将被存入两个瓶子中，总共花费 #cf_span[3 + 3 = 6] 秒。","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the number of bottles.  \nLet $ A = (a_1, a_2, \\dots, a_n) \\in \\mathbb{Z}^n $ be the remaining soda amounts, with $ 1 \\le a_i \\le 100 $.  \nLet $ B = (b_1, b_2, \\dots, b_n) \\in \\mathbb{Z}^n $ be the bottle volumes, with $ 1 \\le b_i \\le 100 $ and $ a_i \\le b_i $ for all $ i $.  \nLet $ S = \\sum_{i=1}^n a_i $ be the total soda volume.\n\n**Constraints**  \n1. $ 1 \\le n \\le 100 $  \n2. $ 1 \\le a_i \\le b_i \\le 100 $ for all $ i \\in \\{1, \\dots, n\\} $\n\n**Objective**  \nFind the minimal number of bottles $ k \\in \\mathbb{Z}^+ $ and minimal pouring time $ t \\in \\mathbb{Z}_{\\ge 0} $ such that:  \n- All $ S $ units of soda are stored in exactly $ k $ bottles,  \n- No bottle $ i $ contains more than $ b_i $ units,  \n- $ k $ is minimized: $ k = \\min \\left\\{ m \\in \\mathbb{Z}^+ \\,\\middle|\\, \\exists \\, I \\subseteq \\{1,\\dots,n\\}, |I| = m, \\sum_{i \\in I} b_i \\ge S \\right\\} $,  \n- $ t $ is minimized: $ t = \\sum_{i \\notin I} a_i $, where $ I $ is a set of $ k $ bottles with total capacity $ \\ge S $, and soda is poured *only* from bottles not in $ I $ into bottles in $ I $, optimally assigned to minimize total poured volume.  \n\n**Note**: The minimal time $ t $ equals the total soda removed from the $ n - k $ bottles that are emptied — which is $ S - \\text{(maximal soda already in the chosen } k \\text{ bottles)} $. To minimize $ t $, maximize the soda retained in the $ k $ selected bottles, subject to their capacities. Thus, select the $ k $ bottles with largest capacities and greedily retain as much of their original soda as possible (up to their volume), then the rest must be poured in.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF730J","tags":["dp"],"sample_group":[["4\n3 3 4 3\n4 7 6 5","2 6"],["2\n1 1\n100 100","1 1"],["5\n10 30 5 6 24\n10 41 7 8 24","3 11"]],"created_at":"2026-03-03 11:00:39"}}