English · Original
Chinese · Translation
Formal · Original
There are two main kinds of events in the life of top-model: fashion shows and photo shoots. Participating in any of these events affects the rating of appropriate top-model. After each photo shoot model's rating increases by _a_ and after each fashion show decreases by _b_ (designers do too many experiments nowadays). Moreover, sometimes top-models participates in talk shows. After participating in talk show model becomes more popular and increasing of her rating after photo shoots become _c_ and decreasing of her rating after fashion show becomes _d_.
Izabella wants to participate in a talk show, but she wants to do it in such a way that her rating will never become negative. Help her to find a suitable moment for participating in the talk show.
Let's assume that model's career begins in moment 0. At that moment Izabella's rating was equal to _start_. If talk show happens in moment _t_ if will affect all events in model's life in interval of time \[_t_.._t_ + _len_) (including _t_ and not including _t_ + _len_), where _len_ is duration of influence.
Izabella wants to participate in a talk show, but she wants to do it in such a way that her rating will not become become negative before talk show or during period of influence of talk show. Help her to find a suitable moment for participating in the talk show.
## Input
In first line there are 7 positive integers _n_, _a_, _b_, _c_, _d_, _start_, _len_ (1 ≤ _n_ ≤ 3·105, 0 ≤ _start_ ≤ 109, 1 ≤ _a_, _b_, _c_, _d_, _len_ ≤ 109), where _n_ is a number of fashion shows and photo shoots, _a_, _b_, _c_ and _d_ are rating changes described above, _start_ is an initial rating of model and _len_ is a duration of influence of talk show.
In next _n_ lines descriptions of events are given. Each of those lines contains two integers _t__i_ and _q__i_ (1 ≤ _t__i_ ≤ 109, 0 ≤ _q_ ≤ 1) — moment, in which event happens and type of this event. Type 0 corresponds to the fashion show and type 1 — to photo shoot.
Events are given in order of increasing _t__i_, all _t__i_ are different.
## Output
Print one non-negative integer _t_ — the moment of time in which talk show should happen to make Izabella's rating non-negative before talk show and during period of influence of talk show. If there are multiple answers print smallest of them. If there are no such moments, print - 1.
[samples]
顶级模特生活中主要有两种事件：时装秀和拍照。参与其中任何一种事件都会影响模特的评分。每次拍照后，模特的评分增加 $a$；每次时装秀后，评分减少 $b$（如今设计师们做了太多实验）。此外，顶级模特有时会参加脱口秀。参加脱口秀后，模特会变得更受欢迎，使得拍照后的评分增加变为 $c$，时装秀后的评分减少变为 $d$。
Izabella 希望参加一次脱口秀，但她希望选择一个合适的时机，使得她的评分在任何时刻都不会变为负数。请帮助她找到适合参加脱口秀的时刻。
假设模特的职业生涯从时刻 0 开始，此时 Izabella 的评分为 $start$。如果脱口秀发生在时刻 $t$，则它将影响模型在时间区间 $[t..t + len)$（包含 $t$，不包含 $t + len$）内的所有事件，其中 $len$ 是影响的持续时间。
Izabella 希望参加一次脱口秀，但她希望选择一个合适的时机，使得在脱口秀之前以及脱口秀影响期间，她的评分始终保持非负。请帮助她找到适合参加脱口秀的时刻。
第一行包含 7 个正整数 $n$, $a$, $b$, $c$, $d$, $start$, $len$（$1 ≤ n ≤ 3·10^5$, $0 ≤ start ≤ 10^9$, $1 ≤ a, b, c, d, len ≤ 10^9$），其中 $n$ 是时装秀和拍照的总次数，$a$, $b$, $c$, $d$ 是上述描述的评分变化量，$start$ 是模特的初始评分，$len$ 是脱口秀影响的持续时间。
接下来 $n$ 行描述了事件。每行包含两个整数 $t_i$ 和 $q_i$（$1 ≤ t_i ≤ 10^9$, $0 ≤ q_i ≤ 1$）——事件发生的时刻及其类型。类型 0 表示时装秀，类型 1 表示拍照。
事件按 $t_i$ 递增顺序给出，所有 $t_i$ 互不相同。
请输出一个非负整数 $t$——脱口秀应发生的时刻，使得 Izabella 在脱口秀之前以及影响期间的评分始终非负。若有多个答案，请输出最小的那个；若不存在这样的时刻，请输出 $-1$。
## Input
第一行包含 7 个正整数 $n$, $a$, $b$, $c$, $d$, $start$, $len$（$1 ≤ n ≤ 3·10^5$, $0 ≤ start ≤ 10^9$, $1 ≤ a, b, c, d, len ≤ 10^9$），其中 $n$ 是时装秀和拍照的总次数，$a$, $b$, $c$, $d$ 是上述描述的评分变化量，$start$ 是模特的初始评分，$len$ 是脱口秀影响的持续时间。接下来 $n$ 行描述了事件。每行包含两个整数 $t_i$ 和 $q_i$（$1 ≤ t_i ≤ 10^9$, $0 ≤ q_i ≤ 1$）——事件发生的时刻及其类型。类型 0 表示时装秀，类型 1 表示拍照。事件按 $t_i$ 递增顺序给出，所有 $t_i$ 互不相同。
## Output
请输出一个非负整数 $t$——脱口秀应发生的时刻，使得 Izabella 在脱口秀之前以及影响期间的评分始终非负。若有多个答案，请输出最小的那个；若不存在这样的时刻，请输出 $-1$。
[samples]
Let $ n $, $ a $, $ b $, $ c $, $ d $, $ s $, $ \ell $ be given positive integers with $ s \geq 0 $, and let $ E = \{(t_i, q_i)\}_{i=1}^n $ be a sequence of events, where $ t_i \in \mathbb{Z}^+ $, $ q_i \in \{0,1\} $, $ t_1 < t_2 < \dots < t_n $, with $ q_i = 0 $ denoting a fashion show and $ q_i = 1 $ a photo shoot.
Define the rating function $ R: \mathbb{R}_{\geq 0} \to \mathbb{Z} $ as follows:
- For $ \tau < t $, $ R(\tau) = s + \sum_{\substack{j: t_j \leq \tau \\ q_j = 1}} a - \sum_{\substack{j: t_j \leq \tau \\ q_j = 0}} b $
- For $ t \leq \tau < t + \ell $, $ R(\tau) = s + \sum_{\substack{j: t_j < t \\ q_j = 1}} a - \sum_{\substack{j: t_j < t \\ q_j = 0}} b + \sum_{\substack{j: t \leq t_j < t+\ell \\ q_j = 1}} c - \sum_{\substack{j: t \leq t_j < t+\ell \\ q_j = 0}} d $
- For $ \tau \geq t + \ell $, $ R(\tau) = s + \sum_{\substack{j: t_j < t \\ q_j = 1}} a - \sum_{\substack{j: t_j < t \\ q_j = 0}} b + \sum_{\substack{j: t \leq t_j < t+\ell \\ q_j = 1}} c - \sum_{\substack{j: t \leq t_j < t+\ell \\ q_j = 0}} d + \sum_{\substack{j: t_j \geq t+\ell \\ q_j = 1}} a - \sum_{\substack{j: t_j \geq t+\ell \\ q_j = 0}} b $
We require $ R(\tau) \geq 0 $ for all $ \tau \in [0, t + \ell) $.
Let $ T = \{0\} \cup \{t_i \mid 1 \leq i \leq n\} \cup \{t_i - \ell \mid 1 \leq i \leq n\} \cap \mathbb{R}_{\geq 0} $.
Find the smallest $ t \in T $ such that:
1. For all $ \tau \in [0, t) $, $ R(\tau) \geq 0 $ under original parameters $ (a, b) $,
2. For all $ \tau \in [t, t + \ell) $, $ R(\tau) \geq 0 $ under modified parameters $ (c, d) $ for events in $ [t, t+\ell) $, and original parameters $ (a, b) $ for events before $ t $.
If no such $ t $ exists, output $ -1 $.
API Response (JSON)
{
"problem": {
"name": "D. Ratings and Reality Shows",
"description": {
"content": "There are two main kinds of events in the life of top-model: fashion shows and photo shoots. Participating in any of these events affects the rating of appropriate top-model. After each photo shoot mo",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 2000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF887D"
},
"statements": [
{
"statement_type": "Markdown",
"content": "There are two main kinds of events in the life of top-model: fashion shows and photo shoots. Participating in any of these events affects the rating of appropriate top-model. After each photo shoot mo...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "顶级模特生活中主要有两种事件：时装秀和拍照。参与其中任何一种事件都会影响模特的评分。每次拍照后，模特的评分增加 $a$；每次时装秀后，评分减少 $b$（如今设计师们做了太多实验）。此外，顶级模特有时会参加脱口秀。参加脱口秀后，模特会变得更受欢迎，使得拍照后的评分增加变为 $c$，时装秀后的评分减少变为 $d$。\n\nIzabella 希望参加一次脱口秀，但她希望选择一个合适的时机，使得她的评分在任何...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "Let $ n $, $ a $, $ b $, $ c $, $ d $, $ s $, $ \\ell $ be given positive integers with $ s \\geq 0 $, and let $ E = \\{(t_i, q_i)\\}_{i=1}^n $ be a sequence of events, where $ t_i \\in \\mathbb{Z}^+ $, $ q...",
"is_translate": false,
"language": "Formal"
}
]
}