问题描述 故事基于我的一个真实梦境，规则描述完全是我梦到的内容。在理解清楚之前请不要开始编码。 小猫正在为女朋友准备一条珠链 —— 一条手工制作（DIY）的项链来表达爱意。他的大盒子里有 $N（4 ≤ N ≤ 400）$种不同的珠子（木质、塑料、玻璃、珍珠、钻石！？等），这些是制作项链的唯一材料。 出于好奇，小猫不假思索地做了两串珠子，一串给自己，一串给女朋友 —— 称为 “情侣项链”。女朋友会喜欢吗？根据市场调查，项链的美观程度取决于两串项链的相似度。每条项链可视为由 $M$ 颗珠子组成的链表。 两颗珠子的相似度构成一个 $N×N$ 的表格。例如：

两串项链的相似度因子由 $M$ 对对应珠子的相似度之和决定。例如： 项链 1：$WPPWW$ 项链 2：$DPDDW$ 相似度因子 = $Table [W,D] + Table [P,P] + Table [P,D] + Table [W,D] + Table [W,W] = -7 + 1 + 1 + (-7) + 6 = -6$ 由于我们不太关心项链的具体构成（此外，小猫想在女朋友生日前保密），我们用另一个 $N×N$ 的表格记录不同珠子对的出现次数：

给定表格 Pairs，但需要确定表格 Table 的值，目标是使两串项链的相似度因子尽可能大。Table 还需满足约束：$Low [i, j] ≤ Table [i, j] ≤ Up [i, j]$（给定的上下界）。显然，$Low [i, j] = Low [j, i] 且 Up [i, j] = Up [j, i]$。 梦境背景：小猫有特殊魔法，他可以一次将所有珍珠变成钻石，所有钻石变成珍珠。更准确地说，他可以一次交换两种不同的珠子。这就是为什么 $N×N$ 的 Pairs 表是固定的，但我们可以自己修改 Table 表！

输入

输入包含多个测试用例。每个测试用例格式如下： 每个测试用例以整数 $N（4 ≤ N ≤ 400）$开头，接下来有 $N$ 行。第 $i$ 行包含 $3×(N–i+1)$ 个整数，其中第 j 个三元组表示 $Pairs [i, j+i–1]、Low [i, j+i–1] 和 Up [i, j+i–1]$。 约束条件：$-10000 ≤ Low [i, j] < Up [i, j] ≤ 10000，-100000 ≤ Pair [i, j] ≤ 100000$。输入保证存在解。

输出

对每个测试用例，输出一行一个整数，表示能生成的最大相似度。

输入数据 1

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


4
0 1 10  2 -10 10  2 -10 10  2 -10 10
        0 1 10    2 -10 10  2 -10 10
                  0 1 10    2 -10 10
                            0 1 10

输出数据 1

90
-4

提示 第一个样例的最优 Table 表： 来源 POJ Monthly--2006.01.22, Zeyuan Zhu