给您一个无向连通简单图,其中包含 $$$n$$$ 节点和 $$$m$$$ 边,其中边 $$$i$$$ 连接节点 $$$u_i$$$ 和 $$$v_i$$$,并附加两个正参数 $$$a_i$$$ 和 $$$b_i$$$。此外,您还会获得一个整数 $$$k$$$。
大小为 $$$m$$$ 的非负数组 $$$x$$$ 被称为 $$$k$$$ 生成树生成器,如果它满足以下条件:
- 考虑具有 $$$n$$$ 节点的无向多重图,其中边 $$$i$$$ 被克隆 $$$x_i$$$ 次(即有 $$$x_i$$$ 边连接 $$$u_i$$$ 和 $$$v_i$$$)。可以将此图的边划分为 $$$k$$$ 生成树,其中每条边恰好属于一个生成树$$$^\dagger$$$。
此类数组 $$$x$$$ 的成本定义为 $$$\sum_{i = 1}^m a_i x_i^2 + b_i x_i$$$。求 $$$k$$$ 生成树生成器的最小成本。
$$$^\dagger$$$ (多)图的生成树是图的边的子集,这些边形成连接图的所有顶点的树。
输入
每个测试包含多个测试用例。第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 500$$$) — 测试用例的数量。测试用例的描述如下。
每个测试用例的第一行包含三个整数 $$$n$$$、$$$m$$$ 和 $$$k$$$ ($$$2 \le n \le 50, n - 1 \le m \le \min(50, \frac{n(n - 1)}{2}), 1 \le k \le 10^7$$$) — 图中的节点数,图中的边数,以及 $$$k$$$ 生成树生成器的参数。
每个测试用例接下来的 $$$m$$$ 行包含四个整数 $$$u_i$$$、$$$v_i$$$、$$$a_i$$$ 和 $$$b_i$$$ ($$$1 \le u_i, v_i \le n, u_i \neq v_i, 1 \le a_i, b_i \le 1000$$$) — 边 $$$i$$$ 的端点及其两个参数。保证图是简单且连通的。
保证所有测试用例的 $$$n^2$$$ 之和与 $$$m^2$$$ 之和不超过 $$$2500$$$。
输出
对于每个测试用例,输出一个整数:$$$k$$$生成树生成器的最小成本。
示例
输入 #1
4 5 5 1 4 3 5 5 2 1 5 7 2 4 6 2 5 3 3 5 2 5 2 9 5 5 3 4 3 5 5 2 1 5 7 2 4 6 2 5 3 3 5 2 5 2 9 2 1 10000000 1 2 1000 1000 10 15 10 7 1 7 6 5 8 6 6 4 8 2 2 4 3 10 9 10 8 3 4 4 6 6 1 5 4 1 3 9 3 4 3 8 3 9 9 7 5 10 3 2 1 3 4 6 1 6 4 2 5 7 3 10 7 2 1 8 2 6 8
输出 #1
38 191 100000010000000000 2722
注意
在第一个测试用例中,有效的 $$$1$$$ 生成树生成器为 $$$x = [1, 1, 1, 1, 0]$$$,如下图所示。该生成器的成本为 $$$(1^2 \cdot 5 + 1 \cdot 5) + (1^2 \cdot 5 + 1 \cdot 7) + (1^2 \cdot 6 + 1 \cdot 2) + (1^2 \cdot 3 + 1 \cdot 5) + (0^2 \cdot 4 + 0 \cdot 9) = 38$$$。可以证明没有其他发电机的成本更低。
$$$x 的 $$$1$$$ 生成树分区 = [1, 1, 1, 1, 0]$$$
在第二个测试用例中,有效的 $$$3$$$ 生成树生成器为 $$$x = [2, 3, 2, 2, 3]$$$,如下图所示。该生成器的成本为 $$$(2^2 \cdot 5 + 2 \cdot 5) + (3^2 \cdot 5 + 3 \cdot 7) + (2^2 \cdot 6 + 2 \cdot 2) + (2^2 \cdot 3 + 2 \cdot 5) + (3^2 \cdot 4 + 3 \cdot 9) = 191$$$。可以证明没有其他发电机的成本更低。
$$$x 的 $$$3$$$ 生成树分区 = [2, 3, 2, 2, 3]$$$