오장원전

서기 234년, 촉나라의 제갈량은 촉의 국력을 기울여 마지막 북벌을 준비한다. 3년간의 준비 끝에 북벌군의 규모는 약 10만이 되었고, 이는 이릉대전 이후 촉의 북벌 규모 중 두 번째로 큰 군세다. 위나라의 사마의는 이 소식을 듣고 곧바로 제갈량을 막으러 나선다. 사마의는 제갈량이 야곡을 통해 넘어온다는 소식을 듣고 미현(眉縣)으로 이동한다. 그리고 제갈량이 무공(武功)과 오장원(五丈原) 중 어느 곳으로 이동할지 지켜본다.

"제갈량이 만약 용감한 자라면 응당 무공을 나와 산을 따라 동진할 것이오. 만약 서쪽으로 가서 오장원에 오른다면 제(諸軍)이 무사할 것이오."

신중한 성격의 제갈량은 군사를 오장원으로 향하고, 위촉의 군대는 오장원에서 격돌하게 된다.

촉나라의 제갈량과 위나라의 사마의는 오장원에서 대치하고 있다. 제갈량은 여러 번 보급을 시도해 작전 중인 부대에 총 $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$의 보급을 모두 보내기 위한 최소 비용을 출력한다.