跳蚤国王在地图中为你选出了一片 $n\times n$ 的方形荒漠，这里坐落着一座太阳能发电站，这将会作为“跳找”实验室的专用能源。

为了保证能源供给稳定，防止机房断电惨案，你被委派为发电站对接和监测工作的负责人。

你本以为只需要在数字化控制中心逛一逛就能完成任务，驾车来到电站之后，才发现问题有本质的不同。

电站年久失修，不仅控制系统无迹可寻，旧的线路也已经全部湮没于黄沙之中。幸运地是，所有光伏元件仍然保持完好——现在，要重新排布和连接这些光伏元件使其恢复运转。

给出 $n\times n$ 的 0/1 矩阵 $A$，其中 $A_{i, j}=1$ 表示位置 $(i,j)$ 有光伏元件，而 $0$ 表示没有元件。

受新的布线方案的限制，对光伏元件的分布有下列要求：

设第 $i$ 行的元件个数为 $c_{0,i}$ ，第 $i$ 列的元件个数为 $c_{1,i}$。

对于每个 $i$ ,给出 $dl_i, dr_i, k_i$ ,要求 $\left\lvert c_{0,i}-c_{1,i} \right\rvert \leq k$ 且 $c_{0,i}, c_{1,i} \in\left[dl_i,dr_i\right]$。即：要求第 $i$ 行和第 $i$ 列的元件个数在 $\left[dl_i, dr_i\right]$ 之间，且相差不超过 $k_i$。

给出 $n\times n$ 的矩阵 $C$，以 $C_{i, j}$ 表示改变位置 $(i,j)$ 上元件有/无状态的代价；特别地，若 $C_{i, j} = -1$，则表示 $(i,j)$ 位置的状态不可改变。

你深知：干活的进度一目了然，咕掉的空洞深不见底，而 deadline 总是比想象中近。于是，你计划尽快找到一组光伏元件的排布方案，在满足要求的前提下，使得总费用最小。

数据保证至少存在一组解。

输入格式

第一行一个正整数 $n$ 表示矩阵的大小。

下面 $n$ 行，每行 $n$ 个整数 $A_{i, j}$ 表示 0/1 矩阵 $A$。

下面 $n$ 行，每行 $n$ 个整数 $C_{i, j}$ 表示矩阵 $C$。

下面 $n$ 行，每行 $3$ 个整数 $dl_i, dr_i, k_i$。

输出格式

输出一行一个整数，表示最小所需的费用。

下面 $n$ 行，每行 $n$ 个数，描述 0/1 矩阵 $R$。第 $i$ 行第 $j$ 列的数表示 $R_{i, j}$。

矩阵 $R$ 即为你给出的对光伏元件分布方案。

如有多种方案，请输出任意一种即可。

样例一

input

4
0 1 0 0
1 1 0 0
1 0 1 0
1 0 1 1
171 -1 445 270
665 464 1204 885
-1 515 1156 893
636 455 1189 890
1 2 1
2 4 1
1 3 1
1 3 0

output

906
0 1 0 1
1 1 0 0
1 0 1 0
0 0 1 1

样例二

见下载文件中的 ex_elec2.in 与 ex_elec2.out。

该样例输入文件满足 $C_{i, j} \leq 0$。

样例三

见下载文件中的 ex_elec3.in 与 ex_elec3.out。

该样例输入文件满足 $k_i = 0$。

样例四

见下载文件中的 ex_elec4.in 与 ex_elec4.out。

该样例没有特殊性质。

限制与约定

对于所有的数据, $1\leq n\leq 100,\ 0\leq dl_i\leq dr_i\leq n,\ 0 \leq k_i \leq n,\ C_{i,j} \geq -1,\ \sum \lvert C_{i, j} \rvert \leq 2\times 10^9$。

特殊性质一栏留空表示没有特殊性质。

时间限制：$6\texttt{s}$

空间限制：$512\texttt{MB}$

下载

样例数据下载