Another Goose Goose Duck Problem

Interview

Time limit1sMemory limit1024 MB

Summary

Choose an integer cooldown a in [l, r] and find the minimum time to kill k geese that arrive every b seconds.

Level: Medium4 of 10
Topics: Math, Greedy
Solved: No attempts yet

Problem

Teacher Rice likes playing the famous game 'Goose Goose Duck'. In the game, he plays a duck, and his goal is to kill geese. Each time he kills a goose, he must wait $a$ seconds for his kill skill to cool down. Since Teacher Rice's role is the Serial Killer, the waiting time depends on which type of goose he kills. As a skilled killer, he can set the waiting time $a$ to any integer in $[\ell,r]$ .

Teacher Rice meets a goose every $b$ seconds. When he meets a goose and his kill skill is ready, he can choose to kill it. Otherwise, the goose runs away immediately and he cannot kill it.

Teacher Rice wants to know the minimum time he needs to kill $k$ geese.

Input

One line contains four integers $\ell$ , $r$ , $b$ , $k$ ( $1\leq \ell\leq r\leq 10^9$ , $1\leq b,k\leq 10^9$ ).

Output

Output one integer, the time Teacher Rice needs to kill $k$ geese.

Examples2

Example 1
Input
```
6 6 3 3
```
Expected output
```
18
```
Example 2
Input
```
2 3 5 4
```
Expected output
```
20
```