Как решить эту задачу ТопСортом?
ФД знает, что Беси любит есть конфеты. У ФД есть N (1 <= N <= 40,000) Конфет, которые она намерен отдать Беси в течение некоторого количества дней. Каждый день ФД дает Беси выбрать, сколько конфет взять сегодня из списка Nopt (1 <= Nopt <= 50) опций, C_i (1 <= C_i <= N). Она может взять ровно c_i конфет, ни больше, ни меньше.
У ФД имеется также F (1 <= F <= 50) любимых чисел FN_i (1 <= FN_i <= N). Если число конфет в конце дня точно совпадает с одним из этих любимых чисел, ФД добавляет в несъеденные конфеты ровно M (1 <= M <= 100) дополнительных конфет. Если вновь оставшееся число снова любимое, то ФД снова добавляет M конфет и т.д. (до бесконечности, в наилучшем для Беси случае).
Если Беси не может взять конфеты (потому, что их не хватает) и количество оставшихся конфет не является любимым числом ФД, процесс получения конфет завершается.
Беси просит Вас помочь ей взять как можно больше конфет.
Для примера, рассмотрим следующий сценарий: * У ФД есть 10 конфет * Беси может брать либо 3 либо 5 конфет каждый день * ФД даст еще 1 конфету, если осталось 2 либо 4 конфеты Оптимальные действия Беси таковы:
Начальное # Конфет Конфет Бонусные Осталось
День # конфет съеденных Осталось конфеты конфет
1 10 3 7 0 7
2 7 3 4 1 5
3 5 3 2 1 3
4 3 3 0 0 0Всего съедено конфет = 3 + 3 + 3 + 3 = 12.
PROBLEM NAME: candy
INPUT FORMAT:
- Строка 1: четыре разделенных пробелом целых числа: N, Nopt, F, M
- Строки 2..Nopt+1: Строка i+1 содержит одно целое число: C_i
- Строки Nopt+2..Nopt+F+1: Строка i+F+1 содержит одно целое число: FN_i
SAMPLE INPUT (файл candy.in): 10 2 2 1 3 5 4 2
OUTPUT FORMAT: * Строка 1: Одно целое число, обозначающее максимальное количество конфет, которое может съесть Беси, или -1, если она может съесть бесконечное количество конфет.
SAMPLE OUTPUT (файл candy.out): 12
