Вам задано матрицю розміром n × m, яка містить невід'ємні цілі числа, що не перевищують 10000.

Сусідні клітинки матриці – це клітинки, номера стовбців чи рядків яких відрізняються на 1. Шлях від однієї клітинки матриці до іншої проходить лише через сусіднні клітинки.

Вам необхідно знайти шлях мінімальної вартості між лівим верхнім та правим нижнім кутами матриці. Вартість шляху формується як сума елементів матриці, через які проходить шлях. Дозволяється рухатись у сусідні клітинки ліворуч, праворуч, угору та вниз.

Вхідні дані

У першому рядку містяться числа n та m (1 ≤ n, m ≤ 10). Далі йде n рядків, у кожному рядку по m чисел, відокремлених пропуском.

Вихідні дані

Виведіть вартість мінімального шляху.