CF2248E Excuse for Breaks

给定三个整数 $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,\ldots,1]$ （全 1）数组。也就是说，$I(a)$ 由 $|a|$ 个 1 组成。 请判断是否存在某个二进制数组 $a$，使得 $f(a) > 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$）。 接下来的 $m$ 行每行包含两个整数 $p_i$ 和 $r_i$（$1 \le p_i \le n$，$1 \le r_i \le 10^9$）。 数组 $p$ 严格递增。 保证所有测试用例中 $m$ 之和不超过 $2000$。

对于每组测试用例，如果存在满足条件的二进制数组 $a$，输出 "YES"；否则输出 "NO"。 输出大小写均可。例如，"yEs", "yes", "Yes" 和 "YES" 都会被识别为肯定的结果。

在第一个测试用例中，可以选择 $a = [1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1]$。 该数组 $a$ 共包含 $16$ 个 1，因此 $d$ 的总贡献为 $16 \times 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 \times 3 + 5 + 9 + 1 + 3 = 36$。因此 $f(I(a)) = 3 \times 36 = 108$。由于 $f(a) > f(I(a))$，答案为 "YES"。 第二个测试用例中不存在满足条件的数组 $a$，因此答案为 "NO"。 由 ChatGPT 5 翻译