E. Извинение за перерывы
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам даны три целых числа $$$n$$$, $$$m$$$ и $$$d$$$, а также два массива $$$p_1, p_2, \ldots, p_m$$$ и $$$r_1, r_2, \ldots, r_m$$$. Массив $$$p$$$ является строго возрастающим.

Для бинарного массива $$$a$$$ любой положительной конечной длины (то есть $$$|a|$$$ не обязательно равно $$$n$$$) определим его значение $$$f(a)$$$ с помощью следующего псевдокода:

функция f(a):
    v := 0
    c := 0
    для всех i от 1 до длины a:
        если a[i] равно 1:
            v := v + d
            c := c + 1
        иначе:
            c := 0
        для всех j от 1 до m:
            если c равно p[j]:
                v := v + r[j]
        если c равно n:
            c := 0
    вернуть v
Здесь «:=» обозначает операцию присваивания.

Обозначим через $$$I(a)$$$ массив $$$[1,1,\ldots,1]$$$ длины $$$|a|$$$. Иными словами, $$$I(a)$$$ состоит из $$$|a|$$$ единиц.

Определите, существует ли бинарный (состоящий только из нулей и единиц) массив $$$a$$$ такой, что $$$f(a) \gt f(I(a))$$$.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 2000$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

В первой строке каждого набора входных данных заданы три целых числа $$$n$$$, $$$m$$$ и $$$d$$$ ($$$1 \le n \le 10^9$$$, $$$0 \le m \le 2000$$$, $$$0 \le d \le 10^9$$$).

$$$i$$$-я из следующих $$$m$$$ строк содержит два целых числа $$$p_i$$$ и $$$r_i$$$ ($$$1 \le p_i \le n$$$, $$$1 \le r_i \le 10^9$$$).

Массив $$$p$$$ являестся строго возрастающим.

Гарантируется, что сумма значений $$$m$$$ по всем наборам входных данных не превосходит $$$2000$$$.

Выходные данные

Для каждого набора входных данных выведите «YES», если такой бинарный массив $$$a$$$ существует, и «NO» в противном случае.

Вы можете выводить каждую букву в любом регистре (строчную или заглавную). Например, строки «yEs», «yes», «Yes» и «YES» будут приняты как положительный ответ.

Пример
Входные данные
3
6 4 3
2 5
3 9
4 1
5 3
7 3 5
2 5
4 5
7 10
684492057 3 386217943
367971233 991739271
612599954 429216213
684492056 402931836
Выходные данные
YES
NO
YES
Примечание

В первом наборе входных данных можно выбрать $$$a = [1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1]$$$.

Массив $$$a$$$ содержит $$$16$$$ единиц, поэтому суммарный вклад $$$d$$$ равен $$$16 \cdot 3 = 48$$$. Его серии подряд идущих единиц имеют длины $$$9$$$, $$$4$$$ и $$$3$$$. Соответствующие суммарные награды равны $$$32$$$, $$$15$$$ и $$$14$$$. Следовательно, $$$f(a) = 48 + 32 + 15 + 14 = 109$$$.

Кроме того, $$$I(a)$$$ состоит из $$$18$$$ единиц. Во время вычисления $$$f(I(a))$$$ они образуют три полных блока по $$$6$$$ единиц, и каждый блок вносит $$$6 \cdot 3 + 5 + 9 + 1 + 3 = 36$$$. Таким образом, $$$f(I(a)) = 3 \cdot 36 = 108$$$. Поскольку $$$f(a) \gt f(I(a))$$$, ответ — «YES».

Во втором наборе входных данных не существует бинарного массива $$$a$$$, для которого $$$f(a) \gt f(I(a))$$$, поэтому ответ — «NO».