문제 설명
N행 M열의 월드맵에 루루와 루미가 있다. 루루는 (1행, 1열)에 있고, 루미는 (N행, M열)에서 기다리고 있으며, 루루는 루미에게 최대한 빠르게 이동할 예정이다.
다만, 월드맵에는 루루가 좋아하는 이삭이 곳곳에 존재하며, 가는 길에 이삭이 있다면 루루는 무조건 가방에 챙기고 이동한다. (한 칸에 여러개의 이삭이 있을 수도 있다.)
루루가 루미를 만나러 가는 길에 챙길 수 있는 최대 이삭의 수를 출력하는 프로그램을 작성하시오.
다만, 월드맵에는 루루가 좋아하는 이삭이 곳곳에 존재하며, 가는 길에 이삭이 있다면 루루는 무조건 가방에 챙기고 이동한다. (한 칸에 여러개의 이삭이 있을 수도 있다.)
루루가 루미를 만나러 가는 길에 챙길 수 있는 최대 이삭의 수를 출력하는 프로그램을 작성하시오.
입력 설명
첫째 줄에는 행(N)과 열(M)이 공백으로 구분되어 주어진다.
둘째 줄부터 맵의 정보가 주어진다.
둘째 줄부터 맵의 정보가 주어진다.
출력 설명
루루가 챙길 수 있는 이삭의 최대 수를 구하시오.
입력 예시 Copy
4 3
0 3 0
2 1 2
0 0 3
5 2 1
출력 예시 Copy
10