题目描述

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

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

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

输入格式

第一行输入一个整数 \(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