一个有向无环道路网络由有向道路段（边）组成，每条边连接 $N$ 个交叉口（顶点）中的两个。在道路段上行驶所需的时间总是正数，并且与使用该路段 $s$ 的车辆数量 $C$ 呈线性关系：

$$T(s) = a_s C + b_s$$

其中 $a_s$ 和 $b_s$ 是两个以单精度浮点数表示的常数，用于描述道路段 $s$ 的属性。通过交叉口所需的时间为 $0$。

一定数量的车辆必须在该道路网络中从顶点 $0$ 行驶到顶点 $N-1$。每辆车都自私地选择其路线以减少自身的旅行时间；每辆车也知道所有其他车辆都会自私地选择它们的路线。你需要编写一个程序，计算从起点到终点的每条可能路径上将有多少辆车行驶，以及在这些路径上行驶所需的时间。

输入格式

输入包含多个测试用例。

第一行包含测试用例的数量。

接下来的行包含测试用例的详细说明。每个测试用例的第一行包含顶点数、边数和车辆数，中间用空格分隔。

此后，每条边占一行，包含以下由空格分隔的字段：起点顶点、终点顶点、$a_s$ 和 $b_s$。

输出格式

针对每个测试用例，输出一行，指定网络中任意车辆的最小旅行时间，向下取整到最接近的整数。

样例

输入格式 1

2
4 4 4000
0 1 0.01 0
0 2 0 45.1
1 3 0 45.1
2 3 0.01 0
4 5 4000
0 1 0.01 0
0 2 0 45.1
1 3 0 45.1
1 2 0 0
2 3 0.01 0

输出格式 1

65
80

说明

第一个输入包含 $4$ 个顶点和 $4$ 条边；$4000$ 辆车必须从顶点 $0$ 行驶到顶点 $3$。为了获得最短的旅行时间，车辆将选择两条可能路径 $(0-1-3)$ 和 $(0-2-3)$ 之一，使得两条路径上的车辆数相等；因此最小旅行时间为 $\lfloor 0.01 \times 2000 + 45.1 \rfloor = 65$。

第二个输入与第一个类似，只是在顶点 $1$ 和 $2$ 之间增加了一条零成本的边。在这种情况下，所有车辆都会自私地选择路径 $(0-1-2-3)$，最小旅行时间为 $80$。