{"problem":{"name":"C. Party Lemonade","description":{"content":"A New Year party is not a New Year party without lemonade! As usual, you are expecting a lot of guests, and buying lemonade has already become a pleasant necessity. Your favorite store sells lemonade","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":1000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF913C"},"statements":[{"statement_type":"Markdown","content":"A New Year party is not a New Year party without lemonade! As usual, you are expecting a lot of guests, and buying lemonade has already become a pleasant necessity.\n\nYour favorite store sells lemonade in bottles of _n_ different volumes at different costs. A single bottle of type _i_ has volume 2_i_ - 1 liters and costs _c__i_ roubles. The number of bottles of each type in the store can be considered infinite.\n\nYou want to buy at least _L_ liters of lemonade. How many roubles do you have to spend?\n\n## Input\n\nThe first line contains two integers _n_ and _L_ (1 ≤ _n_ ≤ 30; 1 ≤ _L_ ≤ 109) — the number of types of bottles in the store and the required amount of lemonade in liters, respectively.\n\nThe second line contains _n_ integers _c_1, _c_2, ..., _c__n_ (1 ≤ _c__i_ ≤ 109) — the costs of bottles of different types.\n\n## Output\n\nOutput a single integer — the smallest number of roubles you have to pay in order to buy at least _L_ liters of lemonade.\n\n[samples]\n\n## Note\n\nIn the first example you should buy one 8-liter bottle for 90 roubles and two 2-liter bottles for 30 roubles each. In total you'll get 12 liters of lemonade for just 150 roubles.\n\nIn the second example, even though you need only 3 liters, it's cheaper to buy a single 8-liter bottle for 10 roubles.\n\nIn the third example it's best to buy three 1-liter bottles for 10 roubles each, getting three liters for 30 roubles.","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"没有柠檬水的跨年派对还算什么跨年派对！和往常一样，你预计会有很多客人，购买柠檬水已经成为一种愉快的必需品。\n\n你最喜欢的商店出售不同容量和价格的柠檬水瓶，共有 #cf_span[n] 种类型。每种类型 #cf_span[i] 的瓶子容量为 #cf_span[2i - 1] 升，价格为 #cf_span[ci] 卢布。每种类型的瓶子库存都可以视为无限。\n\n你希望购买至少 #cf_span[L] 升柠檬水。你需要花费多少卢布？\n\n第一行包含两个整数 #cf_span[n] 和 #cf_span[L]（#cf_span[1 ≤ n ≤ 30]；#cf_span[1 ≤ L ≤ 10^9]）— 分别表示商店中瓶子的类型数和所需的柠檬水总量（升）。\n\n第二行包含 #cf_span[n] 个整数 #cf_span[c1, c2, ..., cn]（#cf_span[1 ≤ ci ≤ 10^9]）— 表示每种类型瓶子的价格。\n\n请输出一个整数 —— 为了购买至少 #cf_span[L] 升柠檬水所需的最少卢布数。\n\n在第一个例子中，你应该购买一个 8 升的瓶子（90 卢布）和两个 2 升的瓶子（每个 30 卢布），总共获得 12 升柠檬水，花费 150 卢布。\n\n在第二个例子中，尽管你只需要 3 升，但购买一个 8 升的瓶子（10 卢布）更便宜。\n\n在第三个例子中，最好购买三个 1 升的瓶子（每个 10 卢布），总共获得 3 升，花费 30 卢布。\n\n## Input\n\n第一行包含两个整数 #cf_span[n] 和 #cf_span[L]（#cf_span[1 ≤ n ≤ 30]；#cf_span[1 ≤ L ≤ 10^9]）— 分别表示商店中瓶子的类型数和所需的柠檬水总量（升）。第二行包含 #cf_span[n] 个整数 #cf_span[c1, c2, ..., cn]（#cf_span[1 ≤ ci ≤ 10^9]）— 表示每种类型瓶子的价格。\n\n## Output\n\n请输出一个整数 —— 为了购买至少 #cf_span[L] 升柠檬水所需的最少卢布数。\n\n[samples]\n\n## Note\n\n在第一个例子中，你应该购买一个 8 升的瓶子（90 卢布）和两个 2 升的瓶子（每个 30 卢布），总共获得 12 升柠檬水，花费 150 卢布。在第二个例子中，尽管你只需要 3 升，但购买一个 8 升的瓶子（10 卢布）更便宜。在第三个例子中，最好购买三个 1 升的瓶子（每个 10 卢布），总共获得 3 升，花费 30 卢布。","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**Definitions:**\n- Let $ n \\in \\mathbb{N} $, $ L \\in \\mathbb{N} $.\n- For $ i \\in \\{1, 2, \\dots, n\\} $, define bottle type $ i $ with volume $ v_i = 2^{i-1} $ liters and cost $ c_i \\in \\mathbb{N} $.\n\n**Given:**\n- $ 1 \\leq n \\leq 30 $\n- $ 1 \\leq L \\leq 10^9 $\n- $ 1 \\leq c_i \\leq 10^9 $\n\n**Objective:**\nMinimize total cost $ \\sum_{i=1}^n x_i c_i $, subject to:\n- $ x_i \\in \\mathbb{Z}_{\\geq 0} $ for all $ i \\in \\{1, 2, \\dots, n\\} $\n- $ \\sum_{i=1}^n x_i \\cdot 2^{i-1} \\geq L $\n\n**Optimization Problem:**\n$$\n\\min_{x_1, x_2, \\dots, x_n \\in \\mathbb{Z}_{\\geq 0}} \\sum_{i=1}^n x_i c_i \\quad \\text{subject to} \\quad \\sum_{i=1}^n x_i \\cdot 2^{i-1} \\geq L\n$$","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF913C","tags":["bitmasks","dp","greedy"],"sample_group":[["4 12\n20 30 70 90","150"],["4 3\n10000 1000 100 10","10"],["4 3\n10 100 1000 10000","30"],["5 787787787\n123456789 234567890 345678901 456789012 987654321","44981600785557577"]],"created_at":"2026-03-03 11:00:39"}}