The following languages are only available languages for the problems from the contest

Kotlin Heroes 5: ICPC Round:

- Kotlin 1.4.0

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

The problem statement has recently been changed. View the changes.

×
H. Rogue-like Game

time limit per test

4 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputMarina 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

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.

Examples

Input

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

Output

3

Input

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

Output

2

Input

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

Output

2

Note

The explanation for the first test:

- 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.
- 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.
- 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.
- 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:

- 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.
- 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.
- 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.

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Apr/20/2021 06:52:13 (j1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|