마을을 지키는 벽

렉토스 섬은 늘 홍수와 해적에 시달린다. 그래서 렉토스의 왕은 섬에 있는 모든 마을을 하나의 거대한 벽으로 둘러싸 지키려고 한다.

렉토스는 직사각형이다. 벽을 설계하는 건축가는 섬을 정사각형 칸으로 나눈 격자로 나타낸다. 마을은 각각 한 칸 안에 있고, 수도는 가장 북서쪽 칸, 즉 왼쪽 위 칸에 있다.

격자 바깥에서 출발하면 벽을 넘지 않고는 어떤 마을에도 닿을 수 없어야 한다.

벽은 격자선 위에만 쌓는다. 건축가는 왼쪽 위 꼭짓점에서 시작하는 두 격자선 조각 중 하나에 첫 번째 벽 조각을 놓는다. 그다음부터는 바로 앞 벽 조각이 끝난 꼭짓점에서 시작하는 격자선 조각 위에 다음 벽 조각을 놓고, 왼쪽 위 꼭짓점으로 돌아오면 멈춘다. 이렇게 쌓으면 같은 격자선 조각 위에 벽 조각이 여러 개 놓일 수도 있다. 즉 벽은 격자선 조각이 이어진 하나의 닫힌 경로다.

지형 때문에 격자선 조각마다 그 위에 벽 조각 하나를 놓는 비용이 정해져 있다. 벽의 총비용은 놓은 벽 조각의 비용을 모두 더한 값이다. 한 격자선 조각 위에 벽 조각을 $t$개 놓았다면 그 조각의 비용을 $t$번 더한다.

마을의 위치와 모든 격자선 조각의 비용이 주어진다. 벽을 쌓는 최소 비용을 구하라.

첫째 줄에 격자의 행 개수 $N$과 열 개수 $M$이 주어진다.

다음 $N$개 줄에는 격자의 각 행이 위에서부터 주어진다. 각 줄에는 0 또는 1인 정수가 왼쪽부터 $M$개 있다. 0은 빈 칸이고, 1은 그 칸에 마을이 있다는 뜻이다. 이 중 첫 줄의 첫 번째 정수는 항상 1이다.

다음 $N$개 줄에는 각각 정수가 $M + 1$개 주어진다. $i$번째 줄의 $j$번째 수는 위에서 $i$번째 행에서 왼쪽부터 $j$번째 세로 격자선 조각에 벽 조각 하나를 놓는 비용이다.

다음 $N + 1$개 줄에는 각각 정수가 $M$개 주어진다. $i$번째 줄의 $j$번째 수는 위에서 $i$번째 가로 격자선에서 왼쪽부터 $j$번째 조각에 벽 조각 하나를 놓는 비용이다.

첫째 줄에 벽을 쌓는 최소 비용을 출력한다.

• $1 \le N, M \le 400$
• 모든 비용 $v$는 $1 \le v \le 10^9$인 정수다.
• 답은 32비트 정수의 범위를 넘을 수 있다.

아래 그림은 예제 입력 두 개의 최적 벽을 보여준다. 벽은 굵은 선이고, 마을이 있는 칸은 색을 칠했다.