{"raw_statement":[{"iden":"background","content":"你的钱里面混进去了一个假币。"},{"iden":"statement","content":"你有 $n$ 枚硬币。经过准确的测量，你发现一定有一枚是假币，假币的质量与其他硬币不同。你想要找出这枚假币。\n\n第 $i$ 轮，假设你当时有 $x_i$ 枚硬币，你会把当前钱堆所有钱分配到若干组，每组 $k_i$ 个，最终剩下的再单独分一组。每个硬币你要拿起来需要 $a$ 秒，那么这将会花费你 $ax_i$ 秒的时间。接下来，你会称量每一组，称量每组需要 $b$ 秒，所以这将会花费你 $b\\cdot\\lceil\\frac{x_i}{k_i}\\rceil$ 秒的时间。由于只有一枚假币，那么只会有一堆的质量与正常的质量不同。**在称量所有堆之后**，你将会选出与正常质量不同的那一堆，并进入下一轮，让 $x_{i+1}=k_i$。一直执行，直到 $x_i=1$。假设进行了 $m$ 轮，那么花费时间 $f=\\sum\\limits_{i=1}^{m}{(ax_i+b\\cdot\\lceil\\frac{x_i}{k_i}\\rceil)}$\n\n请问，你在最差情况下（**即每轮选出不正常的都是 $k_i$ 个一堆的**）最少需要多长时间找出那枚假币？"},{"iden":"input","content":"一行三个正整数，代表 $n,a,b$。"},{"iden":"output","content":"第一行两个个非负整数 $f,m$，代表最小可能的时间和你的方案的轮数。\n\n接下来一行 $m$ 个正整数，代表 $k_i$。"},{"iden":"note","content":"**说明**\n\n**你需要尽量使得花费的时间更少。**\n\n本题采用 Special Judge。\n\n首先，你输出的答案一定要合法，也就是你输出的答案要与下面的选择方法符合，否则将获得 $0$ 分。\n\n接下来，评测机会对你的输出进行判断。如果你输出的答案合法且与正确答案的差 $\\le9$，那么你将获得 $(10-d)\\times100\\%$ 的分数。例如，如果你输出的答案与正确答案的差为 $4$，那么你将获得 $60\\%$ 的分数。如果你输出的答案等于正确答案，你将获得 $100\\%$ 的分数。请不要输出多余的数字或少输出。\n\n**数据范围**\n\n- $\\text{subtask 1(10pts)}:$ $1\\le n\\le2000$。\n- $\\text{subtask 2(20pts)}:$ $1\\le n\\le75000$。\n- $\\text{subtask 3(30pts)}:$ $1\\le n\\le10^7$。\n- $\\text{subtask 4(40pts)}:$ $1\\le n\\le10^9$。\n\n对于所有数据，满足 $0<a,b\\le10^9$。\n\n**样例说明**\n\n对于第一个样例，进行两轮。$x_1=20,k_1=4,x_2=4,k_2=1$。答案 $f=20+15+4+12=51$。"}],"translated_statement":null,"sample_group":[["20 1 3","51 2\n4 1"],["1000 10 100","13570 4\n72 12 3 1"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}