25623번 - 콜라 줍기

키파는 카루나와 정말 친합니다. 키파와 카루나는 N × N의 격자 위에서 살고 있고, 이 격자칸을 상하좌우로 이동할 수 있습니다. 격자 위 r번째 행 c번째 열의 격자칸을 (r, c)로 표기할 때, 키파네 집은 (1, 1)에 있고 카루나의 집은 (N, N)에 있습니다.

하지만 이렇게 친한 둘이어도 서로 절대로 양보할 수 없는 것이 있었으니, 그것은 바로 선호하는 콜라 취향이었습니다! 키파는 코카콜라 제로를 좋아하고 카루나는 펩시 제로를 좋아합니다.

어느 날 격자 위에 코카콜라 제로와 펩시 제로가 나타났다는 소식을 들었습니다! 키파와 카루나는 자신의 집에서 통화로 긴 시간 논의한 끝에 다음과 같이 격자칸 위에 있는 콜라들을 줍기로 했습니다.

• 키파는 코카콜라 제로만, 카루나는 펩시 제로만 주울 것입니다.
• 키파와 카루나는 둘 다 서로의 집을 최단 거리로 한 번 이동할 체력만 있고, 그런 다음엔 반드시 서로의 집에서 쉬어야 합니다.
  • 즉, 서로의 집 사이 최단 거리는 2(N − 1)번 이동하는 것이므로, 둘 모두 자신의 집에서 정확히 그만큼을 이동하여 키파는 카루나의 집에, 카루나는 키파의 집에 도착해야 합니다.
  • 코카콜라 제로와 펩시 제로는 이름에 걸맞게 무게가 0이기 때문에 체력에 영향을 주지 않습니다.
• 둘 모두 코로나19 상황이 걱정되었기 때문에, 서로의 경로가 서로의 집을 제외하고 격자칸을 공유하면 안 됩니다. “이동 중 만나면 안 된다”보다 훨씬 강한 조건임에 유의하세요.
• 서로 어쨌든 콜라가 많으면 좋은 것에는 합의했기 때문에, 키파와 카루나가 주운 콜라의 종류에 상관없이 개수의 합을 최대화하기로 합의했습니다.

여러분은 비밀리에 지도를 입수했습니다. 키파와 카루나를 도와주세요!

첫째 줄에 격자의 크기 N이 주어집니다. (2 ≤ N ≤ 400)

둘째 줄부터 N개의 줄에 각 격자칸에 있는 코카콜라 제로의 개수가 주어집니다.

구체적으로, (i + 1)번째 줄에 각 격자칸에 있는 코카콜라 제로의 개수 c_i,1, c_i,2, ⋯, c_i,N이 공백을 사이에 두고 주어집니다. (1 ≤ i ≤ N, 모든 1 ≤ i, j ≤ N에 대해 0 ≤ c_i,j ≤ 10⁹) 이는 모든 1 ≤ i, j ≤ N에 대해, (i, j)에 있는 코카콜라 제로의 개수가 c_i,j임을 의미합니다.

(N + 2)째 줄부터 N개의 줄에 각 격자칸에 있는 펩시 제로의 개수가 비슷한 형식으로 주어집니다.

구체적으로, (i + N + 1)번째 줄에 각 격자칸에 있는 펩시 제로의 개수 p_i,1, p_i,2, ⋯, p_i,N이 공백을 사이에 두고 주어집니다. (1 ≤ i ≤ N, 모든 1 ≤ i, j ≤ N에 대해 0 ≤ p_i,j ≤ 10⁹) 이는 모든 1 ≤ i, j ≤ N에 대해, (i, j)에 있는 펩시 제로의 개수가 p_i,j임을 의미합니다.

키파네와 카루나네 집에는 콜라가 없습니다. 즉, c_1,1 = c_N,N = p_1,1 = p_N,N = 0인 입력만 주어집니다.

첫째 줄에 키파와 카루나가 조건을 만족하며 주울 수 있는 콜라의 개수의 합의 최댓값을 출력합니다.

다음과 같은 두 가지 방법이 있습니다.

• 키파가 ‘ㄱ’자 모양으로 카루나네 집에 가고, 카루나가 ‘ㄴ’자 모양으로 키파네 집에 갑니다. 이때 키파는 5개의 코카콜라 제로를 주울 수 있고, 카루나는 3개의 펩시 제로를 주울 수 있어서 주울 수 있는 콜라의 합은 5 + 3 = 8입니다.
• 키파가 ‘ㄴ’자 모양으로 카루나네 집에 가고, 카루나가 ‘ㄱ’자 모양으로 키파네 집에 갑니다. 이때 키파는 2개의 코카콜라 제로를 주울 수 있고, 카루나는 4개의 펩시 제로를 주울 수 있어서 주울 수 있는 콜라의 합은 2 + 4 = 6입니다.

두 방법 중 콜라를 더 많이 주울 수 있는 방법은 전자이므로, 8을 출력합니다.