격자 모양의 밭을 $N \times M$ 크기의 정수 행렬 $A$ 로 표현한다.
각 칸 $(r, c)$에는 (싹 없는 감자 수) - (싹 있는 감자 수) $v \in \mathbb{Z}$가 들어 있다.
민준이는 다음 규칙으로 한 줄로 이동하며 최대한 많은 감자를 먹으려 한다.

싹 없는 감자를 먹으면 에너지가 늘며, 싹 있는 감자를 먹으면 독성이 있다.
즉, “싹 있는 감자 1개”는 “싹 없는 감자 -1개”와 완전히 동등하다고 간주한다.

• 시작
  • 임의의 칸 $(r, c)$에서 시작할 수 있다.
  • 그 칸의 값 $n = A[r][c]$를 초기 에너지 $E$이자 현재까지 먹은 감자 수 $S$로 설정한다.
• 이동
  • 네 방향(위, 아래, 왼쪽, 오른쪽) 중 하나를 고른다.
  • 한 칸 이동할 때마다
    1. 에너지 $E$를 1만큼 소모한다. ($E \gets E - 1$)
    2. 이동한 칸의 값 $v'$만큼 에너지를 회복하고, 먹은 감자 수에 더한다. ( $E \gets E + v'$, $S \gets S + v'$ )
  • $E \le 0$ 인 경우 더 이상 이동할 수 없다.
  • 경계를 벗어나면 즉시 이동을 중단한다.
• 목표

  • 가능한 모든 시작 칸과 네 방향을 고려했을 때 먹을 수 있는 감자의 최댓값 $S_{\text{max}}$을 출력한다.

  • 모든 칸의 값이 음수 또는 0이라도, 시작 칸에서 먹기만 하는 경우가 있으므로 $S_{\text{max}}$는

    $\text{max}_{0\le r<N,\,0\le c<M}A[r][c]$이상이 된다.

첫 번째 줄에는 $N, M$이 공백으로 구분되어 입력된다.( $1 \le N,M \le 200$)

다음 $N$개의 줄에는 행렬 $A$가 입력된다. ( $−1000 \le A[r][c] \le 1000$ )