题目描述

你有一个顶级安全箱，可以抽象为长和宽均为 $3$ 的矩形。

有 $n$ 件物品，第 $i$ 件物品可以抽象为长为 $a_i$ ，宽为 $b_i$ 的矩形，价值为 $v_i$ ，你可以将其水平或者旋转 $90°$ 后放置于安全箱内任意位置，物品必须完全在安全箱内部。

你可以选择若干件物品放进安全箱内，但是不能有两件物品有重叠部分，你需要最大化安全箱中物品的总价值。

输入描述

第一行输入一个整数 $T$ 表示测试数据组数。

对于每组数据：

第一行一个正整数 $n$ 。

接下来 $n$ 行，每行三个整数 $a_i,b_i,v_i$ 。

令 $N_{tot}$ 表示所有测试组 $n$ 之和。

$1 \le T \le 10000,1 \le N_{tot} \le 10^6$ 。

$1 \le n \le 10^6, 1 \le a_i,b_i \le 3,1 \le v_i \le 10^8$ 。

输出描述

对于每组数据：

输出一行一个整数，表示最大的总价值。

样例

2
5
2 3 20
1 3 5
1 2 4
1 1 4
1 3 6
2
1 1 13141314
3 3 6947311

28
13141314