CF2248E.Excuse for Breaks

You are given three integers $n$, $m$, and $d$, and two arrays $p_1, p_2, \ldots, p_m$ and $r_1, r_2, \ldots, r_m$. The array $p$ is strictly increasing.

For a binary array $a$ of any positive finite length (so $|a|$ need not equal $n$), define its value $f(a)$ using the following pseudocode:

function f(a):    v := 0    c := 0    for i from 1 to length(a):        if a[i] is equal to 1:            v := v + d            c := c + 1        else:            c := 0        for j from 1 to m:            if c is equal to p[j]:                v := v + r[j]        if c is equal to n:            c := 0    return vHere, ":=" denotes the assignment operation.

Let $I(a)$ denote the array $[1,1,\ldots,1]$ of length $|a|$. In other words, $I(a)$ consists of $|a|$ ones.

Determine whether there exists a binary (consisting only of zeros and ones) array $a$ such that $f(a) \gt f(I(a))$.

给你三个整数 $n$、$m$ 和 $d$，以及两个数组 $p_1, p_2, \ldots, p_m$ 和 $r_1, r_2, \ldots, r_m$。数组 $p$ 是严格递增的。

对于任意正有限长度的二进制数组 $a$（即 $|a|$ 不必等于 $n$），其值 $f(a)$ 由以下伪代码定义：

function f(a):    v := 0    c := 0    for i from 1 to length(a):        if a[i] is equal to 1:            v := v + d            c := c + 1        else:            c := 0        for j from 1 to m:            if c is equal to p[j]:                v := v + r[j]        if c is equal to n:            c := 0    return v

其中，“:=” 表示赋值操作。

记 $I(a)$ 为长度为 $|a|$ 的全 $1$ 数组 $[1,1,\ldots,1]$。换言之，$I(a)$ 由 $|a|$ 个 $1$ 组成。

判断是否存在一个二进制（仅含 $0$ 和 $1$）数组 $a$，使得 $f(a) \gt f(I(a))$。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 2000$). The description of the test cases follows.

The first line of each test case contains three integers $n$, $m$, and $d$ ($1 \le n \le 10^9$, $0 \le m \le 2000$, $0 \le d \le 10^9$).

The $i$-th of the next $m$ lines contains two integers $p_i$ and $r_i$ ($1 \le p_i \le n$, $1 \le r_i \le 10^9$).

The array $p$ is strictly increasing.

It is guaranteed that the sum of $m$ over all test cases does not exceed $2000$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $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$）。

接下来的 $m$ 行中，第 $i$ 行包含两个整数 $p_i$ 和 $r_i$（$1 \le p_i \le n$，$1 \le r_i \le 10^9$）。

数组 $p$ 严格递增。

保证所有测试用例中 $m$ 的总和不超过 $2000$。

For each test case, output "YES" if such a binary array $a$ exists, and "NO" otherwise.

You can output the answer in any case (upper or lower). For example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as positive responses.

对于每个测试用例，如果存在满足条件的二进制数组 $a$，则输出 "YES"；否则输出 "NO"。

你可以以任意大小写形式输出答案（大写或小写均可）。例如，字符串 "yEs"、"yes"、"Yes" 和 "YES" 均将被识别为肯定回答。

In the first test case, you can choose $a = [1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1]$.

The array $a$ contains $16$ ones, so the total contribution of $d$ is $16 \cdot 3 = 48$. Its runs of consecutive ones have lengths $9$, $4$, and $3$. The corresponding total rewards are $32$, $15$, and $14$, respectively. Therefore, $f(a) = 48 + 32 + 15 + 14 = 109$.

Moreover, $I(a)$ consists of $18$ ones. During the computation of $f(I(a))$, they form three complete blocks of $6$ ones, and each block contributes $6 \cdot 3 + 5 + 9 + 1 + 3 = 36$. Thus, $f(I(a)) = 3 \cdot 36 = 108$. Since $f(a) \gt f(I(a))$, the answer is "YES".

In the second test case, no binary array $a$ satisfies $f(a) \gt f(I(a))$, so the answer is "NO".

在第一个测试用例中，你可以选择 $a = [1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1]$。

数组 $a$ 包含 $16$ 个 $1$，因此 $d$ 的总贡献为 $16 \cdot 3 = 48$。其连续的 $1$ 段（即“游程”）长度分别为 $9$、$4$ 和 $3$。对应获得的总奖励分别为 $32$、$15$ 和 $14$。因此，$f(a) = 48 + 32 + 15 + 14 = 109$。

此外，$I(a)$ 由 $18$ 个 $1$ 组成。在计算 $f(I(a))$ 时，它们构成三个完整的、每块含 $6$ 个 $1$ 的块，且每块的贡献为 $6 \cdot 3 + 5 + 9 + 1 + 3 = 36$。因此，$f(I(a)) = 3 \cdot 36 = 108$。由于 $f(a) \gt f(I(a))$，答案为 “YES”。

在第二个测试用例中，不存在满足 $f(a) \gt f(I(a))$ 的二进制数组 $a$，因此答案为 “NO”。