Rogue-like Game

Description:

Input:

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:

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.

Sample Input:

3 4 2
0 5 7
0 2 6 10
2 5 5 2
5 3 4 4
3 4 2 4

Sample Output:

3

Sample Input:

4 2 1
0 3 9 9
0 2
3 3
5 1
1 3
2 3

Sample Output:

2

Sample Input:

3 3 5
0 8 11
0 0 3
3 1 3
1 2 1
1 1 3

Sample Output:

2

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.