1985F.md (2485B)
1 Source: https://codeforces.com/problemset/problem/1985/F 2 3 F. Final Boss 4 5 time limit per test 6 7 2 seconds 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 You are facing the final boss in your favorite video game. The boss enemy has $h$ health. Your character has $n$ attacks. The $i$'th attack deals $a_i$ damage to the boss but has a cooldown of $c_i$ turns, meaning the next time you can use this attack is turn $x + c_i$ if your current turn is $x$. Each turn, you can use all attacks that are not currently on cooldown, all at once. If all attacks are on cooldown, you do nothing for the turn and skip to the next turn. 22 23 Initially, all attacks are not on cooldown. How many turns will you take to beat the boss? The boss is beaten when its health is $0$ or less. 24 25 Input 26 27 The first line contains $t$ ($1 \leq t \leq 10^4$) – the number of test cases. 28 29 The first line of each test case contains two integers $h$ and $n$ ($1 \leq h, n \leq 2 \cdot 10^5$) – the health of the boss and the number of attacks you have. 30 31 The following line of each test case contains $n$ integers $a_1, a_2, ..., a_n$ ($1 \leq a_i \leq 2 \cdot 10^5$) – the damage of your attacks. 32 33 The following line of each test case contains $n$ integers $c_1, c_2, ..., c_n$ ($1 \leq c_i \leq 2 \cdot 10^5$) – the cooldown of your attacks. 34 35 It is guaranteed that the sum of $h$ and $n$ over all test cases does not exceed $2 \cdot 10^5$. 36 37 Output 38 39 For each test case, output an integer, the minimum number of turns required to beat the boss. 40 41 Example 42 43 Input 44 45 ``` 46 8 47 48 3 2 49 50 2 1 51 52 2 1 53 54 5 2 55 56 2 1 57 58 2 1 59 60 50 3 61 62 5 6 7 63 64 5 6 7 65 66 50 3 67 68 2 2 2 69 70 3 3 3 71 72 90000 2 73 74 200000 200000 75 76 1 1 77 78 100000 1 79 80 1 81 82 200000 83 84 6 7 85 86 3 2 3 2 3 1 2 87 88 6 5 9 5 10 7 7 89 90 21 6 91 92 1 1 1 1 1 1 93 94 5 5 8 10 7 6 95 ``` 96 97 Output 98 99 ``` 100 1 101 3 102 15 103 25 104 1 105 19999800001 106 1 107 21 108 ``` 109 110 Note 111 112 For the first test case, you can use attacks $1$ and $2$ on the first turn, dealing $3$ damage in total, and slaying the boss. 113 114 For the second case, you can beat the boss in $3$ turns by using the following attacks: 115 116 Turn $1$: Use attacks $1$ and $2$, dealing $3$ damage to the boss. The boss now has $2$ health left. 117 118 Turn $2$: Use attack $2$, dealing $1$ damage to the boss. The boss now has $1$ health left. 119 120 Turn $3$: Use attack $1$, dealing $2$ damage to the boss. The boss now has $-1$ health left. Since its health is less than or equal to $0$, you beat the boss. 121 122 For the sixth test case: remember to use 64-bit integers as the answer can get large.