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 v ``` Here, ":=" 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)) $ .

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 $ .

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.

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".