Background

One counterfeit coin has been mixed into your money.

Problem Description

You have $n$ coins. After accurate measurement, you find that there must be exactly one counterfeit coin, and its mass is different from the other coins. You want to find this counterfeit coin.

In round $i$, suppose you currently have $x_i$ coins. You will divide all the coins into several groups, with $k_i$ coins in each group, and put the remaining coins (if any) into one additional group. Picking up each coin takes $a$ seconds, so this will take $a x_i$ seconds. Next, you will weigh each group. Weighing one group takes $b$ seconds, so this will take $b\cdot\left\lceil\frac{x_i}{k_i}\right\rceil$ seconds. Since there is only one counterfeit coin, only one group will have a mass different from the normal mass. After weighing all groups, you will select the group whose mass is different from the normal mass and enter the next round, letting $x_{i+1}=k_i$. You keep doing this until $x_i=1$. Suppose there are $m$ rounds in total, then the total time is

$$f=\sum\limits_{i=1}^{m}{\left(ax_i+b\cdot\left\lceil\frac{x_i}{k_i}\right\rceil\right)}.$$

In the worst case (that is, in every round the abnormal group is always a group of $k_i$ coins), what is the minimum time needed to find the counterfeit coin?

Input Format

One line with three positive integers, representing $n,a,b$.

Output Format

The first line contains two non-negative integers $f,m$, representing the minimum possible time and the number of rounds in your plan.

The next line contains $m$ positive integers, representing $k_i$.

20 1 3

51 2
4 1

1000 10 100

13570 4
72 12 3 1

Hint

Explanation

You should try your best to make the total time as small as possible.

This problem uses Special Judge.

First, the answer you output must be valid, i.e. your output must match the selection method described above, otherwise you will get $0$ points.

Then, the judge will evaluate your output. If your output is valid and its difference from the correct answer is $\le9$, you will get a score of $(10-d)\times100\%$. For example, if the difference between your output and the correct answer is $4$, you will get $60\%$. If your output equals the correct answer, you will get $100\%$. Please do not output extra numbers or output fewer numbers than required.

Constraints

• $\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$.

For all testdata, $0<a,b\le10^9$.

Sample Explanation

For the first sample, there are two rounds. $x_1=20,k_1=4,x_2=4,k_2=1$. The answer is $f=20+15+4+12=51$.

Translated by ChatGPT 5