Мінімальний шлях у таблиці

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

Потрібно знайти мінімальну суму в у.о., заплативши яку гравець може потрапити у правий нижній кут.

Вхідні дані

У вхідному файлі задано два числа N і M - розміри таблиці (1 ≤ N ≤ 20, 1 ≤ M ≤ 20). Далі йде N рядків по M чисел у кожному - розміри штрафів в у.о. за проходження через відповідні клітинки (числа від 0 до 100).

Вихідні дані

У вихідний файл запишіть мінімальну суму, витративши яку можна потрапити у правий нижній кут.

Вхідні дані

3 4

1 1 1 1

5 2 2 100

9 4 2 1

Вихідні дані

8

program dfgdf;

var i,j,k,n,m,t : integer;

s1 : int64;

s,l,a : array[1..100,1..100] of integer;

p : array [1..2,1..201] of integer;

BEGIN

readln (n,m);

t:=1;

for i:=1 to n do

for j:=1 to m do read (a[i,j]); s1:=a[1,1];

l[n,m]:=a[n,m]; s[n,m]:=0;

for i:=n-1 downto 1 do begin

l[i,m]:=l[i+1,m]+a[i,m];

s[i,m]:=0;

end;

for i:=m-1 downto 1 do begin

l[n,i]:=l[n,i+1]+a[n,i];

s[n,i]:=1;

end;

for j:=m-1 downto 1 do begin

for i:=n-1 downto 1 do begin

if l[i,j+1]<l[i+1,j] then begin

l[i,j]:=a[i,j]+l[i,j+1]; s[i,j]:=1; end else

begin l[i,j]:=a[i,j]+l[i+1,j]; s[i,j]:=0; end;

end;

end;

i:=1; j:=1; k:=1;

while k < n+m do begin

p[1,k]:=i; p[2,k]:=j; k:=k+1;

if s[i,j] = 1 then j:=j+1 else i:=i+1;

s1:=s1+a[i,j];

end;

writeln (s1);

END.