Олимпиады по информатике (ХМАО - Югра)

   
 
Югорский НИИ ИТ, Югорский ФМЛ
Логин:   Пароль:    
 
   
 
Новости
О проекте
Регистрация
Гостевая книга
Форум
Архив задач
Состояние системы
Олимпиады
Работа в системе
Рейтинг
Новичкам
Методическое пособие
Дистанционное обучение
Дистрибутивы
Ссылки


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

(Время: 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

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

[Все попытки] [Лучшие попытки]


 
     
Югорский НИИ ИТ, Югорский ФМЛ