跳蚤国王在地图中为你选出了一片 $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$ ,给出 $d{l}_i,d{r}_i,k_i$ ,要求 $|c_{0,i}-c_{1,i}|\le k$ 且 $c_{0,i},c_{1,i}\in [d{l}_i,d{r}_i]$。即：要求第 $i$ 行和第 $i$ 列的元件个数在 $[d{l}_i,d{r}_i]$ 之间，且相差不超过 $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$ 个整数 $d{l}_i,d{r}_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}\le 0$。

样例三

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

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

样例四

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

该样例没有特殊性质。

限制与约定

对于所有的数据, $1\le n\le 100,0\le d{l}_i\le d{r}_i\le n,0\le k_i\le n,C_{i,j}\ge -1,\sum |C_{i,j}|\le 2\times {10}^9$。

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

时间限制：$6\mathtt{\text{s}}$

空间限制：$512\mathtt{\text{MB}}$

下载

样例数据下载