Monopoly
Национална Олимпиада по Информатика 2017, Кръг 3
Time Limit: 0.3s, Memory Limit: 64MiB
След създаването на увеселителния парк, Ели получи крупна сума пари, която сега иска да инвестира. Тя е решила да вложи финансите си в закупуването на поредица от съседни магазини по главната улица на града, в който живее.

За придобиването на част от магазините момичето ще трябва да даде пари, но за други, които от години са на загуба, тя даже може да получи пари, само и само собствениците им да се отърват от тях. Така, ако по продължението на централната улица има N магазина, можем да ги представим чрез последователност от цели (положителни и отрицателни) числа A1, A2, ..., AN – количеството пари, което Ели трябва да даде за придобиването на всеки от тях.

Сега момичето се чуди колко най-много последователни магазини може да закупи, ако има възможност да даде не повече от M лева.
Вход
На първия ред на стандартния вход ще бъдат зададени целите числа N и M – съответно броя на всички магазини на централната улица и бюджета, с който разполага Ели. На втория ред ще бъдат зададени N цели числа A1, A2, ..., AN – цената, която момичето трябва да заплати (или получи, ако е отрицателна) за придобиването на всеки от тях. Магазините са дадени в реда, в който се намират по протежението на улицата.
Изход
На единствен ред на стандартния изход изведете две цели числа – съответно най-големия брой последователни магазини, които Ели може да закупи с наличните й пари, и номера (индексирайки от едно) на първия от тях. Ако съществува повече от един валиден индекс, започвайки от който може да се закупи максималната бройка магазини, изведете най-малкия от тях. Гарантирано е, че Ели ще може да закупи поне един магазин.
Ограничения
  • 1 ≤ N ≤ 500,000
  • 1 ≤ M ≤ 1,000,000,000
  • -1,000,000 ≤ Аi ≤ 1,000,000
Примерен Вход Примерен Изход
15 666 101 42 -132 17 404 -13 55 222 89 11 -66 91 -9 21 4 10 2
Ели може да закупи 10 магазина, започвайки от този с индекс 2 (с цена 42). Момичето би заплатило за тях 42 – 132 + 17 + 404 – 13 + 55 + 222 + 89 + 11 – 66 = 629 лева, което е под бюджета й от 666. Забележете, че започвайки от индекс 6 момичето отново може да закупи 10 магазина, при това за по-ниска цена, но от вас се иска да изпечатате най-малкия възможен индекс.
Ако бюджетът й беше само с три лева повече, 669, момичето би могло да купи с един магазин повече (започвайки от индекс 3).
Мрън!