Родзинки#290
Відома пловдивська шоколадниця Боні хоче розрізати плитку шоколаду з родзинками. Плитка має прямокутну форму і складається з одиничних квадратних шматочків. Шматочки вирівняні паралельно краям плитки, так що вони формують рядків і стовпців, усього виходить N \times M шматочків. На кожному зі шматочків є одна або більше родзинок, і жодна родзинка не лежить між шматочками і не перетинає розріз між ними.
Спочатку плитка шоколаду є одним цілим. Боні хоче розрізати її на все менші й менші частини, поки врешті-решт не розріже всю плитку шоколаду на N \times M одиничних шматочків.
Оскільки Боні дуже зайнята, вона попросила свого асистента Петра допомогти розрізати плитку шоколаду. Петро робить лише прямі розрізи від краю до краю частини. Він хоче, щоб йому платили за кожен розріз, який він зробить. У Боні зовсім немає грошей, але у неї залишилась нескінченна кількість родзинок, і вона збирається розраховуватись із Петром родзинками. Петра це влаштовує, але за такої умови: кожного разу, коли він розрізає частину шоколаду на дві менші частини, він отримує стільки ж родзинок, скільки було на вихідній частині.
Боні хоче заплатити Петрові якнайменше. Вона знає, скільки родзинок знаходиться на кожному з N \times M шматочків. Вона може обрати порядок, у якому дає Петрові решту частинок, і також може сказати Петрові, які саме розрізи робити (горизонтальні чи вертикальні) і в якому саме місці.
Допоможіть Боні визначити, як розрізати плитку шоколаду на одиничні шматочки так, щоб розрахуватися з Петром якомога меншою кількістю родзинок.
Завдання
Напишіть програму, яка за заданою кількістю родзинок на кожному з одиничних шматочків визначає мінімальну кількість родзинок, якими Боні має розрахуватися з Петром.
Перший рядок містить два цілі числа і (1 \leq N, M \leq 50) — кількість рядків і стовпців.
Кожен із наступних рядків містить по цілих чисел, що визначають кількість родзинок на кожному шматочку в цьому рядку (зліва направо в кожному рядку). Зокрема, -те число у -му рядку (1 \leq R_{k,p} \leq 1000) вказує кількість родзинок на шматочку у -му рядку і -му стовпці.
Виведіть одне ціле число — мінімальну кількість родзинок, якими Боні має розрахуватися з Петром.
Приклад 1