题目背景

震惊！zbw 竟从 B 城监狱逃出！

作为 B 城的警察局长，你必须在 zbw 逃出你的管辖范围之前抓住他。

题目描述

B 城可视为一个 $n \times n$ 的方阵，其中监狱在 $(1,1)$，B 城唯一出城的出口在 $(n,n)$。每两个相邻的点（横坐标之差的绝对值 $+$ 纵坐标之间的绝对值 $=1$）之间都有一条无向的道路（没有斜着的道路）。你需要在一些道路上部下防守，使得无论 zbw 怎么走，都至少会经过其中的一条道路。

在一条 $(i,j)$ 到 $(i,j+1)$ 的道路上部下防守的花费是 $r_{i,j}$，在一条 $(i,j)$ 到 $(i+1,j)$ 的道路上部下防守的花费是 $d_{i,j}$，同时，在道路上部下防守会对人民的生活造成影响，在一条 $(i,j)$ 到 $(i,j+1)$ 的道路上部下防守对人民的生活造成的影响是 $x_{i,j}$，在一条 $(i,j)$ 到 $(i+1,j)$ 的道路上部下防守对人民的生活造成的影响是 $y_{i,j}$。

定义总花费为 $w$ ，总影响为 $e$ ，作为一名优秀的警察局长，你需要最小化 $w \times e$。

输入格式

第一行一个整数 $n$。

之后的 $n \times (n-1)$ 行，第 $i$ 行两个整数 $r_{i/n+1,(i-1)\bmod n+1}$， $x_{i/n+1,(i-1)\bmod n+1}$。

之后的 $n \times (n-1)$ 行，第 $i$ 行两个整数 $d_{i/n+1,(i-1)\bmod n+1}$ ，$y_{i/n+1,(i-1)\bmod n+1}$。

也就是说，先从上往下给从左往右给出竖边的信息，再从上往下给从左往右给出横边的信息。

如果不理解请见样例解释。

输出格式

一行一个整数，表示 $w \times e$ 的最小值。

3
8 3
5 2
1 1
4 2
1 2
7 5
7 2
6 1
5 4
2 3
1 4 
4 3

49

提示

如图，左上角为 $(1,1)$，右下角为 $(n,n)$， 其中蓝色数字表示 $r$, 红色数字表示 $x$, 黄色数字表示 $d$, 绿色数字表示 $y$。

最优方案为防守三条边，分别为：

$(2,2)-(2,3),(3,1)-(3,2),(3,2)-(3,3)$

三条边的边权分别是 $2,3$---$1,1$ ---$4,3$

答案为 $(1+2+4)\times (1+3+3)=49$

可以发现没有更优的做法。

本题采用捆绑测试。

对于所有数据 $1 \leq n \leq 400$，$0 \leq r_{i,j}, d_{i,j},x_{i,j} ,y_{i,j} \leq 10^3$。

数据于2020/3/4加强，卡掉部分复杂度错误的做法。