Exercise

Interview

Time limit2sMemory limit16 MB

Summary

Simulate a pulse that rises by T when exercising and falls by R when resting (bounded between m and M) to find the minimum minutes needed to accumulate N exercise minutes, or report impossibility.

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

Problem

Youngsik's routine is divided into one-minute intervals. In each minute, he must choose either to exercise or to rest.

If he exercises, his pulse increases by T. That is, if his pulse was X, then after exercising for one minute it becomes X+T. Youngsik does not want his pulse to exceed M, so he may exercise only when X+T is at most M.

If he rests, his pulse decreases by R. If his pulse was X, then after resting for one minute it becomes X-R. However, the pulse must never go below m, so if X-R is less than m, the pulse becomes m instead.

Youngsik's initial pulse is m. He wants to complete N minutes of exercise. Find the minimum elapsed time needed to complete N exercise minutes. The exercise minutes do not need to be consecutive.

Input

The first line contains five integers N, m, M, T, and R.

Output

Print the minimum elapsed time needed to complete N minutes of exercise. If it is impossible to complete N exercise minutes, print -1.

Constraints

1 <= N, T, R <= 200
50 <= m <= M <= 200

Hint

For the first visible test case, one optimal schedule is shown below.

Time	Action	Pulse after the action
1	Exercise	95
2	Exercise	120
3	Rest	105
4	Rest	90
5	Exercise	115
6	Rest	100
7	Rest	85
8	Exercise	110
9	Rest	95
10	Exercise	120

Examples5

Example 1
Input
```
5 70 120 25 15
```
Expected output
```
10
```
Example 2
Input
```
100 50 100 5 200
```
Expected output
```
109
```
Example 3
Input
```
1 60 70 11 11
```
Expected output
```
-1
```
Example 4
Input
```
200 50 200 150 1
```
Expected output
```
30050
```
Example 5
Input
```
19 89 143 17 13
```
Expected output
```
40
```