라이스 선생님은 유명한 '구스 구스 덕' 게임을 하는 것을 좋아합니다. 게임에서 라이스 선생님은 오리 역할을 하고 그의 목표는 거위들을 죽이는 것입니다. 선생님이 거위를 죽일 때마다 a초 동안 기다려야 다시 거위를 죽일 준비가 됩니다. 라이스 선생님의 역할은 연쇄살거위마이기 때문에 선생님이 기다리는 시간은 어떤 종류의 거위를 죽이느냐에 따라 달라집니다. 라이스 선생님은 숙련된 킬러이기 때문에 대기 시간 a를 임의의 정수 [l, r]로 만들 수 있습니다.
라이스 선생님은 b초마다 거위를 만납니다. 거위를 만났을 때, 거위를 죽일 준비가 되어있으면 거위를 죽일 수 있습니다. 하지만 준비가 되어있지 않으면 거위는 즉시 도망쳐버려 이 거위는 죽일 수 없게 됩니다.
라이스 선생님은 거위 k마리를 죽이는 데 걸리는 시간의 최솟값을 알고 싶어합니다.
입력
정수 l, r, b, k가 주어진다 (1 <= l <= r <= 10^9, 1 <= b, k <= 10^9).
kimbh0412 3년 전 4
문제
라이스 선생님은 유명한 '구스 구스 덕' 게임을 하는 것을 좋아합니다. 게임에서 라이스 선생님은 오리 역할을 하고 그의 목표는 거위들을 죽이는 것입니다. 선생님이 거위를 죽일 때마다 a초 동안 기다려야 다시 거위를 죽일 준비가 됩니다. 라이스 선생님의 역할은 연쇄살거위마이기 때문에 선생님이 기다리는 시간은 어떤 종류의 거위를 죽이느냐에 따라 달라집니다. 라이스 선생님은 숙련된 킬러이기 때문에 대기 시간 a를 임의의 정수 [l, r]로 만들 수 있습니다.
라이스 선생님은 b초마다 거위를 만납니다. 거위를 만났을 때, 거위를 죽일 준비가 되어있으면 거위를 죽일 수 있습니다. 하지만 준비가 되어있지 않으면 거위는 즉시 도망쳐버려 이 거위는 죽일 수 없게 됩니다.
라이스 선생님은 거위 k마리를 죽이는 데 걸리는 시간의 최솟값을 알고 싶어합니다.
입력
정수 l, r, b, k가 주어진다 (1 <= l <= r <= 10^9, 1 <= b, k <= 10^9).
출력
거위 k마리를 죽이는 데 걸리는 최소 시간을 출력한다.