[HNOI2014]画框
题号：NC20109
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

小T准备在家里摆放几幅画，为此他买来了N幅画和N个画框。为了体现他的品味，小T希望能合理地搭配画与画框，使得其显得既不过于平庸也不太违和。对于第i幅画与第j个画框的配对，小T都给出了这个配对的平凡度Aij 与违和度Bij 。整个搭配方案的总体不和谐度为每对画与画框平凡度之和与每对画与画框违和度的乘积。具体来说，设搭配方案中第i幅画与第Pi个画框配对，则总体不和谐度为
  
小T希望知道通过搭配能得到的最小的总体不和谐度是多少。

输入描述:

输入文件第 行是一个正整数T ，表示数据组数，接下来是T组数据。 
对于每组数据，第1行是一个正整数N，表示有N对画和画框。 
第2到第N+1行，每行有N个非负整数，第i+1行第j个数表示Aij 。 
第N+2到第2*N+1行，每行有N个非负整数，第i+N+1行第j个数表示Bij 。

输出描述:

包含T行，每行一个整数，表示最小的总体不和谐度
示例1

输入

复制 
1
3
4 3 2
2 3 4
3 2 1
2 3 2
2 2 4
1 1 3

输出

复制 
30

备注:

对于100%的数据，。