48. Студенты и лекции

В одном известном ВУЗе в Берляндии студенты могут свободно посещать лекции. Фёдор — староста группы из $n$ студентов.

Завтра будет замечательный день, за который должно будет пройти $m$ лекций. Каждый студент внимательно выслушает мнение Фёдора и пойдет только на те лекции, которые он им посоветует. Студент $i$, посетив лекцию $j$, получит $a_{ij}$ удовольствия. Если же студент $i$ не пойдет на лекцию $j$, то он получит $b_{ij}$ удовольствия. Заметим, что удовольствие — это просто целое число, вычисленное на основе характеристик каждого студента.

Очень важно, чтобы на каждую лекцию пришёл хотя бы один студент, иначе лектору будет очень грустно, а Фёдору потом отвечать за всю группу. Как ответственный староста, Фёдор хочет максимизировать суммарное удовольствие, полученное студентами от посещения или непосещения лекций. Старостой быть очень сложно, и поэтому Фёдор обратился к вам за помощью: вычислите максимальное суммарное удовольствие, которое может получить вся группа.

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

В следующих $n$ строках даны удовольствия, которые получат студенты от посещения лекций. В $i$-й строке записаны $m$ целых чисел $a_{ij}$ ($-10^9 \le a_{ij} \le 10^9$) — удовольствие, которое получит $i$-й студент от посещения лекции $j$.

Далее идут $n$ строк, где даны удовольствия, которые получат студенты, если лекции пропустят. В $i$-й строке записаны $m$ целых чисел $b_{ij}$ ($-10^9 \le b_{ij} \le 10^9$) — удовольствие, которое получит $i$-й студент, если пропустит лекцию $j$.

Выведите одно целое число — максимальное суммарное удовольствие группы.