题目描述

给定一个带非负容量的无向图。

对于两个不同的顶点 $s,t$，一个 $s-t$ 割是把所有顶点划分为两个集合，并保证 $s,t$ 分属不同集合。割的容量等于所有跨越两个集合的边的容量之和。

记 $minCut(s,t)$ 为所有 $s-t$ 割中的最小容量。

现在有若干询问。每次给出一个整数 $x$，请计算有多少个无序点对 $(s,t)$ 满足 $minCut(s,t)\le x$。

图中允许两个顶点之间存在多条边，也允许图不连通。

输入格式

第一行一个整数 $T$，表示测试数据组数。

对于每组测试数据：

1. 第一行两个整数 $n,m$，表示顶点数和边数；
2. 接下来 $m$ 行，每行三个整数 $u,v,c$，表示一条连接 $u,v$、容量为 $c$ 的无向边；
3. 接下来一行一个整数 $q$；
4. 接下来 $q$ 行，每行一个整数 $x$，表示一次询问。

输出格式

对于每次询问输出一行，一个整数，表示满足条件的无序点对数量。

相邻两组测试数据的输出之间打印一个空行。

样例

1
5 0
1
0

10

数据范围

• 数据组 1：$T\le15$，$n\le40$，$m\le400$，$q\le10$；
• 数据组 2：$T\le20$，$n\le150$，$m\le3000$，$q\le30$；
• 边容量不超过 $10^6$；
• 允许重边。