Description

C国内T局势日趋紧张，可能会有战争爆发。为了防御袭击，军队准备修建一个火力防御网。

一个火力防御网由一个总部，若干中继站，和工事组成。 军队一共准备布置N个前线工事。每个前线工事都直接与总部相连或通过若干补给中继站与总部相连。任意工事间，工事与中继站间，中继站与中继站间都连通。从总部出发，到达任意一个工事所途经的所有中继站按照访问先后顺序依次命名为1级中继，2级中继。。。保证每个中继站都只会有一个级数。出于安全和补给的考虑，总部和中继站最多只能连接M个下级中继站或者前线工事（或者少于M个）。工事不会再有下级的中继或工事，中继或工事都只有一个上级。总部和一个中继站与下级中继站或工事连接时有M种可选择的方案，方案的费用依次为：C1，C2...CM。且每种方案在总部或一个中继站处最多只能选用一次（也可以不选用某种方案）。修建一个中继站的费用Vi等于上级中继连接此中继的方案的费用乘以此中继的所有间接或直接的下级工事的个数。每个工事的费用W等于上级中继连接此工事的方案的费用。一个火力防御网的总费用等于从总部到每个工事所经过的工事和中继的费用总和（如果一个中继在从总部到多个不同的工事的路上都出现，每次都要计算中继站的费用；即如果中继i直接或间接连接着m个下级工事，那么计算防御网总费用时应该加上m*Vi）。 现在给定N，M，和C1...CM。 请算出建设一个火力防御网所需要的最少费用。

Input

第一行为测试数据的个数。

接下来每个测试点的第一行是两个正整数n,m( 1 <= n <= 1024 , 1 <= m <= 160) ，接下来的m行每行有一个正整数Ci。

Output

每个测试点的输出占一行，仅有一个正整数，表示最小费用.

You may assume that the result won’t exceed signed longint.

1
4 3
3
1
2

12

Hint

对此题样例的说明：

最优方案为： 总部O以费用为1的方案连接1阁下级中继M,以费用为2，3的方案分别连接2个工事P1,P2 中继M以费用1，2的方案再连接2个工事P3,P4 P1的费用为2 P2的费用为3 P3的费用为1 P4的费用为2 M的费用为1*2=2（由2个下级工事） 最后计算总费用时，因为M有2个直接（或间接）连接的下级工事，所以还需要乘以2（于是2*2=4） 总费用是2+3+1+2+4=12

特别注意！ 实际上，如果一个中继有N个下级，而它的上级以费用C方案连接它，那么应该把CNN加到总费用中去

Source

LIANGLIANG@POJ