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$，两者是相等的）所需要的时间。
但是他不会，所以他来求助万能的你。
## Input
第一行，三个用空格分隔的整数 $id,n,t$，表示子任务编号，居民点个数和进出站所需要花费的时间。
接下来 $n$ 行，每行一个整数 $s_i$，表示每个居民点的人口。
接下来 $n - 1$ 行，每行四个用空格分隔的整数 $u_i,v_i,w_i,w_i^{\prime}$，表示每条道路的两个端点，步行所需时间和地铁所需时间。
## Output
一行，一个整数，表示所求的最小值。
答案可能超过 $64$ 位整形表示范围，您可以使用 `__int128` 类型，其表示范围为 $[-2^{127},2^{127}-1]$。
以下为 `__int128` 类型的输出模板：
```cpp
#include <bits/stdc++.h>
using namespace std;
__int128 ans;
int main() {
/* Your code here */
string str;
if (!ans) {
str = "0";
} else {
str = "";
while (ans) {
str = ((char)(48 + ans % 10)) + str;
ans /= 10;
}
}
cout << str << endl;
return 0;
}
```
[samples]
## Background
小 $\mathfrak{f}$ 的家乡 A 市最近开通了地铁。
## Note
**样例 $1$ 解释：**
修建地铁前如下图所示：
一种最优的修建地铁的方案为从 $2$ 到 $3$ 修建地铁。如下图所示（实线表示修建了地铁）：
从 $1$ 到 $2$ 经过地铁，所需时间为：$6+0=6$，对答案的贡献为：$9\times9\times6=486$。
从 $1$ 到 $3$ 经过地铁，所需时间为：$5+0=5$，对答案的贡献为：$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$ | $0$ | N/A | 样例 | 无 |
| $1$ | $5$ | $10$ | 无 | 无 |
| $2$ | $5$ | $500$ | 无 | $1$ |
| $3$ | $10$ | $5000$ | 无 | $1,2$ |
| $4$ | $30$ | $10^5$ | A | 无 |
| $5$ | $5$ | $10^5$ | B | 无 |
| $6$ | $20$ | $10^5$ | C | 无 |
| $7$ | $15$ | $10^5$ | D | 无 |
| $8$ | $10$ | $10^5$ | 无 | $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$