Вася готовит инвентарь для ролевой игры. В игре должны принять
участие n игроков, каждый из которых будет
изображать персонажа фантастического мира. В процессе игры каждый персонаж
будет обладать некоторым уровнем x,
который представляет собой целое число от 1 до m.
Для обозначения уровня планируется использовать специальные значки
двух цветов. Белый значок обозначает один уровень, а красный значок — k уровней. Игрок, изображающий персонажа с уровнем x, должен иметь a белых значков и b красных значков, чтобы сумма (a + bk) была
равна x. При этом персонажу не разрешается иметь
более чем
(k – 1) белых значков.
Значки для игры готовятся заранее, однако уровни персонажей заранее
неизвестны. Для успешного проведения игры всем персонажам необходимо выдать
соответствующее их уровням количество значков. Возникает вопрос: какое
минимальное суммарное количество значков необходимо подготовить для успешного
проведения игры при любых уровнях участвующих персонажей.
Требуется написать программу, которая по заданным числам n, m и
k вычисляет минимальное количество значков,
которое необходимо подготовить для успешного проведения игры.
Формат входного файла
Входной файл содержит расположенные в одной строке три целых числа: n, m и k (1 ≤ n ≤ 104,
1 ≤ m ≤ 105, 1 ≤ k ≤ 105).
Формат выходного файла
В выходном файле должно содержаться одно целое число — минимальное
количество значков, которое требуется подготовить.
Пример входных и выходных данных
|
Входные данные
|
Выходные данные
|
|
3 4 2
|
9
|
Пояснения к примеру
В приведенном примере необходимо подготовить 6 красных и 3 белых
значка.
