Задача D. Ролевая игра ≡

Условие

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

Для обозначения уровня планируется использовать специальные значки двух цветов. Белый значок обозначает один уровень, а красный значок — K уровней. Игрок, изображающий персонажа с уровнем X, должен иметь A белых значков и B красных значков, чтобы сумма (A + B × K) была равна X. При этом персонажу не разрешается иметь более чем (K − 1) белых значков.

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

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

Пояснения к примеру

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

Формат входного файла

Входной файл содержит три целых числа: N, M, K

Формат выходного файла

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

Ограничения

1 ≤ N ≤ 10⁴

1 ≤ M, K ≤ 10⁵

Примеры тестов

3 4 2

9