32658번 - 오장원전

문제

촉나라의 제갈량과 위나라의 사마의는 오장원에서 대치하고 있다. 제갈량은 여러 번의 보급을 시도해 작전 중인 부대로 총 $X$의 보급을 보내려고 한다.

제갈량은 한 번에 양의 정수 $a$만큼의 보급을 시도할 수 있으며 이때 $a+C$의 비용을 지불해야 한다.

사마의는 제갈량의 보급 시도를 최대 $K$ 번까지 차단할 수 있으며 보급 시도가 차단되면 제갈량은 비용만 소모하고 보급은 실패로 돌아가게 된다.

제갈량은 최소의 비용을 사용해서 총 $X$의 보급을 보내려고 하고, 사마의는 제갈량이 최대의 비용을 사용하도록 보급 시도를 차단한다. 두 책사는 모두 목적을 달성하기 위해 최선을 다해 임한다. 당신은 제갈량이 $X$의 보급을 모두 보내기 위한 최소 비용을 계산해야 한다.

입력

첫 번째 줄에 양의 정수 $X, K, C$가 공백으로 구분되어 주어진다.

$X$는 제갈량이 보내려고 하는 보급의 목표이다. $(1 \leq X \leq 10,000円)$

$K$는 사마의가 보급을 차단할 수 있는 최대 횟수이다. $(1 \leq K \leq 300)$

$C$는 제갈량이 보급을 시도할 때마다 필요한 비용이다. 구체적으로, $a$의 보급을 시도할 때 $a+C$의 비용을 지불해야 한다. $(1 \leq C \leq 10^9)$

출력

첫 번째 줄에 제갈량이 $X$의 보급을 모두 보내기 위한 최소 비용을 출력한다.

제한

힌트