Произошло радиоактивное заражение местности. Составлена карта зараженности. Она представляет собой прямоугольную таблицу N×M, в клетках которой записана зараженность соответствующего участка.
Требуется написать программу, которая найдет путь из левой верхней клетки таблицы в правую нижнюю клетку с минимальной суммарной дозой радиации.
Входной файл INPUT.TXT содержит в первой строке числа N и M, а в следующих N строках – по M чисел – карта зараженности местности. Числа в строках разделяются одним пробелом. 1 ≤ N ≤ 30, 1 ≤ M ≤ 30, зараженность участка – целое число от 0 до 100.
Выходной файл OUTPUT.TXT должен содержать одно число – суммарную долю радиации.
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 3 5
2 100 0 100 100
1 100 0 0 0
1 0 3 100 2
| 9 |
