SOLUTION
想一下最优情况下肯定让平路或下坡尽量多，于是不难想到这样构图：包括左上角的一部分全部为(0)，包括右下角的一部分全部为(1)，于是现在问题转化为求那个分界线是什么。
画一画图，发现每条分界线对应一组割，转化成了最小割模型，然后因为数据范围对(dinic)不友好，化成对偶图跑最短路就行了
注意不能只考虑向下和向右的边
代码：
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <random>
#include <string>
#include <vector>
#include <cmath>
#include <ctime>
#include <queue>
#include <map>
#include <set>
#define IINF 0x3f3f3f3f3f3f3f3fLL
#define u64 unsigned long long
#define pii pair<int, int>
#define mii map<int, int>
#define u32 unsigned int
#define lbd lower_bound
#define ubd upper_bound
#define INF 0x3f3f3f3f
#define vi vector<int>
#define ll long long
#define mp make_pair
#define pb push_back
#define is insert
#define se second
#define fi first
#define ps push
#define $SHOW(x) cout << #x" = " << x << endl
#define $DEBUG() printf("%d %s
", __LINE__, __FUNCTION__)
namespace FastIO {
const int SIZE = (1 << 21) + 1;
char ibuf[SIZE], *iS, *iT, obuf[SIZE], *oS = obuf, *oT = oS + SIZE - 1, c, qu[55];
int qr;
#define gc() (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, SIZE, stdin), (iS == iT ? EOF : *iS++)) : *iS++) // getchar
inline void flush() { fwrite(obuf, 1, oS - obuf, stdout); oS = obuf; } // print the remaining part
inline void putc(char x) { *oS++ = x; if (oS == oT) flush(); } // putchar
inline void wrap() { *oS++ = '
'; if (oS == oT) flush(); } // wrap
template <class I>
inline void gi(I &x) { // input an integer
I sign = 1;
for (c = gc(); c < '0' || c > '9'; c = gc()) if (c == '-') sign = -1;
for (x = 0; c <= '9' && c >= '0'; c = gc()) x = x * 10 + (c & 15);
x *= sign;
}
inline int gi() { // input an int
int x, sign = 1;
for (c = gc(); c < '0' || c > '9'; c = gc()) if (c == '-') sign = -1;
for (x = 0; c <= '9' && c >= '0'; c = gc()) x = x * 10 + (c & 15);
return x * sign;
}
inline ll gl() { // input an long long
ll x, sign = 1;
for (c = gc(); c < '0' || c > '9'; c = gc()) if (c == '-') sign = -1;
for (x = 0; c <= '9' && c >= '0'; c = gc()) x = x * 10 + (c & 15);
return x * sign;
}
template <class I>
inline void print(I &x) { // print a integer
if (!x) putc('0');
while (x) qu[++qr] = x % 10 + '0', x /= 10;
while (qr) putc(qu[qr--]);
}
template <class I>
inline void println(I &x) { // print a integer and wrap
if (!x) putc('0');
while (x) qu[++qr] = x % 10 + '0', x /= 10;
while (qr) putc(qu[qr--]);
wrap();
}
}
using namespace std;
// using namespace FastIO;
#define MAXN 250000
struct Edge {
int next, to, w;
}e[20 * MAXN + 5];
int n, S = MAXN + 1, T = MAXN + 2;
int head[MAXN + 5], eid, d[MAXN + 5];
bool inq[MAXN + 5];
void addEdge(int x, int y, int w) {
e[++eid].next = head[x];
e[eid].to = y;
e[eid].w = w;
head[x] = eid;
}
void spfa() {
queue<int> q;
memset(d, 0x3f, sizeof d);
d[S] = 0;
q.push(S);
inq[S] = 1;
while(!q.empty()) {
int u = q.front(); q.pop();
inq[u] = 0;
for (int i = head[u]; i; i = e[i].next) {
int v = e[i].to, w = e[i].w;
if (d[v] > d[u] + w) {
d[v] = d[u] + w;
if (!inq[v]) q.push(v), inq[v] = 1;
}
}
}
}
int main() {
scanf("%d", &n);
for (int i = 1, x; i <= n; ++i)
scanf("%d", &x), addEdge(i, T, x);
for (int i = 1; i < n; ++i)
for (int j = 1, x; j <= n; ++j)
scanf("%d", &x), addEdge(i * n + j, (i - 1) * n + j, x);
for (int i = 1, x; i <= n; ++i)
scanf("%d", &x), addEdge(S, (n - 1) * n + i, x);
for (int i = 1, x; i <= n; ++i) {
scanf("%d", &x);
addEdge(S, (i - 1) * n + 1, x);
for (int j = 1; j < n; ++j)
scanf("%d", &x), addEdge((i - 1) * n + j, (i - 1) * n + j + 1, x);
scanf("%d", &x);
addEdge(i * n, T, x);
}
for (int i = 1, x; i <= n; ++i)
scanf("%d", &x), addEdge(T, i, x);
for (int i = 1; i < n; ++i)
for (int j = 1, x; j <= n; ++j)
scanf("%d", &x), addEdge((i - 1) * n + j, i * n + j, x);
for (int i = 1, x; i <= n; ++i)
scanf("%d", &x), addEdge((n - 1) * n + i, S, x);
for (int i = 1, x; i <= n; ++i) {
scanf("%d", &x);
addEdge((i - 1) * n + 1, S, x);
for (int j = 1; j < n; ++j)
scanf("%d", &x), addEdge((i - 1) * n + j + 1, (i - 1) * n + j, x);
scanf("%d", &x);
addEdge(T, i * n, x);
}
spfa();
printf("%d
", d[T]);
return 0;
}