{"problem":{"name":"C. Downloading B++","description":{"content":"Only _T_ milliseconds left before the start of well-known online programming contest Codehorses Round 2017. Polycarp needs to download B++ compiler to take part in the contest. The size of the file i","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":3000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF883C"},"statements":[{"statement_type":"Markdown","content":"Only _T_ milliseconds left before the start of well-known online programming contest Codehorses Round 2017.\n\nPolycarp needs to download B++ compiler to take part in the contest. The size of the file is _f_ bytes.\n\nPolycarp's internet tariff allows to download data at the rate of one byte per _t_0 milliseconds. This tariff is already prepaid, and its use does not incur any expense for Polycarp. In addition, the Internet service provider offers two additional packages:\n\n*   download _a_1 bytes at the rate of one byte per _t_1 milliseconds, paying _p_1 burles for the package;\n*   download _a_2 bytes at the rate of one byte per _t_2 milliseconds, paying _p_2 burles for the package.\n\nPolycarp can buy any package many times. When buying a package, its price (_p_1 or _p_2) is prepaid before usage. Once a package is bought it replaces the regular tariff until package data limit is completely used. After a package is consumed Polycarp can immediately buy a new package or switch to the regular tariff without loosing any time. While a package is in use Polycarp can't buy another package or switch back to the regular internet tariff.\n\nFind the minimum amount of money Polycarp has to spend to download an _f_ bytes file no more than in _T_ milliseconds.\n\nNote that because of technical reasons Polycarp can download only integer number of bytes using regular tariff and both packages. I.e. in each of three downloading modes the number of downloaded bytes will be integer. It means that Polycarp can't download a byte partially using the regular tariff or/and both packages.\n\n## Input\n\nThe first line contains three integer numbers _f_, _T_ and _t_0 (1 ≤ _f_, _T_, _t_0 ≤ 107) — size of the file to download (in bytes), maximal time to download the file (in milliseconds) and number of milliseconds to download one byte using the regular internet tariff.\n\nThe second line contains a description of the first additional package. The line contains three integer numbers _a_1, _t_1 and _p_1 (1 ≤ _a_1, _t_1, _p_1 ≤ 107), where _a_1 is maximal sizes of downloaded data (in bytes), _t_1 is time to download one byte (in milliseconds), _p_1 is price of the package (in burles).\n\nThe third line contains a description of the second additional package. The line contains three integer numbers _a_2, _t_2 and _p_2 (1 ≤ _a_2, _t_2, _p_2 ≤ 107), where _a_2 is maximal sizes of downloaded data (in bytes), _t_2 is time to download one byte (in milliseconds), _p_2 is price of the package (in burles).\n\nPolycarp can buy any package many times. Once package is bought it replaces the regular tariff until package data limit is completely used. While a package is in use Polycarp can't buy another package or switch back to the regular internet tariff.\n\n## Output\n\nPrint the minimum amount of money that Polycarp needs to pay to download B++ compiler no more than in _T_ milliseconds. If there is no solution, print the only integer _\\-1_.\n\n[samples]\n\n## Note\n\nIn the first example Polycarp has to buy the first additional package 5 times and do not buy the second additional package. He downloads 120 bytes (of total 26·5 = 130 bytes) in 120·8 = 960 milliseconds (960 ≤ 964). He spends 8·5 = 40 burles on it.\n\nIn the second example Polycarp has enough time to download 10 bytes. It takes 10·20 = 200 milliseconds which equals to upper constraint on download time.\n\nIn the third example Polycarp has to buy one first additional package and one second additional package.\n\nIn the fourth example Polycarp has no way to download the file on time.","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"距离知名在线编程竞赛 Codehorses Round 2017 开始仅剩 #cf_span[T] 毫秒。\n\nPolycarp 需要下载 B++ 编译器以参加比赛，该文件大小为 #cf_span[f] 字节。\n\nPolycarp 的互联网套餐允许以每 #cf_span[t0] 毫秒下载一字节的速度下载数据。该套餐已预付费，使用时不产生任何费用。此外，互联网服务提供商还提供两个附加套餐：\n\nPolycarp 可以多次购买任意套餐。购买套餐时，其价格（#cf_span[p1] 或 #cf_span[p2]）需在使用前预付。一旦购买，该套餐将取代常规套餐，直至其数据限额被完全用尽。套餐用尽后，Polycarp 可立即购买新套餐或切换回常规套餐，且不会损失任何时间。在套餐使用期间，Polycarp 无法购买其他套餐或切换回常规互联网套餐。\n\n求 Polycarp 为在不超过 #cf_span[T] 毫秒内下载完 #cf_span[f] 字节文件所需的最少花费。\n\n注意：由于技术原因，Polycarp 只能使用常规套餐和两个附加套餐下载整数字节数。即，在三种下载模式中，下载的字节数必须为整数。这意味着 Polycarp 无法部分使用常规套餐或/和两个附加套餐下载一个字节。\n\n第一行包含三个整数 #cf_span[f], #cf_span[T] 和 #cf_span[t0]（#cf_span[1 ≤ f, T, t0 ≤ 10^7]）——待下载文件的大小（字节）、下载文件的最大时间（毫秒）、使用常规互联网套餐下载一字节所需的时间（毫秒）。\n\n第二行描述第一个附加套餐，包含三个整数 #cf_span[a1], #cf_span[t1] 和 #cf_span[p1]（#cf_span[1 ≤ a1, t1, p1 ≤ 10^7]），其中 #cf_span[a1] 为可下载的最大数据量（字节），#cf_span[t1] 为下载一字节所需时间（毫秒），#cf_span[p1] 为套餐价格（布尔）。\n\n第三行描述第二个附加套餐，包含三个整数 #cf_span[a2], #cf_span[t2] 和 #cf_span[p2]（#cf_span[1 ≤ a2, t2, p2 ≤ 10^7]），其中 #cf_span[a2] 为可下载的最大数据量（字节），#cf_span[t2] 为下载一字节所需时间（毫秒），#cf_span[p2] 为套餐价格（布尔）。\n\nPolycarp 可以多次购买任意套餐。一旦购买，该套餐将取代常规套餐，直至其数据限额被完全用尽。在套餐使用期间，Polycarp 无法购买其他套餐或切换回常规互联网套餐。\n\n请输出 Polycarp 为在不超过 #cf_span[T] 毫秒内下载 B++ 编译器所需支付的最少金额。若无解，请输出整数 _-1_。\n\n在第一个示例中，Polycarp 必须购买第一个附加套餐 5 次，不购买第二个附加套餐。他下载了 120 字节（共 #cf_span[26·5 = 130] 字节），耗时 #cf_span[120·8 = 960] 毫秒（#cf_span[960 ≤ 964]），花费 #cf_span[8·5 = 40] 布尔。\n\n在第二个示例中，Polycarp 有足够时间下载 #cf_span[10] 字节，耗时 #cf_span[10·20 = 200] 毫秒，恰好等于下载时间上限。\n\n在第三个示例中，Polycarp 需要购买一个第一个附加套餐和一个第二个附加套餐。\n\n在第四个示例中，Polycarp 无法在规定时间内下载完文件。\n\n## Input\n\n第一行包含三个整数 #cf_span[f], #cf_span[T] 和 #cf_span[t0]（#cf_span[1 ≤ f, T, t0 ≤ 10^7]）——待下载文件的大小（字节）、下载文件的最大时间（毫秒）、使用常规互联网套餐下载一字节所需的时间（毫秒）。第二行描述第一个附加套餐，包含三个整数 #cf_span[a1], #cf_span[t1] 和 #cf_span[p1]（#cf_span[1 ≤ a1, t1, p1 ≤ 10^7]），其中 #cf_span[a1] 为可下载的最大数据量（字节），#cf_span[t1] 为下载一字节所需时间（毫秒），#cf_span[p1] 为套餐价格（布尔）。第三行描述第二个附加套餐，包含三个整数 #cf_span[a2], #cf_span[t2] 和 #cf_span[p2]（#cf_span[1 ≤ a2, t2, p2 ≤ 10^7]），其中 #cf_span[a2] 为可下载的最大数据量（字节），#cf_span[t2] 为下载一字节所需时间（毫秒），#cf_span[p2] 为套餐价格（布尔）。Polycarp 可以多次购买任意套餐。一旦购买，该套餐将取代常规套餐，直至其数据限额被完全用尽。在套餐使用期间，Polycarp 无法购买其他套餐或切换回常规互联网套餐。\n\n## Output\n\n请输出 Polycarp 为在不超过 #cf_span[T] 毫秒内下载 B++ 编译器所需支付的最少金额。若无解，请输出整数 _-1_。\n\n[samples]\n\n## Note\n\n在第一个示例中，Polycarp 必须购买第一个附加套餐 5 次，不购买第二个附加套餐。他下载了 120 字节（共 #cf_span[26·5 = 130] 字节），耗时 #cf_span[120·8 = 960] 毫秒（#cf_span[960 ≤ 964]），花费 #cf_span[8·5 = 40] 布尔。\n\n在第二个示例中，Polycarp 有足够时间下载 #cf_span[10] 字节，耗时 #cf_span[10·20 = 200] 毫秒，恰好等于下载时间上限。\n\n在第三个示例中，Polycarp 需要购买一个第一个附加套餐和一个第二个附加套餐。\n\n在第四个示例中，Polycarp 无法在规定时间内下载完文件。","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ f, T, t_0 \\in \\mathbb{Z}^+ $ be the file size (bytes), maximum allowed time (ms), and time per byte under regular tariff.  \nLet $ (a_1, t_1, p_1), (a_2, t_2, p_2) \\in \\mathbb{Z}^+^3 $ be the parameters of the two packages: maximum bytes, time per byte, and price.  \n\nLet $ x, y, z \\in \\mathbb{Z}_{\\ge 0} $ denote the number of bytes downloaded using:  \n- the regular tariff,  \n- the first package (used $ \\left\\lfloor \\frac{z_1}{a_1} \\right\\rfloor $ times, but total bytes $ z_1 \\leq f $),  \n- the second package (used $ \\left\\lfloor \\frac{z_2}{a_2} \\right\\rfloor $ times, but total bytes $ z_2 \\leq f $),  \n\nwith $ z_1, z_2 \\in \\mathbb{Z}_{\\ge 0} $, $ x + z_1 + z_2 = f $, and $ x \\leq f $, $ z_1 \\leq f $, $ z_2 \\leq f $.  \n\n**Constraints**  \n1. $ x + z_1 + z_2 = f $  \n2. $ x \\cdot t_0 + z_1 \\cdot t_1 + z_2 \\cdot t_2 \\leq T $  \n3. $ z_1 \\leq a_1 \\cdot \\left\\lceil \\frac{z_1}{a_1} \\right\\rceil $, $ z_2 \\leq a_2 \\cdot \\left\\lceil \\frac{z_2}{a_2} \\right\\rceil $ — *implied by integer usage*  \n4. Cost: $ \\text{Cost} = p_1 \\cdot \\left\\lceil \\frac{z_1}{a_1} \\right\\rceil + p_2 \\cdot \\left\\lceil \\frac{z_2}{a_2} \\right\\rceil $  \n\n**Objective**  \nMinimize $ p_1 \\cdot \\left\\lceil \\frac{z_1}{a_1} \\right\\rceil + p_2 \\cdot \\left\\lceil \\frac{z_2}{a_2} \\right\\rceil $  \nsubject to:  \n- $ x = f - z_1 - z_2 \\geq 0 $  \n- $ x t_0 + z_1 t_1 + z_2 t_2 \\leq T $  \n- $ z_1, z_2 \\in \\mathbb{Z}_{\\ge 0} $, $ z_1 \\leq f $, $ z_2 \\leq f $  \n\nIf no such $ (z_1, z_2) $ exists, output $-1$.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF883C","tags":["binary search","implementation"],"sample_group":[["120 964 20\n26 8 8\n13 10 4","40"],["10 200 20\n1 1 1\n2 2 3","0"],["8 81 11\n4 10 16\n3 10 12","28"],["8 79 11\n4 10 16\n3 10 12","\\-1"]],"created_at":"2026-03-03 11:00:39"}}