Uolevi and Maija are playing Wario Kart, a popular racing game. So far, Maija is having a perfect race, while Uolevi is lagging behind.

The cars normally move at a speed of 100 m/s, but there are also m boost pads numbered 1,\,2,\,\dots,\,m; the i-th is located a_i \times 100 meters from the starting line. A boost pad doubles a car's speed for one second. While one boost is active, another cannot be picked up. The racing track is circular and has a length of n \times 100 meters. Calculate Maija's position from the starting line k seconds after the race started.

Input

The first line contains three integers: n,\,m,\,k.

The second line contains m distinct integers: a_1,\,a_2,\,\dots,\,a_m.

Output

Maija's distance from the starting line, in meters.

Constraints

• 1 \leq n \leq 10^5
• 0 \leq m \leq n
• 0 \leq k \leq 5 \times 10^5
• 0 \leq a_i < n
• a_i < a_j if i < j
• All input values are integers

Example 1

Input:

10 2 2 
1 2

Output:

300

Example 2

Input:

5 3 15 
2 3 4

Output:

400

Example 3

Input:

1 0 1

Output:

0