题目背景

小 $\mathfrak{f}$ 的家乡 A 市最近开通了地铁。

题目描述

A 市共有 $n (2\le n \le 10^5)$ 个居民点，第 $i$ 个居民点的人口为 $s_i (1 \le s_i \le 10^7)$，同时有 $n-1$ 条双向道路，构成一棵树，第 $i$ 条双向道路连接居民点 $u_i$ 和 $v_i$，人步行走过这条道路需要 $w_i (1 \le w_i\le 10^7)$ 的时间。

现 A 市政府决定开通一条地铁线路。地铁线路是树上的一条简单路径，若路径经过第 $i$ 条道路，那么地铁从这条道路下方经过只需要 $w_i^{\prime} (1 \le w_i^{\prime} \le 10^7)$ 的时间，同时，地铁的进出站共需要花费 $t (0 \le t \le 10^7)$ 的时间。

已知，若一个人从一个居民点前往另一个居民点，如果这条路径与地铁经过的路径有至少一条公共边，那么就一定会选择尽可能多地乘坐地铁。如果没有公共边，那么就会选择完全步行。题目保证对于第 $i$ 条道路有 $w_i^{\prime} \le w_i - t$。 我们认为，如果两个居民点的人口的乘积越大，那么有人想要在它们之间流动的可能性也越大。

现在，小 $\mathfrak{f}$ 想知道在所有 $\frac{n(n-1)}{2}$ 种建造地铁线路的方案中，$\sum_{a=1}^{n-1}\sum_{b=a+1}^{n}(s_a \cdot s_b \cdot d_{a,b})$ 的最小值，其中 $d_{a,b}$ 表示从居民点 $a$ 前往 $b$（或者从 $b$ 前往 $a$，两者是相等的）所需要的时间。

但是他不会，所以他来求助万能的你。

输入格式

第一行，三个用空格分隔的整数 $id,n,t$，表示子任务编号，居民点个数和进出站所需要花费的时间。

接下来 $n$ 行，每行一个整数 $s_i$，表示每个居民点的人口。

接下来 $n - 1$ 行，每行四个用空格分隔的整数 $u_i,v_i,w_i,w_i^{\prime}$，表示每条道路的两个端点，步行所需时间和地铁所需时间。

输出格式

一行，一个整数，表示所求的最小值。

答案可能超过 $64$ 位整数的表示范围，如果你使用 C/C++，建议使用 __int128 类型，它的表示范围为 $\left[-2^{127},2^{127}-1\right]$，无法直接输入输出。

如果你使用其他编程语言，建议使用该语言自带的高精度整数（如果有）或者手写高精。

0 5 0
9
9
3
2
3
1 2 7 6
1 3 8 5
1 4 6 5
2 5 9 9

2262

0 10 86
50
6
84
50
83
67
93
55
93
70
1 2 94 7
1 3 97 4
1 10 98 12
2 4 89 1
2 7 98 1
4 5 99 13
4 6 96 5
5 8 95 5
5 9 97 7

33600416

提示

样例 $1$ 解释：

修建地铁前如下图所示：

一种最优的修建地铁的方案为从 $2$ 到 $3$ 修建地铁。如下图所示（实线表示修建了地铁）：

从 $1$ 到 $2$ 经过地铁，所需时间为：$6+0=6$，对答案的贡献为：$9\times9\times6=486$。

从 $1$ 到 $3$ 经过地铁，所需时间为：$5+0=6$，对答案的贡献为：$9\times3\times5=135$。

从 $1$ 到 $4$ 不经过地铁，所需时间为：$6$，对答案的贡献为：$9\times2\times6=108$。

从 $1$ 到 $5$ 经过地铁，所需时间为：$6+9+0=15$，对答案的贡献为：$9\times3\times15=405$。

从 $2$ 到 $3$ 经过地铁，所需时间为：$6+5+0=11$，对答案的贡献为：$9\times3\times11=297$。

从 $2$ 到 $4$ 经过地铁，所需时间为：$6+6+0=12$，对答案的贡献为：$9\times2\times12=216$。

从 $2$ 到 $5$ 不经过地铁，所需时间为：$9$，对答案的贡献为：$9\times3\times9=243$。

从 $3$ 到 $4$ 经过地铁，所需时间为：$5+6+0=11$，对答案的贡献为：$3\times2\times11=66$。

从 $3$ 到 $5$ 经过地铁，所需时间为：$5+6+9+0=20$，对答案的贡献为：$3\times3\times20=180$。

从 $4$ 到 $5$ 经过地铁，所需时间为：$6+6+9+0=21$，对答案的贡献为：$2\times3\times21=126$。

综上，答案为：$486+135+108+405+297+216+243+66+180+126=2262$。

可以证明不存在更优的修建地铁的方案。

本题采用捆绑测试且使用子任务依赖。

编号	分值	$n \le$	性质	依赖
$0$		N/A	样例	无
$1$	$5$	$10$	无
$2$		$500$		$1$
$3$	$10$	$5000$		$1,2$
$4$	$30$	$10^5$	A	无
$5$			B
$6$	$20$		C
$7$	$15$		D
$8$	$10$		无	$0,1,2,3,4,5,6,7$

特殊性质 A：$t=0$

特殊性质 B：$u_i=i,v_i=i+1$

特殊性质 C：每一个点的度数都不超过 $100$

特殊性质 D：$u_i=1,v_i=i+1$