P1016 Mission 1 - I : On the Way

Difficulty: \(\color{grey}350\)

Problem Background

Radar is now on the way to beat Cui2010.

But as we all know, Cui2010 is not a normal guy ~~(yeah, he's mad and crazy)~~, so the road is not so satisfying for him and us...

Problem Statement

The road is a long line which is \(L\) kilometres long. Radar is currently at the mark \(0\), and because is rainy there and the road is not so flat, there's much water on the road and it form \(m\) ponds. All the ponds have a constant depth and the one on mark \(i\) have a depth of \(d_{i}\).

Radar have his special shoes: one kind is to make him taller with \(a\) metres (that is, to let him available to walk in ponds), and the other kind is to make him light (that is, to make him walk farther with \(b\) steps at a time).

Radar is currently \(n\) metres tall and can go \(1\) step at a time.

Radar can only wear one kind of his special shoes and he can't change to the other kind of shoes when he is on the road.

So, can Radar go to the mark \(L\) from the mark \(0\)?

Input

First \(2\) lines:

\(n\) \(m\) \(L\)
\(a\) \(b\)

And then following \(m\) lines, each line contains two elements:

\(i\) \(d_{i}\)

Here means that at the mark \(i\) there's a pond, and it's depth is \(d_i\).

Output

If Radar can go to the mark \(L\) from the mark \(0\) wearing one of his shoes on the road, print Yes; Otherwise print No.

Samples

Input 1

2 5 10
7 2
1 3
3 6
4 10
6 4
9 1

Output 1

Yes

In this Sample, Radar can go to mark \(L=10\) wearing the \(2^{nd}\) kind of shoes:

• First, go \(2\) steps to mark \(2\).
• Then, go \(3\) steps to mark \(5\).
• Finally, because Radar can stand on every mark of the marks after without being drown, he can obviously go to mark \(L=10\).

Input 2

2 7 11
7 5
1 3
3 6
4 8
5 8
6 5
7 4
10 6

Output 2

Yes

In this Sample, Radar can go to mark \(L=11\) wearing the \(1^{st}\) kind of shoes, and then he can stand on every mark of the road without drown, so he can obviously go to mark \(L=11\).

Input 3

2 7 12
4 2
2 8
3 1
5 2
7 10
8 11
9 12
11 100000

Output 3

No

Constraints

• \(2 \le n \le 10\).
• \(5 \le m \le \left(L\right)\).
• \(2 \le L \le 150\).
• \(1 \le a \le 50\).
• \(1 \le b \le \min\left\{\left\lfloor\dfrac{L}{2}\right\rfloor, 10\right\}\).
• For the \(m\) \(i\)'s, \(1 \le d_{i} < L\).