Родзинки

Відома пловдивська шоколадниця Боні хоче розрізати плитку шоколаду з родзинками. Пли­тка має прямокутну форму і складається з одиничних квадратних шматочків. Шматочки вирівняні парале­льно краям плитки так, що вони формують N рядків та M стовпців, усього виходить NхM шматочків. На кожному зі шматочків є одна або більше родзинок, і ніяка родзинка не лежить між шматочками і не пере­тинає розріз між ними.

Спочатку плитка шоколаду є одне ціле. Боні хоче розрізати її на все менші і менші частки, пока вона, на­решті, не розріже всю плитку шоколаду на NхM оди­ночних шматочків. Оскільки Боні дуже зайнята, вона попросила свого асистента Петра допомогти розрізати плитку шоколаду. Петро робить тільки прямі розріз від краю до краю частки. Він хоче, щоб йому платили за кажен розріз, який він зробить. У Боні зовсім немає грошей, але у неї залишилась нескінчена кількість ро­дзинок, і вона збирається розраховуватись із Петром родзинками. Петра це влаштовує, але за такої умови: кожен раз, коли він розрізає частину шоколаду на дві менші частини, він отримує стільки ж родзинок, скіль­ки було на вихідній частині.

Боні хоче заплатити Петру якомога менше. Вона знає, скільки родзинок знаходиться на кожному з NхM шматочків. Вона може обрати порядок, у яко­му дає Петру решту частин, і вона також може каза­ти Петру, які саме розрізи робити (горизонтальні чи вертикальні) і в якому саме місці. Допоможіть Боні вирішити, як розрізати плитку шоколаду на одино­чні шматки так, щоб розплатитися з Петром якомо­га меншою кількісттю родзинок.

Завдання

Напишіть програму, яка за заданою кількістю родзинок на кожному з одиночних шма­точків визначить мінімальну кількість родзинок, котрими Боні має розрахуватись з Петром.

Вхідні дані

Ваша програма має прочитати зі ста­ндартного потоку введення такі дані:

• Перший рядок містить два цілих числа N і M, разділені одним пропуском. • Наступні N рядків описують, скільки родзинок знаходиться на кожному шматочку шоколаду. k-й з цих N рядків описує k-ий рядок плитки. Ко­жен такий рядок містить M цілих чисел, розділе­них одиночними пропусками. Ці цілі числа опи­сують шматочки у відповідному рядку плитки зліва направо. p-е з чисел у k-му рядку (серед цих N рядків) повідомляє, скільки родзинок знахо­диться на шматочку, що розміщений у k-му рядку і p-му стовпчику. Обмеження

1 <= N, M <= 50 кількість шматоч­ків вздовж кожної зі сторін плитки шоколаду, 1 <= R_{k,p} <= 1000 кількість родзинок на шматочку у k-му рядку і p-му стовпці. Вихідні дані

Ваша програма має записати у ста­ндартний потік виведення один рядок, що містить одне ціле число: мінімальну кількість родзинок, ко­трими Боні мала розрахуватися з Петром.

Приклади