Benny and Candies
Tag(s):

## Algorithms, Easy-Medium, Greedy

Problem
Editorial
Analytics

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.

SAMPLE INPUT
5 100500
1 1024

SAMPLE OUTPUT
16

Explanation

The array c will look like {4, 8, 12, 16, 20}. Let B be buy and S be sale.

BSBSBSBS.

If you use the strategy above you will get the maximum profit.

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, Visual Basic

## CODE EDITOR

Initializing Code Editor...

## This Problem was Asked in

Challenge Name

January Clash '17

OTHER PROBLEMS OF THIS CHALLENGE
• Math > Number Theory
• Algorithms > Graphs
• Data Structures > Advanced Data Structures