|
Симпатичные таблицы
(Время: 1 сек. Память: 16 Мб Сложность: 75%)
Рассмотрим таблицу размера N×M, в клетках которой стоят целые неотрицательные числа. Скажем, что таблица является симпатичной, если для всех i сумма чисел ее i-ой строки не превышает Ri и для всех j сумма чисел ее j-го столбца не превышает Cj.
Вам задана таблица Z размера N×M (N строк и M столбцов), в некоторых клетках которой уже стоят целые неотрицательные числа. Найдите симпатичную таблицу с максимальной суммой элементов такую, что она совпадает с Z на тех клетках, в которых в Z стоят числа.
Входные данные
Первая строка входного файла INPUT.TXT содержит числа N и M (1 ≤ M, N ≤ 20). Следующая строка содержит N целых неотрицательных чисел - R1, R2, ..., RN. Следующая строка содержит M целых неотрицательных чисел C1, C2, ..., CM. Все числа не превышают 106. Следующие N строк содержат по M целых чисел, которые задают Z. Если на некотором месте в таблице отсутствует число, то на этом месте во входном файле стоит число -1.
Выходные данные
Выведите в выходной файл OUTPUT.TXT выведите целое число - сумму элементов найденной таблицы. Если решение не существует, то выведите единственное число -1.
Пример
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 2 2
2 2
1 2
1 -1
-1 -1
| 3 |
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| |
