문제

시험이 끝난 뒤, 지친 학생들은 놀기 위해 자습 시간마다 공부 대신 책상 사이사이 복도를 돌아다니며 떠들기 시작했다. 시험이 끝나는 날 자습 감독을 맡게 된 박홍 선생님은, 기말고사 전까지는 학생들이 조금이라도 조용히 공부하기를 바랐다. 하지만 독서동의 모든 복도를 직접 돌아다니며 감시하기에는 너무 넓었다. 고민 끝에 박홍 선생님은 자신을 대신해 복도를 감시할 로봇인 가짜 박홍을 만들었다.

대곽의 독서동은 $N × M$ 크기의 격자 모양으로 이루어져 있다. 각 칸은 복도이거나 책상이다.

복도 칸들이 가로 또는 세로로 연속해서 이어져 있으면 하나의 복도 구간을 이룬다. 정확히는 다음과 같이 정의한다.

가로 복도 구간: 같은 행에서 좌우로 인접한 복도 칸들이 최대한 길게 이어진 구간

세로 복도 구간: 같은 열에서 위아래로 인접한 복도 칸들이 최대한 길게 이어진 구간

길이가 $1$인 구간도 하나의 복도 구간이다.

각 복도 칸에는 가짜 박홍을 하나 배치할 수 있다. 복도 칸마다 가짜 박홍을 배치하는 데 드는 비용이 정해져 있다.

어떤 복도 칸에 가짜 박홍을 배치하면, 그 가짜 박홍은 다음 두 복도 구간을 모두 감시한다.

가짜 박홍이 배치된 칸이 속한 가로 복도 구간

가짜 박홍이 배치된 칸이 속한 세로 복도 구간

박홍 선생님은 모든 복도 구간을 감시하려고 한다. 즉, 모든 가로 복도 구간과 모든 세로 복도 구간이 적어도 하나의 가짜 박홍에 의해 감시되어야 한다. 모든 복도 구간을 감시하기 위해 필요한 가짜 박홍 배치 비용의 최솟값을 구하여라.

입력

첫 번째 줄에 독서동의 세로 길이 $N$, 가로 길이 $M$이 공백으로 구분되어 주어진다.

두 번째 줄부터 $N$개의 줄에 걸쳐 각 칸의 정보가 주어진다.

각 줄에는 $M$개의 정수 $A_{ij}$가 공백으로 구분되어 주어진다.

$A_{ij} = 0$이면 $i$행 $j$열은 책상이다.

$A_{ij} > 0$이면 $i$행 $j$열은 복도이며, 이 칸에 가짜 박홍을 배치하는 비용은 $A_{ij}$이다.

$1 \leq N \leq 500$

$1 \leq M \leq 8$

$0 \leq A_{ij} \leq 10^9$

출력

모든 복도 구간을 감시하기 위해 필요한 가짜 박홍 배치 비용의 최솟값을 출력한다.

예제 입력 1

3 3
1 100 1
100 1 100
1 100 1

예제 출력 1

3

예제 입력 2

4 5
4 6 0 2 5
3 1 0 7 2
0 0 6 1 4
5 2 0 0 3

예제 출력 2

25