얇은 얼음

Uolevi는 $n \times m$ 격자 모양의 얼어붙은 호수에 있으며, 각 칸에는 동전이 하나씩 있다. 각 칸에는 내구도가 있는데, 이는 그 칸의 얼음이 견딜 수 있는 동전 수의 최댓값이다.

한 번의 이동으로 Uolevi는 위, 아래, 왼쪽 또는 오른쪽으로 한 칸 이동할 수 있지만, 호수 밖으로 나갈 수는 없다. Uolevi가 현재 있는 칸에 동전이 있다면, 그 동전을 집을 수 있다. Uolevi가 어떤 칸으로 이동할 때, 그 칸에 있는 동전의 수는 절대로 그 칸의 내구도를 초과해서는 안 된다. 여기에는 Uolevi가 들고 있는 동전과, 얼음 위의 동전을 아직 집지 않았다면 그 동전도 포함된다. Uolevi 자신의 무게는 무시할 수 있다.

Uolevi는 호수의 어떤 가장자리 칸에서 여정을 시작하여 어떤 가장자리 칸에서 끝내고 싶어 한다. 여정 중에 모을 수 있는 동전 수의 최댓값은 얼마인가?

채점

그룹 | 점수 | 제약 조건

1 | 17 | $1 \leq n \cdot m, d \leq 16$.

2 | 12 | $1 \leq n \cdot m \leq 200\,000$, $1 \leq d \leq 5$.

3 | 11 | $n = 1$, $1 \leq m, d \leq 100$.

4 | 19 | $n = 1$, $1 \leq m, d \leq 200\,000$.

5 | 14 | $1 \leq n \cdot m, d \leq 1\,000$.

6 | 27 | $1 \leq n \cdot m, d \leq 200\,000$.

입력의 첫째 줄에는 호수의 높이와 너비를 나타내는 정수 $n$와 $m$가 주어진다. 이어서 각 칸의 얼음 내구도 d를 나타내는 정수 $m$개가 있는 줄 $n$개가 주어진다.

Uolevi가 모을 수 있는 동전 수의 최댓값을 출력한다.

예제 입력에서 Uolevi는 왼쪽 위 칸에서 시작할 수 있다. 아래로 한 칸 이동한 뒤 그 동전을 집는다. 그런 다음 오른쪽으로 이동하여 그 동전을 집는다. 이어서 아래로 이동한 다음 왼쪽으로 이동하여 그 동전을 집는다. 그런 다음 오른쪽으로 이동하고 동전을 두 번 가져간다. 이 시점에 그는 가장자리에 있으므로 동전 다섯 개를 가지고 떠날 수 있다. 어떤 가장자리 칸도 내구도가 $\geq 6$이지 않으므로, 동전 여섯 개를 모아 가장자리로 돌아올 수는 없다.