고도

도시 YT는 잘 설계된 도시이다. 동서 방향과 남북 방향으로 뻗은 간선도로가 도시를 n×n개의 구역으로 나눈다. 간단히 말해, 도시 YT는 각 구역도 정사각형인 정사각형으로 볼 수 있다. 따라서 도시 YT에는 (n + 1)×(n + 1)개의 교차로와 2n×(n+1)개의 양방향 도로(이하 도로)가 있다. 각 도로는 간선도로 위의 한 쌍의 교차로를 연결한다. 아래 그림은 2×2개의 구역으로 나뉜 도시 YT(n = 2)의 지도로, 3×3개의 교차로와 12개의 도로를 나타낸다.

\n작은 Z는 이 도시의 시장이다. 통계 정보를 이용해 그는 출퇴근 시간대에 각 도로를 지나는 사람들의 양방향 유동량을 얻었다. 각 출퇴근 시간대 동안 그는 특정 도로의 특정 방향으로 가는 사람 수를 알게 된다. 각 교차로에는 고도가 있으며, 이는 도시 YT의 시민들이 매우 스트레스를 받는 문제이다. 사람이 고도 h까지 올라가려면 h 단위의 에너지를 소모해야 한다. 내려가는 경우에는 에너지가 필요하지 않다. 도로를 따라 이동할 때, 도착지 고도와 출발지 고도의 차이가 h라면(여기서 h는 음수일 수 있다), 사람은 도로를 이동할 때 max{0, h} 단위의 에너지를 소모한다(여기서 max{a, b}는 두 수 a와 b 중 큰 수를 나타낸다).

작은 Z는 또한 도시의 북서쪽 모서리에 있는 교차로의 고도를 0으로, 남동쪽 모서리에 있는 교차로의 고도를 1로 측정했다(위 그림에 나타난 대로). 그러나 다른 교차로의 고도는 결정할 방법이 없다. 작은 Z는 가장 이상적인 상황(모든 교차로의 고도를 자유롭게 가정할 수 있는 상황)에서 출퇴근 시간대에 사람들이 경사를 오르며 소모하는 총 에너지의 최솟값을 알고 싶어 한다.

입력의 첫 줄에는 정수 n이 하나 주어지며, 그 의미는 위에서 설명한 것과 같다.

다음 4n(n + 1)개의 줄에는 각각 하나의 음이 아닌 정수가 주어지며, 이는 출퇴근 시간대에 특정 도로를 특정 방향으로 지나는 사람 수(즉 유동량)를 나타낸다.

입력 순서는 서에서 동으로 가는 사람들의 유동량을 나타내는 n(n + 1)개의 수, 북에서 남으로 가는 사람들의 유동량을 나타내는 n(n + 1)개의 수, 동에서 서로 가는 사람들의 유동량을 나타내는 n(n + 1)개의 수, 마지막으로 남에서 북으로 가는 사람들의 유동량을 나타내는 n(n + 1)개의 수 순이다. 각 방향별 유동량에 대해, 입력 순서는 출발지의 북쪽에서 남쪽 방향 순이다. 출발지의 남북 위치가 같다면 입력 순서는 서쪽에서 동쪽 방향 순이다(아래 샘플 참조).

고도가 이상적일 때 출퇴근 시간대에 이동하는 모든 사람의 총 에너지 소모량의 최솟값을 나타내는 수 하나를 출력한다. 답은 가장 가까운 정수로 반올림(사사오입)한다.

1 ≤ n ≤ 500, 0 ≤ 유동량 ≤ 1,000,000. 또한 모든 유동량은 정수이다.

\n