H. Rogue-like игра
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Марина играет в новую rogue-like игру. В этой игре есть $$$n$$$ различных рас персонажей и $$$m$$$ различных классов. Игра состоит из вылазок; для каждой вылазки Марина должна выбрать расу и класс для своего персонажа. Если она выберет $$$i$$$-ю расу и $$$j$$$-й класс, она получит $$$c_{i, j}$$$ очков за эту сессию.

Изначально некоторые расы и классы разблокированы, все остальные заблокированы. Чтобы разблокировать $$$i$$$-ю расу, Марина должна получить в общей сложности не менее $$$a_i$$$ очков за предыдущие вылазки, то есть, как только ее общее количество очков за сыгранные вылазки составит не менее $$$a_i$$$, эта раса будет разблокирована. Аналогично, чтобы разблокировать $$$j$$$-й класс, она должна получить не менее $$$b_j$$$ очков в общей сложности за предыдущие вылазки. Если $$$a_i = 0$$$ для некоторого $$$i$$$, то эта раса разблокирована изначально (то же самое относится и к классам с $$$b_j = 0$$$).

Марина хочет разблокировать все расы и классы за минимальное количество вылазок. Прежде чем начать играть, она может прочитать ровно одно руководство по некоторой комбинации расы и класса, и чтение руководства увеличит количество очков, которое она получает за каждую вылазку с этой комбинацией на $$$k$$$ (формально, прежде чем начать играть, она может увеличить ровно одно значение $$$c_{i, j}$$$ на $$$k$$$).

Каково минимальное количество вылазок, которые она должна сделать, чтобы разблокировать все расы и классы, если она оптимальным образом выберет комбинацию для которой прочитает руководство?

Входные данные

Первая строка содержит три целых числа $$$n$$$, $$$m$$$ и $$$k$$$ ($$$1 \le n, m \le 1500$$$; $$$0 \le k \le 10^9$$$).

Вторая строка содержит $$$n$$$ целых чисел $$$a_1$$$, $$$a_2$$$, ..., $$$a_n$$$ ($$$0 = a_1 \le a_2 \le \dots \le a_n \le 10^{12}$$$), где $$$a_i$$$ — количество очков, необходимое для разблокировки $$$i$$$-й расы (или $$$0$$$, если она разблокирована изначально). Обратите внимание, что $$$a_1 = 0$$$, и эти значения неубывающие.

Третья строка содержит $$$m$$$ целых чисел $$$b_1$$$, $$$b_2$$$, ..., $$$b_m$$$ ($$$0 = b_1 \le b_2 \le \dots \le b_m \le 10^{12}$$$), где $$$b_i$$$ — количество очков, необходимое для разблокировки $$$i$$$-го класса (или $$$0$$$, если он разблокирован изначально). Обратите внимание, что $$$b_1 = 0$$$, и эти значения неубывающие.

Далее следуют $$$n$$$ строк, каждая из которых содержит $$$m$$$ целых чисел. $$$j$$$-е целое число в $$$i$$$-й строке равно $$$c_{i, j}$$$ ($$$1 \le c_{i, j} \le 10^9$$$) — количество очков, которое Марина получает за вылазку с $$$i$$$-й расой и $$$j$$$-м классом.

Выходные данные

Выведите одно целое число — минимальное количество вылазок, которые Марина должна сделать, чтобы разблокировать все расы и все классы, если она может прочитать ровно одно руководство перед игрой.

Примеры
Входные данные
3 4 2
0 5 7
0 2 6 10
2 5 5 2
5 3 4 4
3 4 2 4
Выходные данные
3
Входные данные
4 2 1
0 3 9 9
0 2
3 3
5 1
1 3
2 3
Выходные данные
2
Входные данные
3 3 5
0 8 11
0 0 3
3 1 3
1 2 1
1 1 3
Выходные данные
2
Примечание

В первом примере из условия Марина может действовать следующим образом:

  1. Марина читает руководство по комбинации $$$1$$$-й расы и $$$2$$$-го класса. Таким образом, $$$c_{1, 2}$$$ становится равно $$$7$$$. Первоначально разблокированы только $$$1$$$-я раса и $$$1$$$-й класс.
  2. Марина делает вылазку с $$$1$$$-й расой и $$$1$$$-м классом. Количество очков становится $$$2$$$, и она открывает $$$2$$$-й класс.
  3. Марина делает вылазку с $$$1$$$-й расой и $$$2$$$-м классом. Количество очков становится $$$9$$$, и она открывает все, кроме $$$4$$$-го класса.
  4. Марина делает вылазку с $$$3$$$-й расой и $$$3$$$-м классом. Количество очков становится $$$11$$$, и она открывает $$$4$$$-й класс. Она разблокировала все расы и классы за $$$3$$$ вылазки.

Обратите внимание, что этот способ разблокировать все расы и классы не является единственным.

Во втором примере из условия Марина может действовать следующим образом:

  1. Марина читает руководство по комбинации $$$2$$$-й расы и $$$1$$$-го класса. Таким образом, $$$c_{2, 1}$$$ становится равно $$$6$$$. Первоначально разблокированы только $$$1$$$-я раса и $$$1$$$-й класс.
  2. Марина делает вылазку с $$$1$$$-й расой и $$$1$$$-м классом. Количество очков становится $$$3$$$, и она открывает $$$2$$$-ю расу и $$$2$$$-й класс.
  3. Марина делает вылазку со $$$2$$$-й расой и $$$1$$$-м классом. Количество очков становится $$$9$$$, и она открывает $$$3$$$-ю и $$$4$$$-ю расу. Она разблокировала все за $$$2$$$ вылазки.

Как и в $$$1$$$-м примере, это не единственный способ разблокировать все за $$$2$$$ вылазки.