UVA1172 The Bridges of Kolsberg

King Beer 统治着一个非常难以管理的地区，该地区由许多城市组成，这些城市对操作系统有着非常固执的信仰，并且贸易往来频繁。这些城市分布在 Klsberg 河的南北两岸。由于河流宽阔且危险，这些城市在经济上彼此隔离。  King Beer 希望建造一些桥梁连接河流的两岸来发展经济。他被告诫不要在不同操作系统信仰的城市之间建造桥梁（这些人彼此非常敌视）。因此，他只能建造连接相同操作系统信仰城市的桥梁（即使这些桥梁会很长或形状奇怪）。然而，技术上无法建造相互交叉的桥梁。(如上图，被指出的两处区域被认为是不合法的建造方式) 一座桥梁的经济价值是它所连接的两个城市的贸易值之和。国王希望在最大化所有桥梁价值总和的同时，最小化需要建造的桥梁数量。 现在给定两岸的城市集合，希望你输出所有桥梁价值的最大可能总和以及实现这一目标所需的最小桥梁数量。

第一行是一个整数，表示测试用例的数量 $T$。 --- 对于每个测试用例，第一行是一个不超过 $1000$ 的非负整数 $N$，表示北岸城市的数量。 接下来 $N$ 行，每行有两个字符串和一个非负整数，分别代表北岸第 $i$ 座城市的名称 $name_i$、操作系统信仰 $sys_i$ 和贸易值 $tra_i$。 其中 $name_i$、$sys_i$ 的长度均不超过$10$， $0

对于每个测试用例，输出一行，包含所有桥梁价值的最大可能总和 $sum$ 以及所需的桥梁数量 $num$，中间用空格隔开并在结尾换行。