Финалистами соревнований «Russian Code Cup» в 2214 году будут участники, ставшие победителями в одном из отборочных раундов.
Отборочные раунды делятся на основные и дополнительные. Каждый из основных отборочных раундов должен состоять из c задач, а победителями раунда считаются n человек, занявшие первые места в этом раунде. Каждый из дополнительных отборочных раундов состоит из d задач. Победителем дополнительного раунда становится один человек. Кроме этого, на финал без конкурса приглашаются k победителей финалов прошлых лет.
В результате всех отборочных раундов в финал должно пройти не менее n·m человек. Каким образом нужно организовать отборочные раунды, чтобы в результате всех отборочных раундов в финал прошли не менее n·m человек, а при этом суммарное количество использованных в раундах задач было как можно меньше?
Выходные данные
В первой строке выведите единственное целое число — минимальное количество задач, которое нужно подготовить членам жюри.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
1 10
7 2
1
|
2
|
|
2
|
2 2
2 1
2
|
0
|