Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official.
×

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ACM-ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

D. Ratings and Reality Shows

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputThere 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·10^{5}, 0 ≤ *start* ≤ 10^{9}, 1 ≤ *a*, *b*, *c*, *d*, *len* ≤ 10^{9}), 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} ≤ 10^{9}, 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.

Examples

Input

5 1 1 1 4 0 5

1 1

2 1

3 1

4 0

5 0

Output

6

Input

1 1 2 1 2 1 2

1 0

Output

-1

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/10/2018 21:59:04 (d2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|