Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Алгоритмы
Курсы ККДП
Дистрибутивы
Ссылки

HotLog


 

Симпатичные таблицы

(Время: 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.TXTOUTPUT.TXT
12 2
2 2
1 2
1 -1
-1 -1
3

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

[Обсуждение] [Все попытки] [Лучшие попытки]

Красноярский краевой Дворец пионеров, (c)2006 - 2017, ICQ: 151483



индивидуальные экскурсии в праге