SOLVE
LATER
One day Benny came up with an excellent idea to become a business-pig! She knows that almost everyone likes candies.
Benny knows about that somewhere on the Earth candy-stock exists. She knows that at the i-th of n days she can buy or sell sweet called "Korovka", if she wants. The price for buying or selling the sweet at the i-th day equals to \(c_i\).
Unfortunately, Benny is not allowed to have more than one candy at some moment of time according to candy-stock rules. She firstly has to sell the candy and then may buy the new one.
Please, note, that at one day Benny could firstly sell the candy and then buy the new one.
From the beginning she has a vary big budget. Benny wants to make the maximal possible profit in case of making such business for n consecutive days and not breaking any candy-stock rules.
Array c is generated in the following way:
\(x_0 = 0\) \(x_i = ((x_{i-1} \bmod M) \cdot a + b) \bmod 2^{32}\)
\(c_i = \left\lfloor \frac{x_i}{2^{8}} \right\rfloor\)
Input format
The first line contains two integers: n and M.
The second line contains two integers: a and b.
Constraints
\(2 \leq n \leq 10^7\)
\(1 \leq M \leq 2^{30}\)
\(1 \leq a, b \leq 10^9\)
Output format
In a single line output the maximum profit Benny can get.
The array c will look like {4, 8, 12, 16, 20}. Let B
be buy and S
be sale.
B
— SB
— SB
— SB
— S
.
If you use the strategy above you will get the maximum profit.