Столовая и звонок

На перемене в школьной столовой выстроилась очередь из n учеников. Все подошли одновременно и стоят строго в заданном порядке.

На кассе обслуживают по одному и без перерывов: сначала первого, потом второго и т. д. На обслуживание i-го ученика нужно a[i] секунд.

Звонок на урок прозвенит ровно через B секунд после начала перемены. Успевшими считаются только те, чьё обслуживание полностью закончилось не позже звонка.

Нужно узнать: 1) сколько учеников успеют полностью обслужиться; 2) сколько секунд останется до звонка после того, как обслужат последнего из успевших (если не успеет никто — это просто B).

Формат ввода

В первой строке два целых числа n и B. Во второй строке n целых чисел a[1], a[2], ..., a[n].

Формат вывода

Выведите два целых числа: k и r, где k — число учеников, которых успели обслужить полностью, а r — сколько секунд осталось до звонка после обслуживания последнего из них.

Ограничения

• 1 ≤ n ≤ 2000
• 1 ≤ B ≤ 1000
• 1 ≤ a[i] ≤ 1000

Пример

Ввод:

5 12
2 5 4 3 1

Вывод:

3 1

В этом примере успеют обслужить первых трёх (2+5+4=11 секунд), после этого до звонка останется 12−11=1 секунда.

Ключевое наблюдение: порядок фиксирован, касса работает без пауз, значит момент окончания обслуживания каждого ученика — это просто сумма a[1] + ... + a[i]. Успеют ровно первые k учеников, для которых эта сумма не превышает B.

Здесь подходит простая симуляция (пошаговый подсчёт), потому что каждое решение «успеет/не успеет» зависит только от уже накопленного времени и длительности текущего ученика.

План решения:

• Заведи переменные: t = 0 (сколько секунд уже потрачено) и k = 0 (сколько учеников успели).
• Иди по массиву a слева направо.
• Для очередного x = a[i] проверь: если t + x <= B, то ученик успевает: сделай t += x, k += 1.
• Иначе дальше никто не успеет (они стоят после него), поэтому можно сразу остановиться.
• Остаток времени до звонка после последнего успевшего: r = B - t. Если не успел никто, то t = 0, и формула всё равно даст r = B.

Мини-сниппет проверки:

• if t + x <= B: t += x; k += 1 else: break

Сложность: O(n) по времени, O(1) по памяти.

Частая ошибка: считать успевшими тех, кто «начал обслуживаться до звонка». По условию нужно, чтобы обслуживание полностью закончилось не позже B, поэтому проверка именно t + a[i] <= B.