CSES - Aalto Competitive Programming 2024 - wk3 - Mon - Wario kart I
  • Time limit: 1.00 s
  • Memory limit: 512 MB

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

Input

First line contains three integers, n,\,m,\,k.

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