{"raw_statement":[{"iden":"statement","content":"Pupils decided to go to amusement park. Some of them were with parents. In total, _n_ people came to the park and they all want to get to the most extreme attraction and roll on it exactly **once**.\n\nTickets for group of _x_ people are sold on the attraction, there should be at least one adult in each group (it is possible that the group consists of one adult). The ticket price for such group is _c_1 + _c_2·(_x_ - 1)2 (in particular, if the group consists of one person, then the price is _c_1).\n\nAll pupils who came to the park and their parents decided to split into groups in such a way that each visitor join exactly one group, and the total price of visiting the most extreme attraction is as low as possible. You are to determine this minimum possible total price. There should be at least one adult in each group."},{"iden":"input","content":"The first line contains three integers _n_, _c_1 and _c_2 (1 ≤ _n_ ≤ 200 000, 1 ≤ _c_1, _c_2 ≤ 107) — the number of visitors and parameters for determining the ticket prices for a group.\n\nThe second line contains the string of length _n_, which consists of zeros and ones. If the _i_\\-th symbol of the string is zero, then the _i_\\-th visitor is a pupil, otherwise the _i_\\-th person is an adult. It is guaranteed that there is at least one adult. It is possible that there are no pupils."},{"iden":"output","content":"Print the minimum price of visiting the most extreme attraction for all pupils and their parents. Each of them should roll on the attraction exactly once."},{"iden":"examples","content":"Input\n\n3 4 1\n011\n\nOutput\n\n8\n\nInput\n\n4 7 2\n1101\n\nOutput\n\n18"},{"iden":"note","content":"In the first test one group of three people should go to the attraction. Then they have to pay 4 + 1 * (3 - 1)2 = 8.\n\nIn the second test it is better to go to the attraction in two groups. The first group should consist of two adults (for example, the first and the second person), the second should consist of one pupil and one adult (the third and the fourth person). Then each group will have a size of two and for each the price of ticket is 7 + 2 * (2 - 1)2 = 9. Thus, the total price for two groups is 18."}],"translated_statement":[{"iden":"statement","content":"学生们决定去游乐园。其中一些人有父母陪同。总共有 #cf_span[n] 人来到公园，他们都想前往最刺激的设施并恰好乘坐一次。\n\n该设施出售针对 #cf_span[x] 人的团体票，每个团体必须至少包含一名成人（团体可以仅由一名成人组成）。此类团体的票价为 #cf_span[c1 + c2·(x - 1)2]（特别地，若团体仅有一人，则票价为 #cf_span[c1]）。\n\n所有来到公园的学生及其父母决定将自己分成若干组，使得每位游客恰好属于一个组，且参观最刺激设施的总费用尽可能低。你需要确定这个最小可能的总费用。每个组必须至少包含一名成人。\n\n第一行包含三个整数 #cf_span[n], #cf_span[c1] 和 #cf_span[c2]（#cf_span[1 ≤ n ≤ 200 000], #cf_span[1 ≤ c1, c2 ≤ 107]）——分别表示游客人数以及确定团体票价的参数。\n\n第二行是一个长度为 #cf_span[n] 的字符串，由 0 和 1 组成。如果字符串的第 #cf_span[i] 个字符是 0，则第 #cf_span[i] 位游客是学生；否则，第 #cf_span[i] 位是成人。保证至少有一名成人，也可能没有学生。\n\n请输出所有学生及其父母参观最刺激设施的最小总费用。每个人必须恰好乘坐一次。"},{"iden":"input","content":"第一行包含三个整数 #cf_span[n], #cf_span[c1] 和 #cf_span[c2]（#cf_span[1 ≤ n ≤ 200 000], #cf_span[1 ≤ c1, c2 ≤ 107]）——分别表示游客人数以及确定团体票价的参数。第二行是一个长度为 #cf_span[n] 的字符串，由 0 和 1 组成。如果字符串的第 #cf_span[i] 个字符是 0，则第 #cf_span[i] 位游客是学生；否则，第 #cf_span[i] 位是成人。保证至少有一名成人，也可能没有学生。"},{"iden":"output","content":"请输出所有学生及其父母参观最刺激设施的最小总费用。每个人必须恰好乘坐一次。"},{"iden":"examples","content":"输入3 4 1011输出8输入4 7 21101输出18"},{"iden":"note","content":"在第一个测试用例中，应将三人组成一组前往设施。此时需支付 #cf_span[4 + 1 * (3 - 1)2 = 8]。在第二个测试用例中，最好分成两组前往。第一组由两名成人组成（例如第一和第二位游客），第二组由一名学生和一名成人组成（第三和第四位游客）。每组人数均为二，每组票价为 #cf_span[7 + 2 * (2 - 1)2 = 9]。因此，两组的总费用为 #cf_span[18]。"}],"sample_group":[],"show_order":[],"formal_statement":"**Definitions:**\n\n- Let $ n $: total number of visitors.\n- Let $ c_1, c_2 $: parameters defining the group ticket price.\n- Let $ s \\in \\{0,1\\}^n $: binary string where $ s_i = 0 $ denotes a pupil, $ s_i = 1 $ denotes an adult.\n- Let $ a $: number of adults, $ a = \\sum_{i=1}^n s_i $, with $ a \\geq 1 $.\n- Let $ p = n - a $: number of pupils.\n\n**Constraint:**\n- Each group must contain **at least one adult**.\n\n**Group Price Function:**\n- For a group of size $ x $, the price is:  \n  $$\n  f(x) = c_1 + c_2 \\cdot (x - 1)^2\n  $$\n\n**Objective:**\n- Partition the $ n $ visitors into $ k \\geq 1 $ disjoint groups (each of size $ \\geq 1 $) such that:\n  1. Each group contains **at least one adult**.\n  2. Every visitor is in exactly one group.\n  3. The **total cost** $ \\sum_{i=1}^k f(x_i) $ is minimized, where $ x_i $ is the size of group $ i $, and $ \\sum_{i=1}^k x_i = n $.\n\n**Formal Problem:**\n\nMinimize  \n$$\n\\sum_{i=1}^k \\left( c_1 + c_2 \\cdot (x_i - 1)^2 \\right)\n$$  \nsubject to:  \n- $ x_i \\in \\mathbb{Z}^+, \\quad \\sum_{i=1}^k x_i = n $,  \n- $ k \\leq a $ (since each group needs at least one adult),  \n- $ k \\geq 1 $.\n\nEquivalently, since $ c_1 $ is added once per group:  \n$$\n\\text{Minimize} \\quad k \\cdot c_1 + c_2 \\cdot \\sum_{i=1}^k (x_i - 1)^2\n$$  \nwith $ \\sum_{i=1}^k x_i = n $, $ 1 \\leq k \\leq a $, $ x_i \\geq 1 $.\n\nLet $ y_i = x_i - 1 \\geq 0 $, then $ \\sum_{i=1}^k y_i = n - k $, and the objective becomes:  \n$$\nk \\cdot c_1 + c_2 \\cdot \\sum_{i=1}^k y_i^2\n$$  \nsubject to:  \n- $ y_i \\in \\mathbb{Z}_{\\geq 0} $,  \n- $ \\sum_{i=1}^k y_i = n - k $,  \n- $ 1 \\leq k \\leq a $.\n\nThus, for fixed $ k $, minimize $ \\sum_{i=1}^k y_i^2 $ subject to $ \\sum y_i = n - k $, $ y_i \\geq 0 $, integer.\n\n**Known Result:**  \nFor fixed sum $ S = n - k $, the sum of squares $ \\sum y_i^2 $ is minimized when the $ y_i $'s are as equal as possible.\n\nLet $ q = \\left\\lfloor \\frac{n - k}{k} \\right\\rfloor $, $ r = (n - k) \\mod k $.  \nThen minimal $ \\sum y_i^2 = r \\cdot (q + 1)^2 + (k - r) \\cdot q^2 $.\n\nThus, the minimal total cost for a given $ k \\in [1, a] $ is:  \n$$\nC(k) = k \\cdot c_1 + c_2 \\cdot \\left[ r \\cdot (q + 1)^2 + (k - r) \\cdot q^2 \\right]\n$$  \nwhere $ q = \\left\\lfloor \\frac{n - k}{k} \\right\\rfloor $, $ r = (n - k) \\mod k $.\n\n**Final Objective:**\n\n$$\n\\boxed{\n\\min_{k=1}^{a} \\left\\{ k \\cdot c_1 + c_2 \\cdot \\left[ r \\cdot (q + 1)^2 + (k - r) \\cdot q^2 \\right] \\right\\}\n}\n\\quad \\text{where} \\quad\nq = \\left\\lfloor \\frac{n - k}{k} \\right\\rfloor, \\quad r = (n - k) \\bmod k\n}","simple_statement":null,"has_page_source":false}