시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 512 MB149973661148.415%

문제

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

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

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

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

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

입력

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

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

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

출력

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

예제 입력 1

4 5
1 1 4 1 3
3 4 1 3 2
1 1 5 3 2
5 3 1 1 1

예제 출력 1

3

3번 만에 이동하는 최적 경로는 다음과 같다.

  • 1행 1열에서 1개의 부스터 아이템을 획득하고, 아래쪽으로 1칸 이동하여 2행 1열에서 멈춘다.
  • 2행 1열에서 3개의 부스터 아이템을 획득하고, 아래쪽으로 2칸 이동하여 4행 1열에서 멈춘다.
  • 4행 1열에서 5개의 부스터 아이템을 획득하고, 오른쪽으로 4칸 이동하여 4행 5열에서 멈춘다. 도착지점에 도달했기 때문에 게임이 종료된다.

예제 입력 2

5 4
2 4 2 3
1 1 1 3
2 1 2 2
1 4 4 1
1 2 2 1

예제 출력 2

3

3번 만에 이동하는 최적 경로는 다음과 같다.

  • 1행 1열에서 2개의 부스터 아이템을 획득하고, 오른쪽으로 1칸 이동하여 1행 2열에서 멈춘다.
  • 1행 2열에서 4개의 부스터 아이템을 획득하고, 아래쪽으로 4칸 이동하여 5행 2열에서 멈춘다.
  • 5행 2열에서 2개의 부스터 아이템을 획득하고, 오른쪽으로 2칸 이동하여 5행 4열에서 멈춘다. 도착지점에 도달했기 때문에 게임이 종료된다.