Duck Contest

I'm Sorry

Program time limit: 6 seconds

Program memory limit: 1024 MB

The problem seemed to have made the ducks run away, so they won’t be available for this problem, and it has been stripped down to the mathematical statement!

But Nah, You’d Win, right?

You are given a rooted tree with $N$ vertices, rooted at vertex $1$.

For every vertex $i$, you are given four integers $T_i$, $E_i$, $L_i$, and $R_i$, where $T_i$ is the target endpoint depth of a downward path starting at vertex $i$, $E_i$ is the endpoint cost when a downward path ends at vertex $i$, and $L_i$ and $R_i$ are the minimum and maximum allowed endpoint depths of a downward path starting at vertex $i$.

For every vertex $i$ from $2$ to $N$, you are given two integers $P_i$ and $D_i$, where $P_i$ is the parent of vertex $i$, and $D_i$ is the length of the edge connecting $P_i$ and $i$.

Let $\operatorname{depth}(u)$ be the distance from the root to vertex $u$.

A downward path is a sequence of vertices $(X_1, X_2, \dots, X_k)$, where for every $i$ from $2$ to $k$, the parent of $X_i$ is $X_{i - 1}$. A downward path starting at vertex $X_1$ and ending at vertex $X_k$ is valid only if

$$ L_{X_1} \le \operatorname{depth}(X_k) \le R_{X_1}. $$

In other words, the allowed endpoint depth range is determined by the starting vertex of the downward path. The cost of a valid downward path starting at $X_1$ and ending at $X_k$ is

$$ C + (T_{X_1} - \operatorname{depth}(X_k))^2 + E_{X_k}. $$

A downward path decomposition partitions all vertices of the tree into valid downward paths, so every vertex belongs to exactly one downward path.

Find the minimum possible total cost of a downward path decomposition.

The input guarantees that $L_i \le \operatorname{depth}(i) \le R_i$ for every vertex $i$, so a valid decomposition always exists.

Input

The first line contains two integers $N$ and $C$.

The next $N$ lines each contain four integers $T_i$, $E_i$, $L_i$, and $R_i$.

The next $N - 1$ lines describe the tree. For each $i$ from $2$ to $N$, the $(i - 1)$-th of these lines contains two integers $P_i$ and $D_i$, meaning that the parent of vertex $i$ is $P_i$, and the edge from $P_i$ to $i$ has length $D_i$.

Output

Output a single integer: the minimum possible total cost of a valid downward path decomposition.

Constraints

For all test cases:

  • $1 \le N \le 10^5$
  • $0 \le C \le 10^9$
  • $0 \le T_i \le 10^6$
  • $0 \le E_i \le 10^9$
  • $0 \le L_i \le \operatorname{depth}(i) \le R_i \le 10^6$
  • $1 \le P_i < i$ for $2 \le i \le N$
  • $1 \le D_i \le 10^6$ for $2 \le i \le N$
  • The answer fits in a signed 64-bit integer.

Example

Input

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

Output

40

Explanation

The depths of vertices $1,2,3,4,5,6$ are respectively $0,\ 2,\ 5,\ 5,\ 6,\ 7.$

One optimal downward path decomposition is

$$ (1, 2, 5), \quad (3, 6), \quad (4). $$

The cost of downward path $(1, 2, 5)$ is

$$ 10 + (5 - 6)^2 + 6 = 17. $$

The cost of downward path $(3, 6)$ is

$$ 10 + (7 - 7)^2 + 0 = 10. $$

The cost of downward path $(4)$ is

$$ 10 + (4 - 5)^2 + 2 = 13. $$

Therefore, the total cost is

$$ 17 + 10 + 13 = 40. $$

It can be shown that no valid downward path decomposition has a smaller total cost, so the answer is $40$.

Submit

The contest ended at 8:16 p.m. AEST on Thursday 2nd July. All submissions will be unofficial .