Metro Optimal Flow Minimization

A city has \(n\) resident points (\(2\le n \le 10^5\)) with populations \(s_i\) (\(1 \le s_i \le 10^7\)). They are connected by \(n-1\) bidirectional roads forming a tree. The \(i\)th road connects nodes \(u_i\) and \(v_i\) and takes \(w_i\) time to walk, with \(1\le w_i\le 10^7\). The government plans to build a metro line along a simple path of the tree. For every road that the metro passes under, it takes \(w'_i\) time (\(1 \le w'_i\le 10^7\)) and, in addition, getting on and off the metro costs a total of \(t\) time (\(0\le t \le 10^7\)). It is guaranteed that for each road \(i\) we have \[ w'_i \le w_i - t. \]

When a person travels between two resident points, if their unique path shares at least one common edge with the metro line then they will ride the metro on as many common edges as possible; otherwise, they travel entirely on foot. In other words, if the unique path between two nodes (a) and (b) is [ d_{walk}(a,b)=\sum_{e\in Q}w_e ] and if (Q) and the metro edge set (P) have a nonempty intersection (which, in a tree, is a contiguous segment), then the actual travel time is [ d(a,b)= d_{walk}(a,b) - \Bigl(\sum_{e\in I}(w_e - w'_e) - t\Bigr), ] where (I) is the contiguous segment of (Q) that is contained in (P). (Note: the guarantee ensures that the saving ((w_e-w'_e)) per edge is at least (t) when at least one edge is used.)

We define the total cost as \[ \sum_{1\le a<b\le n} s_a\cdot s_b \cdot d(a,b). \] The task is to choose a metro line (i.e. a simple path on the tree) among all \(\frac{n(n-1)}{2}\) possibilities that minimizes this total cost, and output the minimum value.

inputFormat

The first line contains two integers \(n\) and \(t\) -- the number of resident points and the additional time needed for boarding/alighting the metro.

The second line contains \(n\) integers: \(s_1, s_2, \ldots, s_n\) representing the population at each resident point.

Then \(n-1\) lines follow. Each line contains four integers \(u_i, v_i, w_i, w'_i\) representing a bidirectional road connecting nodes \(u_i\) and \(v_i\) with walking time \(w_i\) and metro time \(w'_i\). It is guaranteed that \(w'_i \le w_i - t\).

outputFormat

Output one integer, the minimum total cost \(\sum_{1\le a<b\le n} s_a \cdot s_b \cdot d(a,b)\) after choosing the optimal metro line.

sample

2 1
1 2
1 2 5 3

9