Garbage
Национална Олимпиада по Информатика 2015, Кръг 3
Time Limit: 2s, Memory Limit: 64MiB
Навярно не много от вас знаят, че скоро ще бъде отворен първият завод за преработване на боклук в България. Част от работата, която ще се върши там е да се компресира боклука. За да се прави това той се поставя в правоъгълна "стая", като всяка от четирите стени е бутало, което може да натисне боклука от съответната страна. Боклукът, от друга страна е разнороден и се нуждае от различно количество енергия за натискане, за да се компресира.

Можете да си представите боклука и стаята като правоъгълна матрица с N реда и M колони. Във всяка клетка на матрицата има по една цифра Aij между 0 и 9, включително - какъв "натиск" се изисква, за да бъде компресирана тя. Когато някоя от четирите стени "натисне" оставащия боклук е нужна енергия, равна на най-голямата цифра в съответната страна на матрицата - краен ред за горната и долната стена, и крайна колона за лявата и дясната.

Например, нека имаме компресираща стая с 3 реда и 4 колони, като боклукът в нея е с "твърдост", зададена в таблицата.
6872
3091
4291
Ако натиснем с горната стена (ред с числа 6, 8, 7, 2) ще ни е нужна сила 8, тъй като това е най-твърдата клетка в този ред. Аналогично, за долната стена ще ни е нужна сила 9, за лявата - сила 6, а за дясната - сила 2. След натискане въпросният ред или колона изчезва - вече считаме за компресиран и не играе роля в следващи натискания. Целта е целият боклук (тоест всички клетки) да бъдат компресирани. За да е ефективен заводът се изисква това да стане с минимална обща използвана сила.

Оказва се, че има значение кои бутала и в какъв ред ползваме. Ако, например, ползваме само горното бутало биха ни били нужни 8 + 9 + 9 = 26 единици сила. Ако вместо това ползваме горното, дясното, дясното, лявото, долното за 8 + 1 + 9 + 4 + 2 = 24.

Чувайки за вече легендарната креативност на Ели (най-вече в това да предоставя сложните си проблеми на вас) сега тя е назначена на ръководител на отдела по натискането. Разбира се, момичето ви дава възможността да блеснете, като напишете програма, която намира с колко най-малко енергия може да бъде компресиран целия боклук.
Вход
На първия ред на стандартния вход ще бъдат зададени броя редове N и броя колони M на стаята. Следват N на брой реда, всеки съдържащ по M цифри Aij - твърдостта на боклука във всяка от клетките.
Изход
На стандартния изход изведете едно цяло число - минималната енергия, нужна за компресирането на всичкия боклук.
Ограничения
  • 1 ≤ N, M ≤ 100
  • 0 ≤ Aij ≤ 9
Примерен Вход Примерен Изход
3 4 6 8 7 2 3 0 9 1 4 2 9 1 24
8 7 9 5 9 9 8 9 1 1 3 7 0 1 7 7 6 0 7 3 7 0 3 2 2 6 1 5 4 8 6 9 9 2 3 2 7 4 6 7 3 1 1 3 1 6 7 1 2 6 7 4 4 7 3 9 8 9 62
Мрън!