J. 心里阴影

kimoyami 正在忙着给春季校赛出题，他想出了 $n$ 道题目，每道题目需要花费 $a_i$ 的精力出题。因为 kimoyami 心狠手辣，每道题都会对选手造成一定的心理阴影，具体表现为一个以 $(0,0)$ 和 $(x_i,y_i)$ 为顶点的矩形,其中 $x_i$ 和 $y_i$ 都是正整数。kimoyami 的愉悦值为所有矩形的面积并减去出题所耗费的精力，请你帮助残忍的 kimoyami 选择适当的题目最大化他的愉悦值。

注意：由于 kimoyami 出题水平很高，保证不存在两个矩形使得其中一个被另外一个完全包含!

第一行一个整数 $T(1\leq T\leq 10)$ 代表数据组数

每组数据第一行两个数 $n(1\leq n \leq 5*10^3)$。

下面 $n$ 行，每行三个数 $x_i,\ y_i,\ a_i(1\leq x_i,y_i \leq 10^9,0\leq a_i \leq x_i \times y_i)$。

$T$ 行每行一个整数表示最大愉悦值。

输入样例

1
3
1 5 0
3 4 2
5 1 3

输出样例

11

样例解释

选取第一个和第二个矩形，总面积为 $13$，消耗精力为 $2$。