题目描述

两个人的花环上一共有 $\red{n }$种花。首先，$\red{Vani }$会煞有介事地向妹子解释说某两种花配对的 话有着怎样的意义，并且 $\red{Vani }$会解释清楚所有 $\red{C_n^2}$个配对的含义。严格地说，$\red{Vani }$声明了一 个整数矩阵 $\red{A ，}$ $\red{A_{ij} }$的值表示花$\red{i }$和花 $\red{j }$配对的话会增加的花环的契合度。这个值如果是正 的，就表示这样配对有着正面意义，否则表示负面意义。显然对于任意的$\red{1<=i, j <= n ，}$有 $\red{A_{ij} = A_{ji} }$。

之后，$\red{Vani }$必须考虑自己的理论的可信度。$\red{Vani }$觉得，只有$\red{\sum\limits_{i=1}^{n}{\sum\limits_{j=1}^{n}{A_{ij}=0}}，}$并且对于 任意的$\red{1<=i, j <= n，}$都满足 $\red{L_{ij} <= A_{ij} <= R_{ij} ，}$他的一套说辞才是可信的。所以，$\red{Vani }$必须使得 自己的解释满足条件。

$\red{Vani }$发现两人的花环上花朵的数目相同，并且都有一个蝴蝶结。于是他从蝴蝶结开始 沿顺时针方向将花朵编号，并且将两个花环对应位置上的花朵进行比较。每出现一个花朵对 $\red{(i, j) ，}$两个花环之间的契合度就会增加 $\red{A_{ij} }$。由于花环是确定的，你的任务就是帮助 $\red{Vani}$ 确定一个满足要求的矩阵 $\red{A ，}$使得两个花环的契合度达到最大。$\red{Vani }$向你保证一定存在一 个满足全部要求的矩阵 $\red{A ，}$并且你只需要给出最大可能的契合度。注意这个最大的契合度 也有可能是 $\red{0 }$甚至是负数。

输入格式

显然，花环上花朵的排布并不重要，这个问题需要的只是各个花朵对的数目。于是我们 将按照以下格式给出所需的信息。

输入文件的行从 $\red{1 }$开始标号。

第一行包含一个整数 $\red{n ，}$表示花朵的种类数。

之后 $\red{n }$行，每行$\red{n }$个整数。第$\red{i }$行第 $\red{j }$个整数为$\red{k }$就表示花朵对$\red{(i -1, j) }$出现了$\red{k }$次。

之后 $\red{n }$行，每行$\red{n }$个整数。第$\red{i }$行第 $\red{j }$个整数为$\red{k }$就表示 $\red{L _{(i-n-1)j}=k }$。

之后 $\red{n }$行，每行$\red{n }$个整数。第$\red{i }$行第 $\red{j }$个整数为$\red{k }$就表示 $\red{L _{(i-2n-1)j}=k}$。

输出格式

输出一个整数，表示最大可能的契合度。

样例

输入样例

4 
7 0 1 0 
0 0 0 0 
1 0 0 0 
0 0 0 0 
1 -10 -10 -10 
-10 1 -10 -10 
-10 -10 1 -10 
-10 -10 -10 1 
10 10 10 10 
10 10 10 10 
10 10 10 10 
10 10 10 10

输出样例

90

提示

对于 $\red{20\% }$的数据，满足 $\red{n<=5,-10<=L_{ij}<R_{ij}<=10 }$。

对于 $\red{50\% }$的数据，满足 $\red{n<=50,-100<=L_{ij}<R_{ij}<=100}$。

对于 $\red{100\% }$的数据，满足 $\red{4<=n<=500,-10000<=L_{ij}<R_{ij}<=10000，}$对于任意的 $\red{1<=i, j <= n，}$满足 $\red{max( L_{ij},L_{ji} ) min( R_{ij} , R_{ji}) }$。花朵对的数目不为负，且不大于 $\red{100000}$。