Жизнь топ-модели крутится вокруг событий двух типов – показы мод и фотосессии. Участие в любом из событий влияет на рейтинг участвующей модели. После каждой фотосессии рейтинг модели увеличивается на a, а после каждого показа мод уменьшается на b (дизайнеры в последнее время слишком много экспериментируют). Также в жизни модели иногда бывают ток-шоу. После участия в ток-шоу модель становится обсуждаемой, и увеличение рейтинга от фотосессии становится равным c, а уменьшение рейтинга от показа мод становится равным d.
Будем считать, что карьера модели начинается в момент времени 0. В этот момент рейтинг Изабеллы был start. Если участие в ток-шоу произошло в момент времени t, то под его влияние попадают события, чьи времена попадают в интервал [t..t + len) (включая t, не включая t + len), где len — продолжительность влияния.
Изабелла хочет поучаствовать в ток-шоу, но при этом так, чтобы от момента начала её карьеры до конца влияния ток-шоу её рейтинг никогда не стал отрицательным. Помогите ей найти подходящий момент времени для участия в ток-шоу.
Выходные данные
Выведите одно неотрицательное целое число t — момент времени, в который Изабелла может поучаствовать в ток-шоу так, чтобы её рейтинг не был отрицательным до начала ток шоу и во время его действия. Если таких моментов несколько, выведите минимальный из них. Если таких моментов не существует, выведите - 1.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5 1 1 1 4 0 5
1 1
2 1
3 1
4 0
5 0
|
6
|
|
2
|
1 1 2 1 2 1 2
1 0
|
-1
|