Background

City A, the hometown of little $\mathfrak{f}$, has recently opened a subway.

Problem Description

City A has $n$ residential areas $(2\le n \le 10^5)$. The population of the $i$-th residential area is $s_i (1 \le s_i \le 10^7)$. There are also $n-1$ bidirectional roads forming a tree. The $i$-th road connects residential areas $u_i$ and $v_i$. It takes $w_i (1 \le w_i\le 10^7)$ time for a person to walk through this road.

Now the government of City A decides to build one subway line. The subway line is a simple path on the tree. If the path passes through the $i$-th road, then taking the subway through (under) this road only takes $w_i^{\prime} (1 \le w_i^{\prime} \le 10^7)$ time. Also, entering and exiting the subway stations costs a total of $t (0 \le t \le 10^7)$ time.

It is known that when a person travels from one residential area to another, if the travel path shares at least one common edge with the subway path, then they will definitely choose to take the subway for as much of the trip as possible. If there is no common edge, they will walk the whole way. The problem guarantees that for the $i$-th road, $w_i^{\prime} \le w_i - t$. We consider that the larger the product of the populations of two residential areas is, the more likely people want to move between them.

Now, little $\mathfrak{f}$ wants to know, among all $\frac{n(n-1)}{2}$ ways to build the subway line, the minimum value of $\sum_{a=1}^{n-1}\sum_{b=a+1}^{n}(s_a \cdot s_b \cdot d_{a,b})$, where $d_{a,b}$ denotes the time needed to travel from residential area $a$ to $b$ (or from $b$ to $a$, which is the same).

But he cannot do it, so he comes to ask the all-powerful you for help.

Input Format

The first line contains three integers $id, n, t$ separated by spaces, representing the subtask id, the number of residential areas, and the time cost for entering and exiting stations.

The next $n$ lines each contain one integer $s_i$, representing the population of each residential area.

The next $n - 1$ lines each contain four integers $u_i, v_i, w_i, w_i^{\prime}$ separated by spaces, representing the two endpoints of each road, the walking time, and the subway time.

Output Format

One line with one integer, representing the minimum value required.

The answer may exceed the range of a $64$-bit integer. You may use the __int128 type, whose range is $[-2^{127},2^{127}-1]$.

The following is an output template for the __int128 type:

#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;
}

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

Hint

Sample $1$ explanation:

Before building the subway, it is as shown in the figure below:

One optimal subway plan is to build the subway from $2$ to $3$. It is as shown in the figure below (solid lines indicate roads where the subway is built):

From $1$ to $2$, the path uses the subway. The required time is $6+0=6$, and the contribution to the answer is $9\times9\times6=486$.

From $1$ to $3$, the path uses the subway. The required time is $5+0=5$, and the contribution to the answer is $9\times3\times5=135$.

From $1$ to $4$, the path does not use the subway. The required time is $6$, and the contribution to the answer is $9\times2\times6=108$.

From $1$ to $5$, the path uses the subway. The required time is $6+9+0=15$, and the contribution to the answer is $9\times3\times15=405$.

From $2$ to $3$, the path uses the subway. The required time is $6+5+0=11$, and the contribution to the answer is $9\times3\times11=297$.

From $2$ to $4$, the path uses the subway. The required time is $6+6+0=12$, and the contribution to the answer is $9\times2\times12=216$.

From $2$ to $5$, the path does not use the subway. The required time is $9$, and the contribution to the answer is $9\times3\times9=243$.

From $3$ to $4$, the path uses the subway. The required time is $5+6+0=11$, and the contribution to the answer is $3\times2\times11=66$.

From $3$ to $5$, the path uses the subway. The required time is $5+6+9+0=20$, and the contribution to the answer is $3\times3\times20=180$.

From $4$ to $5$, the path uses the subway. The required time is $6+6+9+0=21$, and the contribution to the answer is $2\times3\times21=126$.

In summary, the answer is $486+135+108+405+297+216+243+66+180+126=2262$.

It can be proven that there is no better subway construction plan.

This problem uses bundled tests and subtask dependencies.

Special property A: $t=0$.

Special property B: $u_i=i, v_i=i+1$.

Special property C: The degree of every node is at most $100$.

Special property D: $u_i=1, v_i=i+1$.

Translated by ChatGPT 5