Contest.uni-smr.ac.ru :: соревнования по программированию
Русская версия || English version
Login:
Password:
Забыли пароль?
 пример поиска: Вася Пупкин
 

E. Разрезы

Задачу добавил: alef

Успешно сдано решений: 26

Разрезы
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Составители расписания успешно справились со своей задачей: каждая группа оказалась в подходящей аудитории. Но одну важную деталь они учесть не смогли. Обучение работе с онлайн-платформой отнимает много сил, и, когда в обеденный перерыв все слушатели захотели подкрепиться, ни буфеты в здании, ни даже ближайшие кафе не смогли справиться с нагрузкой.

Одна из групп слушателей, состоящая из n человек, решила заказать пиццу. Точнее, много пицц. Изначально слушатели планировали разрезать каждую пиццу на m равных кусков и после этого разделить между собой. Для каждого слушателя известно, сколько таких кусков пиццы он хотел бы получить: слушатель #j хотел бы получить pj таких кусков пиццы.

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

Неонил берёт первую пиццу и отрезает от неё сектор, эквивалентный количеству кусков, которые хотел получить слушатель #1. Затем он отрезает от неё сектор, эквивалентный количеству кусков, которые хотел получить слушатель #2. Так продолжается до тех пор, пока оставшаяся часть пиццы не окажется меньше сектора, желаемого очередным слушателем. В этом случае Неонил отдаст этому слушателю эту оставшуюся часть пиццы, после чего перейдёт к следующей пицце, чтобы добавить столько, сколько этому слушателю не хватает до желаемого количества кусков.

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

Примечание. Считайте, что Неонил всегда делает разрез, ведя нож от центра пиццы к её краю.

Входные данные

В первой строке содержатся целые числа n и m (1 ≤ n ≤ 1000,  2 ≤ m ≤ 1000) — количество слушателей в группе и количество одинаковых кусков, на которое они хотели разрезать каждую пиццу.

Во второй строке содержится n целых чисел p1, p2, ..., pn (1 ≤ pj ≤ 1000,  j = 1, 2, ..., n), pj — количество кусков пиццы, которое пожелал съесть слушатель #j.

Гарантируется, что (суммарное количество кусков пиццы, которое пожелали съесть слушатели, делится на m нацело).

Выходные данные

Выведите единственное целое число — суммарное количество разрезов, которое сделает Неонил.

Пример

Входные данные
7 8
4 5 11 8 3 7 2
Выходные данные
11

Сдать задачу

Задать вопрос жюри по этой задаче