Rating changes for last rounds are temporarily rolled back. They will be returned soon. ×
H. Another Goose Goose Duck Problem
time limit per test
1 second
memory limit per test
1024 mebibytes
input
standard input
output
standard output

Teacher Rice likes playing the famous game 'Goose Goose Duck'. In the game, Teacher Rice plays a duck and his goal is to kill the geese. Every time he kills a goose, he should wait $$$a$$$ seconds for his killing skill to cool down. Since Teacher Rice's role is the Serial Killer, the time Teacher Rice waits depends on which type of goose he kills. Because Teacher Rice is a skilled killer, he can make the waiting time $$$a$$$ to be an arbitrary integer in $$$[\ell,r]$$$.

Teacher Rice meets a goose every $$$b$$$ seconds. Once Teacher Rice meets a goose, he can choose to kill the goose if his killing skill is ready, otherwise the goose runs away immediately and he can not kill this goose.

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

Input

There are four integers in one line: $$$\ell$$$, $$$r$$$, $$$b$$$, $$$k$$$ ($$$1\leq \ell\leq r\leq 10^9$$$, $$$1\leq b,k\leq 10^9$$$).

Output

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

Examples
Input
6 6 3 3
Output
18
Input
2 3 5 4
Output
20