Cars

Time limit2sMemory limit1024 MB

Summary

Simulate n cars adjusting speed by 5 m/s every 5 seconds to keep gaps within 80 to 100 meters, and output -1 on collision or the front car distance.

Level: Easy2 of 10
Topics: Simulation, Implementation
Solved: No attempts yet

Problem

On a straight single lane road, $n$ cars stand in one line, and the space between every two neighbouring cars is $d$ meters. All of them face the same direction, and they start moving one after another.

At the moment they set off, only the front car moves, at $v$ meters per second, and every other car stands still. Every 5 seconds after the start, all cars measure the space to the car in front of them or behind them at the same moment and change their speed when the rules below say so.

The front car increases its speed by 5 meters per second if the space to the car behind it is less than 80 meters, decreases its speed by 5 meters per second if that space is more than 100 meters, and keeps its speed otherwise.

Every other car decreases its speed by 5 meters per second if the space to the car in front of it is less than 80 meters, increases its speed by 5 meters per second if that space is more than 100 meters, and keeps its speed otherwise.

Against the laws of physics, a change of speed takes effect immediately. A car that stands still and has to decrease its speed keeps standing still. Cars never move backwards. A collision happens when the space between two cars becomes 0 or less.

Decide whether a collision happened during the first $t$ intervals of 5 seconds, and if it did not, compute how far the front car travelled.

Speeds change only at interval boundaries. During the first interval every car keeps the speed it started with, and from the second interval on the change happens at the moment the interval begins. Spaces are checked at the end of each interval. Inside one interval every speed is constant.

If $n = 1$ there is no car behind the front car, so the front car keeps the speed $v$ the whole time.

The length of a car does not count.

Input

The first line contains the integers $n$ , $v$ , $d$ , $t$ in this order, separated by spaces.

$1 \le n, v, d, t \le 1000$

Output

If no collision happened, print on one line the distance the front car travelled, as a whole number of meters. If a collision happened, print -1.

Examples3

Example 1
Input
```
5 10 80 3
```
Expected output
```
75
```
Example 2
Input
```
2 60 100 14
```
Expected output
```
-1
```
Example 3
Input
```
20 5 5 100
```
Expected output
```
2550
```