「WHOI-1」Derives

你有 $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)}$ 请问，你在最差情况下（**即每轮选出不正常的都是 $k_i$ 个一堆的**）最少需要多长时间找出那枚假币？ ## Input 一行三个正整数，代表 $n,a,b$。 ## Output 第一行两个个非负整数 $f,m$，代表最小可能的时间和你的方案的轮数。 接下来一行 $m$ 个正整数，代表 $k_i$。 [samples] ## Background 你的钱里面混进去了一个假币。 ## Note **说明** **你需要尽量使得花费的时间更少。** 本题采用 Special Judge。 首先，你输出的答案一定要合法，也就是你输出的答案要与下面的选择方法符合，否则将获得 $0$ 分。 接下来，评测机会对你的输出进行判断。如果你输出的答案合法且与正确答案的差 $\le9$，那么你将获得 $(10-d)\times100\%$ 的分数。例如，如果你输出的答案与正确答案的差为 $4$，那么你将获得 $60\%$ 的分数。如果你输出的答案等于正确答案，你将获得 $100\%$ 的分数。请不要输出多余的数字或少输出。 **数据范围** - $\text{subtask 1(10pts)}:$ $1\le n\le2000$。 - $\text{subtask 2(20pts)}:$ $1\le n\le75000$。 - $\text{subtask 3(30pts)}:$ $1\le n\le10^7$。 - $\text{subtask 4(40pts)}:$ $1\le n\le10^9$。 对于所有数据，满足 $0<a,b\le10^9$。 **样例说明** 对于第一个样例，进行两轮。$x_1=20,k_1=4,x_2=4,k_2=1$。答案 $f=20+15+4+12=51$。