ACSL Practice 2009

Task 2: Cars

On a straight single-lane road, there are n cars parked with a space of d meters wide separating every two adjacent cars. The cars will start to move successively in the same direction as follows. 

At the beginning, the first car moves at a speed of v meters per second, while the other cars are standing still. After every 5 seconds from the beginning, every car checks the distance to the car in front or behind, and adapts its speed, if necessary. 

The first car adapts as follows. If there are less than 80 meters space to the car behind it, it immediately increases its speed by 5 meters per second; if there are more than 100 meters space to the car behind it, it immediately decreases its speed by 5 meters per second; and otherwise it keeps its speed. 

All the other cars adapt as follows. If there are less than 80 meters space to the car in front, it immediately decreases its speed by 5 meters per second; if there are more than 100 meters space to the car in front, it immediately increases its speed by 5 meters per second; and otherwise it keeps its speed. 

Against the laws of physics, any change of speed takes immediate effect. If a car stands still and needs to decrease speed, it will remain standing still; the cars never go backwards. A collision occurs if the space between two cars becomes 0 or less. 

The goal is to find out if a collision has occurred after t 5-second-intervals, and if not, how far the first car will have traveled. 

Note that the length of the cars is irrelevant. 

Example 1. There are n = 5 cars. The first car starts with v = 10 meters per second, there are d = 80 meters between adjacent cars and there are t = 3 5-second-intervals. 

  1. The first car will travel 10*5 = 50 meters in the first period, while all other cars stand still in this period.
  2. At the beginning of the second period, the first car decelerates to a speed of 5 meters per second, because there is now 130 meters space to the car behind, and thus travels 5 * 5 = 25 meters in the second period. At the beginning of the second period, the second car accelerates to a speed of 5 meters per second, because there is 130 meters space to the car in front, and thus travels 5 * 5 = 25 meters in the second period. At the beginning of the second period, all other cars remain standing, because there still are 80 meters space to the car in front.
  3. At the beginning of the third period, the first car decelerates to a speed of 0 meters per second, because there is again 130 meters space to the car behind, and thus travels 0 * 5 = 0 meters in the third period.

Answer: The first car will have traveled 50 + 25 + 0 = 75 meters after the first three periods. 

Example 2. There are n = 2 cars. The first car starts with v = 60 meters per second, there are d = 100 meters between adjacent cars and there are t = 14 5-second-intervals. 
Answer: A collision occurs. 

Example 3. There are n = 20 cars. The first car starts with v = 5 meters per second, there are d = 5 meters between adjacent cars and there are t = 100 5-second-intervals. 
Answer: The first car will have traveled 2550 meters.

Input

The input consists of a line containing the four integers nvd, and t in this order, and 1 ≤ nvdt ≤ 1000. 

Output

The output contains the number of meters traveled by the first car if there is no collision. If there is a collision, output -1.

Examples

Input

5 10 80 3

Output

75

Input

2 60 100 14

Output

-1

Input

20 5 5 100

Output

2550

All Submissions
Best Solutions


Point Value: 10 (partial)
Time Limit: 2.00s
Memory Limit: 16M
Added: May 19, 2009

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

It's quiet in here...