MATHEXAM - Finishing Your Math Exam

You procrastinated studying too long on studying for your maths exam. Now that you're there, you don't even know if you can finish the exam on time!

Luckily you have noticed that the examiners also procrastinated on making the exam, many of the questions are really similar! There are n questions labelled 1 through n, (1, 2, 3 ... n).

You've listed down all the pairs of questions which you think are "similar" (and you're extremely good at evaluating them, so good you haven't missed a single pair).

If one question is similar to another question then they have the same type. The first time you do a question of some type it will take you x seconds to figure out the method of solving it, then for all future questions of that type, it will take only y seconds to copy what you did previously.

All questions have exactly one type.

Quickly! There are only T seconds left in the exam, given all the pairs of similar questions, determine whether or not you can finish on time (in less than or equal to T.

Input

Your first line will contain four space separated integers N, x, y and T.

Your second line will contain a single integer M representing the number of pairs you have listed down.

Your next M lines will contain 2 integers each, representing a pair of similar questions.

1 <= N <= 10,000

1 <= x <= 100,000

1 <= y <= 100,000

1 <= T <= 1,000,000,000

1 <= M <= 100,000

Output

Output YES if you can complete all questions within the time limit, otherwise NO

Example

Input 1
6 3 1 10
4
1 2
1 3
4 3
5 6

Output 1
YES
Input 2
6 3 1 9
4
1 2
1 3
4 3
5 6

Output 2
NO

Added by:jslew
Date:2021-11-03
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.