Известная Пловдивская шоколадница Бонни хочет разрезать плитку шоколада с изюмом. Плитка имеет прямоугольную форму и состоит из одиночных квадратных кусочков. Кусочки выровнены параллельно краям плитки таким образом, что они формируют N строк и M столбцов, всего получается N*M кусочков. На каждом из кусочков имеется одна или более изюминок, и никакая изюминка не лежит между кусочками и не пересекает разрез между ними. Изначально плитка шоколада представляет собой единое целое. Бонни хочет разрезать её на все меньшие и меньшие части, пока она, наконец, не разрежет всю плитку шоколада на N*M одиночных кусочков. Поскольку Бонни очень занята, она попросила своего ассистента Петра помочь разрезать плитку шоколада. Пётр делает только прямые разрезы от края до края части. Он хочет, чтобы ему платили за каждый разрез, который он сделает. У Бонни совсем нет денег, но у неё осталось бесконечное количество изюминок, и она собирается расплачиваться с Петром изюмом. Петра это устраивает, но при следующем условии: каждый раз, когда он разрезает часть шоколада на две меньших части, он получает столько же изюминок, сколько было на исходной части. Бонни хочет заплатить Петру как можно меньше. Она знает, сколько изюминок находится на каждом из N*M кусочков. Она может выбрать порядок, в котором даёт Петру остающиеся части, и она также может говорить Петру, какие именно разрезы делать (горизонтальные или вертикальные) и в каком именно месте. Помогите Бонни решить, как разрезать плитку шоколада на одиночные кусочки таким образом, чтобы расплатиться с Петром как можно меньшим количеством изюминок. ЗАДАНИЕ Напишите программу, которая по заданному количеству изюминок на каждом из одиночных кусочков определяет минимальное количество изюминок, которым Бонни должна расплатиться с Петром. ВХОДНЫЕ ДАННЫЕ Ваша программа должна читать из стандартного потока ввода следующие данные: • Первая строка содержит два целых числа \textbf{N} и \textbf{M}, разделённые одним пробелом. • Последующие N строк описывают, сколько изюминок находится на каждом кусочке шоколада. \textbf{k}-я из этих N строк описывает \textbf{k}-ю строку плитки. Каждая такая строка содержит \textbf{M} целых чисел, разделенных одиночными пробелами. Эти целые числа описывают кусочки в соответствующей строке плитки слева направо. p-е из чисел на \textbf{k}-й строке (среди этих \textbf{N} строк) сообщает, сколько изюминок находится на кусочке, размещённом в \textbf{k}-й строке и \textbf{p}-м столбце. ОГРАНИЧЕНИЯ 1 <= \textbf{N}, \textbf{M} <= 50 Количество кусочков вдоль каждой стороны плитки шоколада. 1 <= \textbf{R_\{k,p\}} <= 1000 Количество изюминок на кусочке в \textbf{k}-й строке и \textbf{p}-м столбце. ВЫХОДНЫЕ ДАННЫЕ Ваша программа должна писать в стандартный поток вывода одну строку, содержащую одно целое число: минимальное количество изюминок, которым Бонни должна расплатиться с Петром.