"If your total score is higher than mine, then I will be with you!"

The vow of youth is like the twinkling of stars in the eyes of a girl full of expectations, twinkling in those distant and blurry memories...

Once again, can you avoid leaving regrets?

Simply put, there are $n$ exams in total. Each exam has a different importance, but the scores for every exam are integers in the range $[0, x]$. For the $i$-th exam, your score and her score are $a_i$ and $b_i$ respectively, and the importance is $c_i$. Out of selfishness, she changed the calculation formula for the total score to $\sum_{i=1}^n d_i \cdot (c_i + k \cdot a_i)$, where $d_i$ is your score in the $i$-th exam: if it is your total score, $d_i = a_i$; if it is her total score, $d_i = b_i$.

Given $\sum_{i=1}^n a_i = m$, is there a distribution of scores such that your final total score is greater than hers?

Input

The first line contains an integer $T$ ($1 \le T \le 2 \cdot 10^5$), representing the number of test cases.

Each test case starts with $n+1$ integers, the first line contains four integers $n, m, k, x$ ($1 \le n, x, k \le 2 \cdot 10^5, 1 \le m \le 10^9$). The next $n$ lines each contain two integers $b_i, c_i$ ($0 \le b_i \le x, 1 \le c_i \le 2 \cdot 10^5$).

It is guaranteed that for all $T$ test cases, $\sum n \le 5 \cdot 10^5$.

Output

For each test case, output a single line containing YES or NO (case-sensitive), indicating whether it is possible for your total score to be greater than hers.

Please note that the calculations during the process may exceed 64-bit integers.

Examples

Input 1

2
2 10 1 9
8 2
7 3
2 10 1 8
8 2
7 3

Output 1

YES
NO

Note

For the first test case, if the scores for the two exams are 1 and 9, then your total score is $1 \times 3 + 9 \times 12 = 111$, and her total score is $8 \times 3 + 7 \times 12 = 108$. Your total score can be greater than hers.