1763B.md (2154B)
1 Source: https://codeforces.com/problemset/problem/1763/B 2 3 B. Incinerate 4 5 time limit per test 6 7 1 second 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 To destroy humanity, The Monster Association sent $n$ monsters to Earth's surface. The $i$-th monster has health $h_i$ and power $p_i$. 22 23 With his last resort attack, True Spiral Incineration Cannon, Genos can deal $k$ damage to all monsters alive. In other words, Genos can reduce the health of all monsters by $k$ (if $k \gt 0$) with a single attack. 24 25 However, after every attack Genos makes, the monsters advance. With their combined efforts, they reduce Genos' attack damage by the power of the $^\dagger$weakest monster $^\ddagger$alive. In other words, the minimum $p_i$ among all currently living monsters is subtracted from the value of $k$ after each attack. 26 27 $^\dagger$The Weakest monster is the one with the least power. 28 29 $^\ddagger$A monster is alive if its health is strictly greater than $0$. 30 31 Will Genos be successful in killing all the monsters? 32 33 Input 34 35 The first line of the input contains a single integer $t$ ($1 \le t \le 100$) — the number of test cases. The description of test cases follows. 36 37 The first line of each test case contains two integers, $n$ and $k$ ($1 \le n, k \le 10^5$) — the number of monsters and Genos' initial attack damage. Then two lines follow, each containing $n$ integers describing the arrays $h$ and $p$ ($1 \le h_i, p_i \le 10^9$). 38 39 It's guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$. 40 41 Output 42 43 For each test case, print the answer — "YES" (without quotes) if Genos could kill all monsters and "NO" otherwise. 44 45 Example 46 47 Input 48 49 ``` 50 3 51 52 6 7 53 54 18 5 13 9 10 1 55 56 2 7 2 1 2 6 57 58 3 4 59 60 5 5 5 61 62 4 4 4 63 64 3 2 65 66 2 1 3 67 68 1 1 1 69 ``` 70 71 Output 72 73 ``` 74 YES 75 NO 76 YES 77 ``` 78 79 Note 80 81 In the first example, after Genos' first attack, $h$ and $k$ will update to: 82 83 * $h: [11,0,6,2,3,0]$ 84 * $k: 7-1 = 6$ 85 86 After second attack: 87 88 * $h: [5,0,0,0,0,0]$ 89 * $k: 6-2 = 4$ 90 91 After third attack: 92 93 * $h: [1,0,0,0,0,0]$ 94 * $k: 4-2 = 2$ 95 96 After fourth attack: 97 98 * $h: [0,0,0,0,0,0]$ 99 100 As Genos could kill all monsters, the answer is YES.