파파야 정글

베시가 농장을 벗어나 이웃한 농부의 땅으로 들어갔다. 그 농부는 소들이 아주 좋아하는 맛있는 파파야를 재배한다. 파파야 정글은 $R$개의 행과 $C$개의 열로 이루어진 격자로 나뉘어 있다 ($1 \le R \le 40$, $1 \le C \le 40$). 베시는 현재 칸에서 $x$축 또는 $y$축 방향으로 인접한(상하좌우) 칸으로만 이동할 수 있다. 예를 들어 아래 그림에서 베시가 B 칸에 있다면 T로 표시된 칸 중 하나로 이동할 수 있다.

.T.
TBT
.T.

베시는 항상 $(1, 1)$ 칸(첫째 행, 첫째 열)의 파파야를 먹는 것으로 시작한다. 한 칸을 다 먹은 뒤에는 믿음직한 쌍안경으로 인접한 각 칸에 남아 있는 파파야의 개수를 세고, 아직 먹지 않은 파파야가 가장 많은 칸으로 이동한다. 그런 칸은 항상 유일하게 정해진다. 이 규칙을 계속 따르면 베시는 언젠가 반드시 $(R, C)$ 칸에 도달하여 그곳의 파파야까지 먹게 된다.

파파야 정글의 크기와 각 칸에 있는 파파야의 개수 $F_{ij}$ ($1 \le F_{ij} \le 100$)가 주어질 때, 베시가 먹는 파파야의 총 개수를 구하여라.

• 첫째 줄: 공백으로 구분된 두 정수 $R$과 $C$.
• 둘째 줄부터 $R+1$째 줄까지: $i+1$째 줄에는 정글의 $i$번째 행에 있는 $C$개의 정수 $F_{i1}, F_{i2}, \ldots, F_{iC}$가 공백으로 구분되어 주어진다. 각 값은 해당 칸에 있는 파파야의 개수이다.

• 첫째 줄: 베시가 오른쪽 아래 $(R, C)$ 칸의 파파야까지 모두 먹었을 때 먹은 파파야의 총 개수를 나타내는 정수 하나.

베시는 아래 숫자 옆에 적힌 알파벳 순서(a, b, c, …)대로 파파야를 먹는다. 이는 위 예시 입력에 해당한다.

3a  3   4g  5h
4b  5c  3f  2i
1   7d  4e  2j

베시는 파파야 4개($(1,2)$의 3과 $(3,1)$의 1)를 먹지 않고 지나치며, 격자의 12칸 중 10칸을 방문하여 총 39개를 먹는다.