Марина играет в новую 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\)).
Каково минимальное количество вылазок, которые она должна сделать, чтобы разблокировать все расы и классы, если она оптимальным образом выберет комбинацию для которой прочитает руководство?
Выходные данные
Выведите одно целое число — минимальное количество вылазок, которые Марина должна сделать, чтобы разблокировать все расы и все классы, если она может прочитать ровно одно руководство перед игрой.
Примечание
В первом примере из условия Марина может действовать следующим образом:
- Марина читает руководство по комбинации \(1\)-й расы и \(2\)-го класса. Таким образом, \(c_{1, 2}\) становится равно \(7\). Первоначально разблокированы только \(1\)-я раса и \(1\)-й класс.
- Марина делает вылазку с \(1\)-й расой и \(1\)-м классом. Количество очков становится \(2\), и она открывает \(2\)-й класс.
- Марина делает вылазку с \(1\)-й расой и \(2\)-м классом. Количество очков становится \(9\), и она открывает все, кроме \(4\)-го класса.
- Марина делает вылазку с \(3\)-й расой и \(3\)-м классом. Количество очков становится \(11\), и она открывает \(4\)-й класс. Она разблокировала все расы и классы за \(3\) вылазки.
Обратите внимание, что этот способ разблокировать все расы и классы не является единственным.
Во втором примере из условия Марина может действовать следующим образом:
- Марина читает руководство по комбинации \(2\)-й расы и \(1\)-го класса. Таким образом, \(c_{2, 1}\) становится равно \(6\). Первоначально разблокированы только \(1\)-я раса и \(1\)-й класс.
- Марина делает вылазку с \(1\)-й расой и \(1\)-м классом. Количество очков становится \(3\), и она открывает \(2\)-ю расу и \(2\)-й класс.
- Марина делает вылазку со \(2\)-й расой и \(1\)-м классом. Количество очков становится \(9\), и она открывает \(3\)-ю и \(4\)-ю расу. Она разблокировала все за \(2\) вылазки.
Как и в \(1\)-м примере, это не единственный способ разблокировать все за \(2\) вылазки.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 4 2
0 5 7
0 2 6 10
2 5 5 2
5 3 4 4
3 4 2 4
|
3
|
|
2
|
4 2 1
0 3 9 9
0 2
3 3
5 1
1 3
2 3
|
2
|
|
3
|
3 3 5
0 8 11
0 0 3
3 1 3
1 2 1
1 1 3
|
2
|