0259. Аэропорт

Имя входного файла:	airport.in
Имя выходного файла:	airport.out
Ограничение по времени:	2 s
Ограничение по памяти:	64 megabytes

Студенческая жизнь - крайне увлекательное занятие. Как все мы знаем, в Университете есть очень много различных организаций, клубов, кружков, ансамблей и прочих подобных вещей. Таким образом, каждый студент может полностью реализовать себя в какой-либо области. В том числе и в программировании: в Университете есть клуб, который этими вещами занимается. Так как студенты работают очень усердно, то они достаточно часто попадают на чемпионат мира по программированию. Конечно, чемпионат проводится в разных странах, но почти всегда поездка на мировые соревнования сопряжена с длительными перелетами. Подчас получается так, что лететь приходится сутки, а то и побольше. А иногда ведь еще и рейс задержать могут, и тогда программистам приходится сидеть в аэропорту и ждать. А что можно делать, когда делать нечего? Правильно, решать задачи! Задачи часто берутся из реальных жизненных проблем, а так как сидят программисты в аэропорту, то задачи могут быть и про него.

Итак, в аэропорту T терминалов. На каждый терминал можно поставить какой-то самолет (а можно и не ставить). Самолеты бывают разные, но реально используется некоторое небольшое количество стандартных моделей (пусть это будет M). Самолет, поставленный к терминалу занимает не только этот терминал но может и занять соседние (аэропорт очень старый и на большие лайнеры проектировщики аэропорта не рассчитывали). Соседние места занимают не только крылья лайнера, но и всякие подсобные вещи, вроде заправщиков, трапов и т. д. Будем просто считать, что размер самолета - не один терминал, а несколько. В то же время, самолет всегда занимает одинаковое количество места как слева, так и справа от себя, а устанавливается на тот терминал, который находится в его середине (т. е. размер самолета - нечетное число и если самолет размера 3 установить на терминал #2, он займет терминалы #1, #2 и #3). Кроме того, не любой самолет можно установить на любой терминал. В силу технических неувязок, каждый терминал принимает самолеты только определенных типов. Однако совсем не нужно, чтобы в терминал можно было установить самолет данного типа, если этот самолет устанавливается в соседний терминал, а этот занимает своим крылом. Также, известно, что установка самолета в терминал более комфортна для пассажиров, чем размещение на летном поле, поэтому авиакомпании платят аэропорту, если самолет устанавливается в терминал. Эта сумма зависит от типа самолета, поэтому для каждого типа самолета известно, сколько заплатит компания за установку такого самолета в терминал. Да, кстати, если самолет занимает крыльями соседние терминалы, это значит, что его нельзя устанавливать на какой-то крайний терминал (т.е. самолет размера 3 нельзя поставить в терминал #1). Вас попросили найти максимальную сумму выплат за установку самолетов в терминалы, которую может получить аэропорт.

Формат входного файла

В первой строке входного файла даны 2 числа: T - количество терминалов и M - количество типов самолетов (1 ≤ T ≤ 1000, 1 ≤ M ≤ 10). Далее M строк описывают типы самолетов. В каждой из них записаны 2 числа: размер самолета (в терминалах, нечётное число, не большее 999) и стоимость выплаты за установку самолета такого типа в терминал (не более 10000). Все числа целые. После этого следует T строк по M чисел, разделенных пробелами. Если i-тое число в j-той строке равно 1, то самолет i-того типа можно установить в j-тый терминал, если 0 - нельзя.

Формат выходного файла

Вывести одно число - максимальную сумму, которую можно получить.

Пример:

airport.in	airport.out
5 2 1 10 3 20 0 1 1 0 1 0 0 1 0 1	30

Источник: Первенство первокурсника ПетрГУ. Осень 2006.

Обсудить       Отправить решение