P16370 [OOI 2026] Monsters and Swords

Given $n$ monsters arranged in a row, for each monster, two values are known: $h_i$ --- the health of the monster and $r_i$ --- the reward for defeating this monster, expressed in coins. The knight must defeat all the monsters. For fighting the monsters, the knight has $m$ types of swords, and for each type of sword, its characteristics are known: $s_j$ --- the strength of the sword and $c_j$ --- the price of the sword in coins. To purchase a sword with price $c_j$, the knight must have at least $c_j$ coins. After purchasing a sword, the knight's coin count decreases by $c_j$. Initially, the knight has $x$ coins. After purchasing a sword, it can be used no more than $k$ times in battles against the monsters. Any type of sword can be purchased an arbitrary number of times. A sword with strength $s_j$ can kill a monster with health $h_i$ if $s_j \geq h_i$. At any moment, the knight can only possess one sword, meaning that after purchasing a new sword, the old sword can no longer be used (but it can be purchased again in the future). The monsters must be defeated in a fixed order: from the first to the last. It is required to determine whether the knight can do this.

The first line contains four integers $n$, $m$, $k$, and $x$ ($1 \le n, m \le 500\,000$, $1 \le k \le n$, $1 \le x \le 10^9$) --- the number of monsters, the number of sword types, the maximum number of times a sword can be used, and the initial number of coins the knight has. In the following $n$ lines, the descriptions of the monsters are given. In the $i$-th line, there are two integers: $h_i$ and $r_i$ ($1 \le h_i, r_i \le 10^9)$ --- the health of the $i$-th monster and the reward for defeating it. In the next $m$ lines, the characteristics of the swords are described. In the $j$-th line, there are two integers $s_j$ and $c_j$ ($1 \le s_j, c_j \le 10^9)$ --- the strength and price of the $j$-th sword.

Print $\texttt{Yes}$ (without quotes) if the knight can defeat all the monsters, and $\texttt{No}$ (without quotes) otherwise.

### Note In the first example, the knight can first buy the third sword, using it to defeat the first and second monsters. After that, he will have $5 - 1 + 1 + 5 = 10$ coins. This allows him to buy the first sword and defeat the last monster. In the second example, the knight cannot defeat all the monsters because there is no type of sword that can defeat the fifth monster. ### Scoring The tests for this problem consist of 9 groups. Points for each group are awarded only if all tests of the group and all tests of some previous groups are passed. Note that passing the tests from the statement is not required for some groups. Offline testing means that the results of testing your solution on this group will only be available after the competition ends. The final score for each group is equal to the maximum score obtained for this group of tests across all submitted solutions. | Group | Points | Additional constraints | < | < | Required groups | Comment | | :---: | :---: | :---: | :---: | :---: | :---: | :---: | | | | $n$ | $m$ | $k$ | | | | $0$ | $0$ | $--$ | $--$ | $--$ | $--$ | Tests from the statement. | | $1$ | $11$ | $--$ | $--$ | $k=1$ | $--$ | $--$ | | $2$ | $9$ | $n \leq 100$ | $m \leq 100$ | $k=n$ | $--$ | $--$ | | $3$ | $14$ | $n \leq 100\,000$ | $m \leq 3000$ | $k=n$ | $2$ | $--$ | | $4$ | $16$ | $--$ | $--$ | $k=n$ | $2, 3$ | $--$ | | $5$ | $7$ | $n \leq 400$ | $m \leq 400$ | $--$ | $0, 2$ | $--$ | | $6$ | $8$ | $n \leq 3000$ | $m \leq 3000$ | $--$ | $0, 2, 5$ | $--$ | | $7$ | $10$ | $n \leq 150\,000$ | $m \leq 150\,000$ | $--$ | $0, 2, 3, 5, 6$ | $--$ | | $8$ | $12$ | $n \leq 300\,000$ | $m \leq 300\,000$ | $--$ | $0, 2, 3, 5$ -- $7$ | $--$ | | $9$ | $13$ | $--$ | $--$ | $--$ | $0$ -- $8$ | **Offline testing.** |