Недавно Люба приобрела себе кредитную карту и начала активно ей пользоваться. Рассмотрим отрезок из n подряд идущих дней.

Изначально на кредитной карте Любы находится 0 единиц денежных средств.

В i-й день вечером происходит денежная операция на сумму a_i. Если a_i > 0, то на счёт Любы зачисляется a_i денежных средств. Если a_i < 0, то со счёта списывается a_i денежных средств. Если же a_i = 0, то в этот день проверяется состояние счёта на предмет задолженности.

Люба может прийти в банк в любой из n дней утром и положить дополнительно на счёт какое-либо положительное количество денег. Но из-за лимита она не может допустить, чтобы в какой-либо момент количество денежных средств на карте превышало d.

Может случиться, что количество денег на карте Любы превысит d после какой-либо вечерней транзакции. В этом случае ответ равен «-1».

Люба не хочет превысить этот лимит. Также она не хочет, чтобы в какой-либо из дней проверки (в те дни, когда a_i = 0) на её кредитной карте был отрицательный баланс. Также для Любы дорога до банка занимает очень много времени, поэтому ей нужно узнать минимальное количество дней, когда ей необходимо будет прийти в банк и положить дополнительные деньги на карту, либо узнать, что заданным ограничениям удовлетворить невозможно. Помогите ей с этим!