Недавно Люба приобрела себе кредитную карту и начала активно ей пользоваться. Рассмотрим отрезок из n подряд идущих дней.
Изначально на кредитной карте Любы находится 0 единиц денежных средств.
В i-й день вечером происходит денежная операция на сумму ai. Если ai > 0, то на счёт Любы зачисляется ai денежных средств. Если ai < 0, то со счёта списывается ai денежных средств. Если же ai = 0, то в этот день проверяется состояние счёта на предмет задолженности.
Люба может прийти в банк в любой из n дней утром и положить дополнительно на счёт какое-либо положительное количество денег. Но из-за лимита она не может допустить, чтобы в какой-либо момент количество денежных средств на карте превышало d.
Может случиться, что количество денег на карте Любы превысит d после какой-либо вечерней транзакции. В этом случае ответ равен «-1».
Люба не хочет превысить этот лимит. Также она не хочет, чтобы в какой-либо из дней проверки (в те дни, когда ai = 0) на её кредитной карте был отрицательный баланс. Также для Любы дорога до банка занимает очень много времени, поэтому ей нужно узнать минимальное количество дней, когда ей необходимо будет прийти в банк и положить дополнительные деньги на карту, либо узнать, что заданным ограничениям удовлетворить невозможно. Помогите ей с этим!
Выходные данные
В единственной строке выведите «-1» (без кавычек), если Люба не сможет класть деньги на карту так, чтобы удовлетворить всем вышеописанным ограничениям, либо же минимальное количество дней, необходимое для этого.