무한부스터

카트라이더를 처음 시작한 카린이 정범이는 어려운 조작법에 점점 실망하고 있다. 드리프트, 순간 부스터, 커팅, 톡톡이 같은 어려운 테크닉에 지친 정범이는 그나마 쉬운 ‘숭고한 무한부스터 모드’에 도전하려고 한다.

‘숭고한 무한부스터 모드’는 크기 N × M의 직사각형 맵에서 진행되며, 맵 전체가 단위 격자로 이루어져 있다. 기존 ‘무한부스터 모드’와 달리 모든 격자 안에 특정 개수의 부스터 아이템이 놓여 있다. 이 모드의 진행 방식은 다음과 같다.

처음에 플레이어의 카트바디는 출발지점인 1행 1열에 멈춰 있는 상태로 있고, 보유한 부스터 아이템은 0개이다. 목표는 도착지점인 N행 M열 격자에 도달하는 것이며, 도달하는 즉시 게임이 끝난다. 카트바디가 격자에 멈춰 있을 때 격자에 놓인 부스터 아이템을 자동으로 전부 습득한다. 이때 x개를 습득했다면 한 방향을 정해 오른쪽으로 최대 x칸 또는 아래쪽으로 최대 x칸 이동할 수 있고, 이동은 1칸 단위로 한다. 예를 들어 부스터 아이템을 3개 습득했을 때 오른쪽으로 2칸 이동하거나 아래쪽으로 3칸 이동하는 것은 가능하지만, 오른쪽으로 1칸 이동한 뒤 아래로 2칸 이동하는 것, 왼쪽으로 1칸 이동하는 것, 아래쪽으로 2.718칸 이동하는 것은 불가능하다. 이동을 마치고 멈추면 보유하던 부스터 아이템은 모두 소진된다.

이동 중에 멈추지 않고 지나치는 격자의 부스터 아이템은 습득할 수 없으며, 카트바디는 맵을 벗어나는 방향으로 움직일 수 없다.

정범이는 ‘숭고한 무한부스터 모드’에서 출발지점부터 도착지점까지 주행하면서 부스터 아이템을 획득하게 되는 격자의 개수를 최소화하려고 한다. 카린이 정범이를 도와주자.

첫 번째 줄에 맵의 세로 길이와 가로 길이를 나타내는 양의 정수 N과 M이 공백으로 구분되어 주어진다. (1 ≤ N, M ≤ 300)

두 번째 줄부터 N개의 줄에 걸쳐 각 격자에 있는 부스터 아이템 개수인 M개의 양의 정수 aij가 공백으로 구분되어 주어진다. (1 ≤ aij ≤ max(N, M)) aij는 i행 j열 격자에 있는 부스터 아이템 개수이다.

출발지점과 도착지점은 다르다.

첫 번째 줄에 정범이가 맵의 출발지점부터 도착지점까지 이동하면서 부스터 아이템을 획득하게 되는 격자의 최소 개수를 출력한다.