서예가

리틀 E는 서예를 아주 좋아한다. NOI2013이 시작되었다는 소식을 듣고, 모두에게 NOI 글자를 쓴 서예 작품을 선물하려고 한다.

리틀 E에게는 마법의 종이가 한 장 있다. 이 종이는 $n$개의 행과 $m$개의 열로 이루어진 2차원 격자이다. 왼쪽 아래 모서리의 좌표는 $(1, 1)$이고, 오른쪽 위 모서리의 좌표는 $(m, n)$이다. 각 칸에는 정수 행운도가 적혀 있다. 칸에 글씨를 쓰면 모두의 행운도가 올라간다. 전체 행운도는 글씨를 쓴 모든 칸의 행운도 합이다. 종이에 N, O, I 세 글자를 써야 한다.

세 글자는 다음과 같이 정의된다.

1. N은 격자의 축에 평행한 직사각형 3개 이상으로 이루어진다. 직사각형의 개수를 $K$라 하고 1부터 $K$까지 번호를 붙인다. $i$번째 직사각형의 왼쪽 아래 모서리는 $(L_i, B_i)$, 오른쪽 위 모서리는 $(R_i, T_i)$이다. 이 값들은 다음을 만족한다.

   1. $L_i \leq R_i$, $B_i \leq T_i$;
   2. 모든 $1 < i \leq K$에 대해 $L_i = R_{i-1} + 1$;
   3. 모든 $3 \leq i < K$에 대해 $B_{i-1} - 1 \leq T_i \leq T_{i-1}$, $B_i \leq B_{i-1}$;
   4. $B_2 > B_1$, $T_2 = T_1$, $B_{K-1} = B_K$, $T_{K-1} < T_K$.

2. O는 큰 직사각형 $A$에서 작은 직사각형 $B$를 도려낸 모양이다. 두 직사각형 모두 변이 격자의 축에 평행하다. $A$의 왼쪽 아래 모서리를 $(u, v)$, 너비를 $W$, 높이를 $H$라 하자. 그러면 $B$의 왼쪽 아래 모서리는 $(u+1, v+1)$이고, 너비는 $W-2$, 높이는 $H-2$이다. 이 값들은 다음을 만족한다.

   1. $W \geq 3$, $H \geq 3$;
   2. $u > R_K + 1$.

3. I는 격자의 축에 평행한 직사각형 3개로 이루어진다. 아래에서 위로 1, 2, 3번을 붙인다. $i$번 직사각형의 왼쪽 아래 모서리는 $(P_i, Q_i)$, 오른쪽 위 모서리는 $(G_i, H_i)$이다. 이 값들은 다음을 만족한다.

   1. $P_i \leq G_i$, $Q_i \leq H_i$;
   2. $P_1 = P_3 > u + W$, $G_1 = G_3$;
   3. $Q_1 = H_1 = Q_2 - 1$, $H_2 + 1 = Q_3 = H_3$;
   4. $P_1 < P_2 \leq G_2 < G_1$.

아래 그림은 N, O, I를 올바르게 배치한 예이다.

설계에서 그리는 도형은 어느 것도 격자의 경계를 넘으면 안 된다. 리틀 E는 이 설계로 얻을 수 있는 행운도의 최댓값을 구하려고 한다.

첫 줄에 행의 수 $n$과 열의 수 $m$이 주어진다. 이어지는 $n$개의 줄에는 각각 $m$개의 정수가 주어진다. $i + 1$번째 줄의 $j$번째 정수는 $(j, n - i + 1)$ 칸의 행운도이다.

설계로 얻을 수 있는 전체 행운도의 최댓값 $T$를 정수 하나로 출력한다.

$3 \leq n \leq 150$

$3 \leq m \leq 500$

각 칸의 행운도는 $[-200, 200]$ 범위의 정수이다.