F. Сундуки и ключи
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Алиса и Боб играют в игру. У Алисы есть $$$n$$$ сундуков с сокровищами (в $$$i$$$-м лежит $$$a_i$$$ монет) и $$$m$$$ ключей ($$$j$$$-й из которых она может продать Бобу за $$$b_j$$$ монет).

Сначала Алиса вешает некоторые замки на сундуки. Есть $$$m$$$ типов замков, замок $$$j$$$-го типа можно открыть только $$$j$$$-м ключом. Чтобы повесить замок типа $$$j$$$ на $$$i$$$-й сундук, Алиса должна заплатить $$$c_{i,j}$$$ долларов. Алиса может повесить произвольное количество различных замков на каждый сундук (возможно, ноль).

Затем Боб покупает у Алисы несколько ключей (возможно, ноль или все) и открывает все сундуки, которые он может открыть (он может открыть сундук, если у него есть ключи от всех замков на этом сундуке). Прибыль Боба — это разность между суммарным количеством монет в открытых сундуках и суммарным количеством монет, которые он тратит на покупку ключей у Алисы. Если прибыль Боба строго положительная (больше ноля), то он выигрывает игру. Иначе Алиса выигрывает игру.

Алиса хочет повесить замки на некоторые сундуки так, чтобы она выиграла игру вне зависимости от ключей, которые Боб купит (Боб не может получить положительную прибыль). Разумеется, она хочет потратить как можно меньше долларов на покупку замков. Помогите ей определить, может ли она выиграть игру, а если может, то сколько долларов ей придется потратить на замки.

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

В первой строке записаны два целых числа $$$n$$$ and $$$m$$$ ($$$1 \le n, m \le 6$$$) — количество сундуков и количество ключей, соответственно.

Во второй строке записаны $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 4$$$), где $$$a_i$$$ — это количество монет в $$$i$$$-м сундуке.

В третьей строке записаны $$$m$$$ целых чисел $$$b_1, b_2, \dots, b_m$$$ ($$$1 \le b_j \le 4$$$), где $$$b_j$$$ — это количество монет, которые Боб тратит на покупку $$$j$$$-го ключа у Алисы.

Затем следуют $$$n$$$ строк. В $$$i$$$-й строке записаны $$$m$$$ целых чисел $$$c_{i,1}, c_{i,2}, \dots, c_{i,m}$$$ ($$$1 \le c_{i,j} \le 10^7$$$), где $$$c_{i,j}$$$ — это количество долларов, которые Алиса тратит на покупку замка $$$j$$$-го типа на $$$i$$$-й сундук.

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

Если Алиса не может гарантированно выиграть (как бы она ни выбирала замки, Боб всегда сможет получить положительную прибыль), то выведите $$$-1$$$.

Иначе выведите одно целое число — минимальное количество долларов, которые необходимо потратить Алисе, чтобы выиграть вне зависимости от действий Боба.

Примеры
Входные данные
2 3
3 3
1 1 4
10 20 100
20 15 80
Выходные данные
205
Входные данные
2 3
3 3
2 1 4
10 20 100
20 15 80
Выходные данные
110
Входные данные
2 3
3 4
1 1 4
10 20 100
20 15 80
Выходные данные
-1
Примечание

В первом примере Алиса должна повесить замки $$$1$$$ и $$$3$$$ типов на первый сундук и замки $$$2$$$ и $$$3$$$ типов на второй сундук.

Во втором примере Алиса должна повесить замки $$$1$$$ и $$$2$$$ типов на первый сундук и замок $$$3$$$ типа на второй сундук.