### Problem Statement

You have two lists of numbers, X and Y, each containing exactly N elements. You can optionally apply any number of circular shifts to each list. A circular shift means removing the last element from a list and re-inserting it before the first element. For example, {1, 2, 3} would become {3, 1, 2}, and {3, 1, 2} would become {2, 3, 1}. After you apply any circular shifts, the final score is calculated as:

X*Y + X*Y + ... + X[N-1]*Y[N-1]

You are given ints Z0, A, B and M. Generate a list Z of length 2*N, using the following recursive definition:

Z = Z0 MOD M

Z[i] = (Z[i-1]*A+B) MOD M (note that Z[i-1]*A+B may overflow a 32-bit integer)

Then, generate lists X and Y, each of length N, using the following definitions:

X[i] = Z[i] MOD 100

Y[i] = Z[i+N] MOD 100

Return the maximal final score you can achieve.

### Definition

 Class: CircularShifts Method: maxScore Parameters: int, int, int, int, int Returns: int Method signature: int maxScore(int N, int Z0, int A, int B, int M) (be sure your method is public)

### Notes

-In the statement, "A MOD B" represents the remainder of integer division of A by B. For example, 14 MOD 5 = 4 and 20 MOD 4 = 0.
-The author's solution does not depend on any properties of the pseudorandom generator. It would solve any input of allowed size within the given limits.

### Constraints

-N will be between 1 and 60,000, inclusive.

-Z0, A and B will each be between 0 and 1,000,000,000, inclusive.

-M will be between 1 and 1,000,000,000, inclusive.

### Examples

0)

 `5` `1` `1` `0` `13`
`Returns: 5`
 Both lists contain only ones, so no matter how many shifts you perform, the score will always be 5.
1)

 `4` `1` `1` `1` `20`
`Returns: 70`
 The lists are {1, 2, 3, 4} and {5, 6, 7, 8}. The maximal score is achieved by not making any shifts.
2)

 `10` `23` `11` `51` `4322`
`Returns: 28886`
 The lists are (23, 4, 95, 20, 17, 94, 63, 44, 13, 96) and (87, 54, 13, 18, 61, 24, 17, 94, 53, 2).
3)

 `1000` `3252` `3458736` `233421` `111111111`
`Returns: 2585408`
4)

 `141` `96478` `24834` `74860` `92112`
`Returns: 419992`

#### Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=10336

#### Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=13698&pm=10336

Gluk

#### Testers:

PabloGilberto , ivan_metelsky , ged , zhuzeyuan

Math