Matrisdə yol

Sizə n × m ölçüsündə bir matris verilib, burada hər bir element 0-dan böyük və 10000-dən kiçik olan tam ədəddir.

Matrisdə qonşu hüceyrələr, sütun və ya sətir nömrələri yalnız 1 fərqlənən hüceyrələrdir. Bir hüceyrədən digərinə keçid yalnız qonşu hüceyrələr vasitəsilə mümkündür.

Sizdən tələb olunan, matrisin sol üst küncündən sağ alt küncünə qədər minimal dəyərli yolu tapmaqdır. Yolun dəyəri, yol boyunca keçilən matris elementlərinin cəmi ilə müəyyən edilir. Qonşu hüceyrələrə sola, sağa, yuxarı və aşağı hərəkət etmək icazəlidir.

Giriş məlumatları

Birinci sətirdə n və m ədədləri (1 ≤ n, m ≤ 10) verilir. Sonra n sətir gəlir, hər sətirdə boşluqla ayrılmış m ədəd var.

Çıxış məlumatları

Minimal yolun dəyərini çıxış edin.

Nümunələr