Codeforces Round 444 (Div. 2) |
---|
Закончено |
Жизнь топ-модели крутится вокруг событий двух типов – показы мод и фотосессии. Участие в любом из событий влияет на рейтинг участвующей модели. После каждой фотосессии рейтинг модели увеличивается на a, а после каждого показа мод уменьшается на b (дизайнеры в последнее время слишком много экспериментируют). Также в жизни модели иногда бывают ток-шоу. После участия в ток-шоу модель становится обсуждаемой, и увеличение рейтинга от фотосессии становится равным c, а уменьшение рейтинга от показа мод становится равным d.
Будем считать, что карьера модели начинается в момент времени 0. В этот момент рейтинг Изабеллы был start. Если участие в ток-шоу произошло в момент времени t, то под его влияние попадают события, чьи времена попадают в интервал [t..t + len) (включая t, не включая t + len), где len — продолжительность влияния.
Изабелла хочет поучаствовать в ток-шоу, но при этом так, чтобы от момента начала её карьеры до конца влияния ток-шоу её рейтинг никогда не стал отрицательным. Помогите ей найти подходящий момент времени для участия в ток-шоу.
В первой строке даны 7 целых положительных чисел n, a, b, c, d, start, len (1 ≤ n ≤ 3·105, 0 ≤ start ≤ 109, 1 ≤ a, b, c, d, len ≤ 109), где n – число показов мод и фотосессий, a, b, c и d — изменения рейтинга, описанные выше, start — начальный рейтинг модели, len — длительность влияния ток-шоу.
В следующих n строках содержатся описания событий. Каждая из этих строк содержит по два целых числа ti и qi (1 ≤ ti ≤ 109, 0 ≤ q ≤ 1) — момент времени события и его тип. Тип 0 означает показ мод, а тип 1 – фотосессию.
События во входных данных упорядочены по возрастанию ti, все ti различны.
Выведите одно неотрицательное целое число t — момент времени, в который Изабелла может поучаствовать в ток-шоу так, чтобы её рейтинг не был отрицательным до начала ток шоу и во время его действия. Если таких моментов несколько, выведите минимальный из них. Если таких моментов не существует, выведите - 1.
5 1 1 1 4 0 5
1 1
2 1
3 1
4 0
5 0
6
1 1 2 1 2 1 2
1 0
-1
Название |
---|