| Codeforces Beta Round 58 |
|---|
| Закончено |
В результате таинственных экспериментов Пинки и Брейна в Большом Адронном Коллайдере открылись порталы — чёрные дыры — в параллельное измерение, откуда сразу же Вселенское Зло протянуло свои зловещие щупальца. Брейн быстро оценил ситуацию и понял, что, чем больше щупалец выберется на свободу, тем выше его шансы повелевать миром.
Конструкция Коллайдера представляет собой квадратную сетку, свёрнутую в цилиндр, и состоящую из n строк и m столбцов такую, какая показана на рисунке ниже:
В данном примере n = 4, m = 5. Пунктирными линиями обозначены коридоры, которые замыкают каждый столбец в кольцо, то есть соединяют n-ную и 1-ую строки сетки.
В самом левом столбце этой сетки находятся порталы, из которых готовы вылезти щупальца Вселенского Зла. В самом правом столбце расположены выходы из сооружения. Щупальца могут выбраться только через эти выходы. Отрезки, соединяющие узлы этой сетки — это коридоры.
Брейн рад бы выпустить все щупальца, но вот незадача: из порталов может вылезти бесконечное количество щупалец, каждое щупальце обладает бесконечной длиной и некоторой толщиной, а объёмы коридоров, увы, весьма ограничены. Брейн навскидку смог оценить максимальное количество щупалец, которое может пролезть через каждый коридор.
Теперь помогите мышкам определить, какое максимальное количество щупалец Вселенского Зла выберется из Большого Адронного Коллайдера.
В первой строке входного файла дано два целых числа n и m (2 ≤ n ≤ 5, 2 ≤ m ≤ 105) — размеры сетки Большого Адронного Колайдера. В последующих m - 1 строках записано по n чисел: пропускные способности горизонтально расположенных коридоров. В последующих m строках записано по n чисел: пропускные способности вертикально расположенных коридоров. Коридоры описываются слева направо, сверху вниз. Каждый n-ый вертикальный коридор соединяет узлы n-ой и 1-ой строк. Пропускная способность коридора — неотрицательное целое число, не превосходящее 109.
Выведите одно число — количество щупалец Вселенского Зла, которыми будут повелевать Пинки и Брейн.
Пожалуйста, не используйте спецификатор %lld для чтения или записи 64-х битовых чисел на С++. Рекомендуется использовать поток cout (также вы можете использовать спецификатор %I64d).
3 4
4 4 4
1 1 5
5 5 3
4 1 2
1 3 1
3 5 4
1 4 3
7
2 2
9 2
2 3
6 1
11
