#3699. GAL的数组

内存限制:256 MiB 时间限制:40 Sec

题目描述

GAL喜欢自娱自乐,这次她拿出了3*N的非负整数,分配到3个长度为N的数组A,B,C中。她对这个数组的元素进行各种各样的运算,探究各种各样的问题,乐在其中。
现在她定义三个数组的GAL值,GAL(A,B,C)=Σ(A[i]-B[i])*C[i],1 ≤ i ≤ N。她要你求出GAL(A,B,C)的最大值。

输入格式

第一行包含两个数T和N,T是数据组数。
接下来T行,每行包含3*N个数。

输出格式

输出包含T行,每行输出最大的GAL(A,B,C)。

样例

样例输入


			
1 2
4 1 8 2 0 5

样例输出


			
46

数据范围与提示

1 ≤ n ≤ 25