小 T 准备在家里摆放几幅画，为此他买来了 NNN 幅画和 NNN 个画框。为了体现他的品味，小 T 希望能合理地搭配画与画框，使得其显得既不过于平庸也不太违和。
对于第 iii 幅画与第 jjj 个画框的配对，小 T 都给出了这个配对的平凡度 Ai,jA_{i, j}Ai,j 与违和度 Bi,jB_{i, j}Bi,j 。整个搭配方案的总体不和谐度为每对画与画框平凡度之和与每对画与画框违和度的乘积。具体来说，设搭配方案中第 iii 幅画与第 PiP_iPi 个画框配对，则总体不和谐度为
小T希望知道通过搭配能得到的最小的总体不和谐度是多少。
输入文件第一行是一个正整数 TTT ，表示数据组数，接下来是 TTT 组数据。对于每组数据，第一行是一个正整数 NNN，表示有 NNN 对画和画框。第二到第 N+1N+1N+1 行，每行有 NNN 个非负整数，第 i+1i+1i+1 行第 jjj 个数表示 Ai,jA_{i, j} Ai,j。第 N+2N+2N+2 到第 2N+12N+12N+1 行，每行有 NNN 个非负整数，第 i+N+1i+N+1i+N+1 行第 jjj 个数表示 Bi,jB_{i, j}Bi,j 。
包含 TTT 行，每行一个整数，表示最小的总体不和谐度。
1 3 4 3 2 2 3 4 3 2 1 2 3 2 2 2 4 1 1 3
30
第 1 幅画搭配第 3 个画框，第 2 幅画搭配第 1 个画框，第 3 幅画搭配第 2 个画框，则总体不和谐度为 303030。
对于所有的数据，N≤70, T≤3, Ai,j≤200, Bi,j≤200N \leq 70,\ T \leq 3,\ A_{i, j} \leq 200,\ B_{i,j} \leq 200N≤70, T≤3, Ai,j≤200, Bi,j≤200。