Задача B. Доставка почты ≡

Условие

Почтальон Пётр привёз посылки для жителей 108 дома. В этом доме всего один подъезд, N этажей и отсутствует лифт.

Так совпало, что именно сегодня на каждый этаж необходимо доставить по одной посылке. Почтальон хочет сделать работу как можно быстрее, поэтому берёт всегда как можно больше посылок, но не более чем M штук — тяжелые они, однако.

Пётр не привык выбирать, какие посылки доставлять в первую очередь, поэтому берёт их случайно. Взяв посылки, он доставляет их в порядке возрастания этажей. Например, если почтальон взял посылки для 2, 5 и 10 этажа, то сначала он доставит посылку на 2-й этаж, потом на 5-й, потом на 10-й. После этого он возвращается в свой грузовик за новой партией. И так до тех пор, пока не будут доставлены все посылки.

Подъёмом называется суммарное количество этажей, на которое необходимо подняться, доставляя посылки. Например, если почтальон доставляет посылки на 1 и 3 этажи, а потом на 2, то сначала он поднимется на 1-й этаж, потом поднимется с 1-о этажа на 3-й, потом вернётся в грузовик за посылкой для 2-о этажа и доставит её. Подъём в данном случае будет равен 1 + (3 − 1) + 2 = 5.

Разумеется, от порядка доставки зависит величина подъёма. Пётр хочет узнать минимальное или максимальное возможное значение подъёма.

Требуется написать программу, которая определит минимальное или максимальное возможное значение подъёма, если известны количество этажей в доме и количество посылок, которые почтальон может унести.

Формат входных данных

Первая строка содержит одно целое число N — количество этажей в доме.

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

Третья строка содержит одно целое число P. Если P = 1, то необходимо посчитать минимальное значение подъёма. Иначе P = 2 и необходимо посчитать максимальное значение подъёма.

Формат выходных данных

В единственной строке выведите ответ на задачу.

Ограничения

1 ≤ M ≤ N ≤ 2 ⋅ 10⁹

1 ≤ P ≤ 2

Описание подзадач и системы оценивания

Баллы за каждую подзадачу начисляются только в случае, если все тесты этой подзадачи и необходимых подзадач успешно пройдены.

Проверка каждой подзадачи выполняется до первой ошибки на каком-нибудь тесте этой подзадачи.

По запросу сообщается результат окончательной проверки на каждом тесте.

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

Обратите внимание, что первый и третий примеры относится к первой подзадаче, а второй и четвёртый — к четвёртой.

В первом примере Пётр мог сначала доставить посылки на 2-й и 3-й этажи, а потом на 1-й. Подъём равен 2 + (3 − 2) + 1 = 4.

Во втором примере Пётр мог сначала доставить посылки на 1-й и 2-й этажи, а потом на 3-й. Подъём равен 1 + (2 − 1) + 3 = 5.

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

3
2
1

4

3
2
2

5

7
3
1

12

7
3
2

18