Задача №113584. Опасность ожирения
Мислав любит бывать на природе, особенно в лесу. Мислав решил провести день в лесу и, так как он очень практичен, он решил не брать еду с собой. Мислав следит за фигурой, поэтому он собирается съесть не более C килограмм еды.
У него есть возможность есть грибы, которые он находит во время прогулки. Все грибы, которые ему встречаются, различны, и он собирается съесть как можно больше различных грибов, но не превысить свою норму. Мислав действует так: он идет по лесу и в любой момент может начать действовать по следующему алгоритму. Если он может съесть гриб и не переесть, то он ест его, иначе – проходит мимо.
Вам дан массив из N весов грибов в том порядке, в котором Мислав находит их. Определите, сколько грибов он может съесть.
Первая строка содержит два целых числа N и C ( 1 ≤ N ≤ 1000 , 1 ≤ C ≤ 10 6 ).
Вторая строка содержит N целых чисел w i ( 1 ≤ w i ≤ 1000 ), обозначающих веса грибов.
Выведите одно число – максимальное количество грибов, которое может съесть Мислав, чтобы не ожиреть.
В первом примере если он начнет есть с первого гриба, то он съест 3 гриба (3, 1, 1). Если он начнет со второго, то он сможет съесть 4 гриба (1, 2, 1, 1).
5 5 3 1 2 1 1
4
7 5 1 5 4 3 2 1 1
3