学生决定去游乐园。其中一些人与父母在一起。总共有 n 个人来到公园,他们都想到达最极限的景点并在上面滚一次。
景点出售x人团体门票,每组至少须有一名成人(也有可能团体由一名成人组成)。该团体的票价为c1 + c2·(x - 1)2(特别是,如果该团体由一个人组成,则价格为c1)。
所有来公园的学生和家长决定分成几组,每个游客都只参加一组,并且参观最极限景点的总费用尽可能低。您需要确定这个最低可能总价。每组中至少应有一名成人。
输入
第一行包含三个整数 n、c1 和 c2 (1 ≤ n ≤ 200 000, 1 ≤ c1, c2 ≤ 107) - 游客数量和用于确定团体票价的参数。
第二行包含长度为 n 的字符串,由 0 和 1 组成。如果字符串的第 i 个符号为零,则第 i 个访客是学生,否则第 i 个访客是成年人。保证至少有一名成人。可能没有学生。
输出
打印所有学生及其家长参观最极限景点的最低价格。他们每个人都应该在景点上滚动一次。
示例
输入 #1
3 4 1 011
输出 #1
8
输入 #2
4 7 2 1101
输出 #2
18
注意
在第一个测试中,一组三人应该去景点。那么他们必须支付 4 + 1 * (3 - 1)2 = 8。
第二次测试时最好分两组去景点。第一组应由两名成人(例如第一人和第二人)组成,第二组应由一名学生和一名成人(第三人和第四人)组成。那么每组人数为两人,每组门票价格为 7 + 2 * (2 - 1)2 = 9。因此,两组的总价格为 18。