- 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