Another Goose Goose Duck Problem

시간 제한1초메모리 제한1024 MB

요약

쿨다운 범위 [l, r]과 b초마다 등장하는 거위, 목표 k마리가 주어질 때, 정수 쿨다운 a를 [l, r]에서 하나 골라 k마리를 처치하는 최소 시간을 구한다.

난이도: 보통10점 중 7점
유형: 수학, 이분 탐색, 그리디, 구현
정답자: 아직 제출이 없습니다

문제

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.

입력

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 one integer denotes the time Teacher Rice needs to kill $k$ geese.

예제2

예제 1
입력
```
6 6 3 3
```
예상 출력
```
18
```
예제 2
입력
```
2 3 5 4
```
예상 출력
```
20
```