题目描述

圣诞老人准备了 $N$ 个信封，编号为 $1,2,\ldots,N$。第 $i$ 个信封中包含：

• $1$ 颗魔法钻石；
• $m_i$ 根火柴；
• 一张红色卡片，数字为 $r_i$；
• 一张蓝色卡片，数字为 $b_i$。

游戏按以下步骤进行：

1. 你先选择保留一部分信封，并丢弃其余信封。至少要保留一个信封。
2. 你立即收集所保留信封中的全部魔法钻石以及红、蓝卡片。
3. 设你收集到的所有红色数字之和为 $R$，所有蓝色数字之和为 $B$。圣诞老人会划出一块长为 $R$、宽为 $B$ 的矩形场地，你需要清除这块场地上的积雪，因此你的工作量等于矩形面积 $R\times B$。
4. 接下来，圣诞老人可以从你保留的信封中再丢弃任意一些，但至少保留一个信封。他也可以一个都不丢弃。
5. 将圣诞老人最终保留的每个信封中的火柴分别作为一堆，进行一局 Nim 游戏。你先手。每次操作可以选择一堆非空火柴，从中拿走任意正数根火柴。无法操作的玩家失败，也就是说，拿走最后一根火柴的玩家获胜。
6. 如果你赢得 Nim 游戏，就可以保留第 2 步中收集到的全部魔法钻石。

圣诞老人会在整个过程中采取最优策略：只要存在一种方式能够使他获胜，他就会选择这种方式。

你的首要目标是确保自己最终获胜，并在此前提下获得尽可能多的魔法钻石。由于每保留一个信封就能获得一颗魔法钻石，这等价于尽可能多地保留信封。在能够获得最多魔法钻石的所有方案中，你还希望第 3 步的工作量最小，即最小化 $R\times B$。

请输出这个最小面积。

输入格式

第一行输入一个整数 $N$，表示信封数量。

接下来 $N$ 行，第 $i$ 行输入三个整数 $m_i,r_i,b_i$，分别表示第 $i$ 个信封中的火柴数量、红色卡片数字和蓝色卡片数字。

输出格式

输出一个整数，表示在获得尽可能多魔法钻石的前提下，需要清理的最小矩形面积。

数据范围

• $1\le N\le 50$；
• $1\le m_i\le 10^6$；
• $1\le r_i\le 10^4$；
• $1\le b_i\le 10^4$。

答案可能超过 $32$ 位有符号整数范围，请使用 $64$ 位整数。

输入输出样例 #1

输入 #1

2
1 5 5
1 6 4

输出 #1

24

说明 #1

两个信封中的火柴数都为 $1$。如果两个信封都保留，圣诞老人可以保留这两个信封，此时两堆火柴的异或和为 $0$，你会输掉 Nim。因此最多只能保留一个信封。

保留第一个信封时面积为 $5\times5=25$；保留第二个信封时面积为 $6\times4=24$，故答案为 $24$。

输入输出样例 #2

输入 #2

3
1 4 9
2 5 8
3 6 7

输出 #2

153

说明 #2

最优方案是保留前两个信封，此时面积为 $(4+5)\times(9+8)=153$。

输入输出样例 #3

输入 #3

7
1 20 23
2 11 10
3 12 31
4 23 18
5 21 13
6 52 10
7 65 13

输出 #3

2255