← 返回题目列表

Codeforces · 887/D

D. 收视率和真人秀

中文机器翻译题面 查看原题

顶级模特的生活主要有两类事件:时装秀和写真拍摄。参加任何这些活动都会影响相应顶级模特的评级。每次拍摄照片后,模特的评分会增加a,而每次时装秀后,模特的评分会减少b(现在设计师做了太多的实验)。此外,有时顶级模特也会参加脱口秀节目。参加脱口秀后模特变得更受欢迎,拍摄照片后的评分上升为c,时装秀后的评分下降为d。

伊莎贝拉想要参加脱口秀节目,但她希望以这样的方式进行,让她的评分永远不会变成负数。帮助她找到合适的时机参加脱口秀。

假设模特的职业生涯从时刻 0 开始。在那一刻,伊莎贝拉的评分等于开始。如果脱口秀发生在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 是初始评级model和len的长度是脱口秀影响的持续时间。

接下来的 n 行给出了事件的描述。每行包含两个整数 ti 和 qi (1 ≤ ti ≤ 109, 0 ≤ q ≤ 1) - 事件发生的时刻以及事件的类型。类型 0 对应于时装秀,类型 1 对应于照片拍摄。

事件按 ti 递增的顺序给出,所有 ti 都不同。

输出

打印一个非负整数 t — 脱口秀开始前以及脱口秀影响期间,使伊莎贝拉的评分为非负值的时刻。如果有多个答案,则打印其中最小的一个。如果没有这样的时刻,则打印 - 1。

示例

输入 #1

5 1 1 1 4 0 5
1 1
2 1
3 1
4 0
5 0

输出 #1

6

输入 #2

1 1 2 1 2 1 2
1 0

输出 #2

-1