Школьный этап олимпиады 2018, 7-8 кл.

Задача C. Парашютное шоу ≡

задачи
детали
видимые пробелы
простые формулы
широкий текст
редактор

Автор:	А. Щуров	Ограничение времени:	1 сек
Входной файл:	input.txt	Ограничение памяти:	512 Мб
Выходной файл:	output.txt
Максимальный балл:	100

Условие

В распоряжении комитета по организации праздников имеется n самолётов и p парашютистов. Необходимо устроить парашютное шоу с определенными требованиями:

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

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

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

Кстати, самолёты ограничены по вместимости. Столько проблем у комитета по праздникам!

Сколько парашютистов останется на земле?

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

В первой строке входные данные содержат целые числа p, g и n — общее количество парашютистов, размер выпрыгивающей группы и количество самолетов. Во второй строке — n целых чисел a_i, где a_i равно максимальной вместимости i-го самолета.

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

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

Ограничения

1 ≤ p, g, a_i ≤ 10⁵

1 ≤ n ≤ 100

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

№	Входной файл (`input.txt`)	Выходной файл (`output.txt`)
1	`1000 10 10 100 100 100 100 100 100 100 100 100 100`	`0`
2	`100 10 8 8 9 10 11 12 13 14 15`	`100`
3	`100 4 8 8 9 10 11 12 13 14 15`	`36`