21645번 - Ролевая игра 다국어

문제

Вася готовит инвентарь для ролевой игры. В игре должны принять участие n игроков, каждый из которых будет изображать персонажа фантастического мира. В процессе игры каждый персонаж будет обладать некоторым уровнем x, который представляет собой целое число от 1 до m.

Для обозначения уровня планируется использовать специальные значки двух цветов. Белый значок обозначает один уровень, а красный значок — k уровней. Игрок, изображающий персонажа с уровнем x, должен иметь a белых значков и b красных значков, чтобы сумма (a + bk) была равна x. При этом персонажу не разрешается иметь более чем (k – 1) белых значков.

Значки для игры готовятся заранее, однако уровни персонажей заранее неизвестны. Для успешного проведения игры всем персонажам необходимо выдать соответствующее их уровням количество значков. Возникает вопрос: какое минимальное суммарное количество значков необходимо подготовить для успешного проведения игры при любых уровнях участвующих персонажей.

Требуется написать программу, которая по заданным числам n, m и k вычисляет минимальное количество значков, которое необходимо подготовить для успешного проведения игры.

입력

Входной файл содержит расположенные в одной строке три целых числа: n, m и k (1 ≤ n ≤ 10⁴, 1 ≤ m ≤ 10⁵, 1 ≤ k ≤ 10⁵).

출력

В выходном файле должно содержаться одно целое число — минимальное количество значков, которое требуется подготовить.

제한

힌트

В приведенном примере необходимо подготовить 6 красных и 3 белых значка.