有 棵 个点的树，它们都分别相同地用 条边连接起来，也就是这 棵树的 结构完全相同。
接下来再在树与树之间添加 条边使得这 棵树连通，则得到一棵点数为 的大树，以第一棵树的根作为整棵大树的根。
在树上通过一条边 时，若 ，则花费是 ，否则花费是 。
求在这棵大树上任意一点 通过树上最短路径到达任意一点 的 最大花费 以及能达到这个最大花费的 的 数量。
第一行一个整数 表示数据组数，对于每组数据：
第一行两个整数 ，表示每棵树的点数以及树的数量。
接下来 行，每行两个数 ，表示每棵树上都有一条边 。
接下来 行，每行四个数 ，表示第 棵树的结点 与第 棵树的结点 之间有连边。
共 行，第 行两个整数，分别表示最大花费和对应点对的数量。
2 3 3 3 1 2 1 3 1 2 2 1 3 2 1 3 8 3 1 2 3 4 3 3 1 3 1 2 3 6 2 1 3 8 3 7 3 5 3 7 3 6 3 7 2 8 3 2 2
11 2 22 3
对于 的数据，，，，。
