Задача №113074. Проблема сапожника
2 задачи должны быть решены бин. поиском по ответу
2 задачи должны быть решены с помощью метода динамического программирования
В некоей воинской части есть сапожник. Рабочий день сапожника длится \(N\) минут. Заведующий складом оценивает работу сапожника по количеству починенной обуви, независимо от того, насколько сложный ремонт требовался в каждом случае. Дано \(k\) сапог, нуждающихся в починке. Определите какое максимальное количество из них сапожник сможет починить за один рабочий день.
В первой строке вводятся число \(N\) (натуральное, не превышает 1000), и число \(k\) (натуральное, не превышает 500). Затем идет \(k\) чисел – количество минут, которые требуются чтобы починить \(i\)-й сапог (времена – натуральные числа, не превосходят 100).
Выведите единственное число – максимальное количество сапог, которые можно починить за один рабочий день.
В первом примере можно починить либо первый и второй, либо второй и третий сапоги.
10 3 6 2 8
2
3 2 10 20
0
100 4 2 6 7 8
4