Rogue-like Game
Contest: Kotlin Heroes 5: ICPC Round
Difficulty rating: 2600
Tags: *special, brute force, greedy, two pointers

Marina plays a new rogue-like game. In this game, there are $$$n$$$ different character species and $$$m$$$ different classes. The game is played in runs; for each run, Marina has to select a species and a class for her character. If she selects the $$$i$$$-th species and the $$$j$$$-th class, she will get $$$c_{i, j}$$$ points for this run.

Initially, some species and classes are unlocked, all others are locked. To unlock the $$$i$$$-th species, Marina has to get at least $$$a_i$$$ points in total for previous runs — that is, as soon as her total score for played runs is at least $$$a_i$$$, this species is unlocked. Similarly, to unlock the $$$j$$$-th class, she has to get at least $$$b_j$$$ points in total for previous runs. If $$$a_i = 0$$$ for some $$$i$$$, then this species is unlocked initially (the same applies to classes with $$$b_j = 0$$$).

Marina wants to unlock all species and classes in the minimum number of runs. Before playing the game, she can read exactly one guide on some combination of species and class, and reading a guide will increase the score she gets for all runs with that combination by $$$k$$$ (formally, before playing the game, she can increase exactly one value of $$$c_{i, j}$$$ by $$$k$$$).

What is the minimum number of runs she has to play to unlock all species and classes if she chooses the combination to read a guide on optimally?

Input format:
The first line contains three integers $$$n$$$, $$$m$$$ and $$$k$$$ ($$$1 \le n, m \le 1500$$$; $$$0 \le k \le 10^9$$$).

The second line contains $$$n$$$ integers $$$a_1$$$, $$$a_2$$$, ..., $$$a_n$$$ ($$$0 = a_1 \le a_2 \le \dots \le a_n \le 10^{12}$$$), where $$$a_i$$$ is the number of points required to unlock the $$$i$$$-th species (or $$$0$$$, if it is unlocked initially). Note that $$$a_1 = 0$$$, and these values are non-descending.

The third line contains $$$m$$$ integers $$$b_1$$$, $$$b_2$$$, ..., $$$b_m$$$ ($$$0 = b_1 \le b_2 \le \dots \le b_m \le 10^{12}$$$), where $$$b_i$$$ is the number of points required to unlock the $$$i$$$-th class (or $$$0$$$, if it is unlocked initially). Note that $$$b_1 = 0$$$, and these values are non-descending.

Then $$$n$$$ lines follow, each of them contains $$$m$$$ integers. The $$$j$$$-th integer in the $$$i$$$-th line is $$$c_{i, j}$$$ ($$$1 \le c_{i, j} \le 10^9$$$) — the score Marina gets for a run with the $$$i$$$-th species and the $$$j$$$-th class.

Output format:
Print one integer — the minimum number of runs Marina has to play to unlock all species and all classes if she can read exactly one guide before playing the game.

Constraints:
Time limit: 4.0 s
Memory limit: 256.0 MB

Note:
The explanation for the first test:

1. Marina reads a guide on the combination of the $$$1$$$-st species and the $$$2$$$-nd class. Thus, $$$c_{1, 2}$$$ becomes $$$7$$$. Initially, only the $$$1$$$-st species and the $$$1$$$-st class are unlocked.
2. Marina plays a run with the $$$1$$$-st species and the $$$1$$$-st class. Her score becomes $$$2$$$, and she unlocks the $$$2$$$-nd class.
3. Marina plays a run with the $$$1$$$-st species and the $$$2$$$-nd class. Her score becomes $$$9$$$, and she unlocks everything except the $$$4$$$-th class.
4. Marina plays a run with the $$$3$$$-rd species and the $$$3$$$-rd class. Her score becomes $$$11$$$, and she unlocks the $$$4$$$-th class. She has unlocked everything in $$$3$$$ runs.

Note that this way to unlock everything is not the only one.

The explanation for the second test:

1. Marina reads a guide on the combination of the $$$2$$$-nd species and the $$$1$$$-st class. Thus, $$$c_{2, 1}$$$ becomes $$$6$$$. Initially, only the $$$1$$$-st species and the $$$1$$$-st class are unlocked.
2. Marina plays a run with the $$$1$$$-st species and the $$$1$$$-st class. Her score becomes $$$3$$$, and she unlocks the $$$2$$$-nd species and the $$$2$$$-nd class.
3. Marina plays a run with the $$$2$$$-nd species and the $$$1$$$-st class. Her score becomes $$$9$$$, and she unlocks the $$$3$$$-rd species and the $$$4$$$-th species. She has unlocked everything in $$$2$$$ runs.

As in the $$$1$$$-st example, this is not the only way to unlock everything in $$$2$$$ runs.

Example input:
3 4 2
0 5 7
0 2 6 10
2 5 5 2
5 3 4 4
3 4 2 4

Example output:
3

Example input:
4 2 1
0 3 9 9
0 2
3 3
5 1
1 3
2 3

Example output:
2

Editorial:
While Marina is playing the game, there will be at most $$$n + m$$$ events when she unlocks something. Let's sort all unlockables by the required score.
After Marina has unlocked something, it is quite obvious that she has to play runs with the best combination of species and class she has already unlocked, until she unlocks something else. Since the number of unlockables is at most $$$n + m$$$, Marina needs to consider only at most $$$n + m$$$ different combinations — only the best combinations available between two "unlocking" events are needed.
So, the solution consists of two parts:
• find at most $$$n + m$$$ combinations we need to consider (these are the best combinations before each "unlocking" event);
• then iterate on one of these combinations that we will boost by reading a guide, and solve the problem with $$$n + m$$$ combinations, one of which is already boosted, greedily in $$$O(n + m)$$$ or $$$O((n + m) \log (n + m))$$$.
The complexity of the model solution is $$$O((n + m)^2 \log (n + m))$$$.