You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```python
<your code here>
```

Execution time limit: 3.0 seconds
Memory limit: 1024.0 MB

# Problem
LuoTianyi is watching the anime Made in Abyss. She finds that making a Cartridge is interesting. To describe the process of making a Cartridge more clearly, she abstracts the original problem and gives you the following problem.

You are given a tree $$$T$$$ consisting of $$$n$$$ vertices. Each vertex has values $$$a_i$$$ and $$$b_i$$$ and each edge has values $$$c_j$$$ and $$$d_j$$$.

Now you are aim to build a tree $$$T'$$$ as follows:

- First, select $$$p$$$ vertices from $$$T$$$ ($$$p$$$ is a number chosen by yourself) as the vertex set $$$S'$$$ of $$$T'$$$.
- Next, select $$$p-1$$$ edges from $$$T$$$ one by one (you cannot select one edge more than once).
- May you have chosen the $$$j$$$-th edge connects vertices $$$x_j$$$ and $$$y_j$$$ with values $$$(c_j,d_j)$$$, then you can choose two vertices $$$u$$$ and $$$v$$$ in $$$S'$$$ that satisfy the edge $$$(x_j,y_j)$$$ is contained in the simple path from $$$u$$$ to $$$v$$$ in $$$T$$$, and link $$$u$$$ and $$$v$$$ in $$$T'$$$ by the edge with values $$$(c_j,d_j)$$$ ($$$u$$$ and $$$v$$$ shouldn't be contained in one connected component before in $$$T'$$$).

A tree with three vertices, $$$\min(A,C)=1,B+D=7$$$, the cost is $$$7$$$.

Selected vertices $$$2$$$ and $$$3$$$ as $$$S'$$$, used the edge $$$(1,2)$$$ with $$$c_j = 2$$$ and $$$d_j = 1$$$ to link this vertices, now $$$\min(A,C)=2,B+D=4$$$, the cost is $$$8$$$.

Let $$$A$$$ be the minimum of values $$$a_i$$$ in $$$T'$$$ and $$$C$$$ be the minimum of values $$$c_i$$$ in $$$T'$$$. Let $$$B$$$ be the sum of $$$b_i$$$ in $$$T'$$$ and $$$D$$$ be the sum of values $$$d_i$$$ in $$$T'$$$. Let $$$\min(A, C) \cdot (B + D)$$$ be the cost of $$$T'$$$. You need to find the maximum possible cost of $$$T'$$$.

## Input Format
The first line contains one integer $$$n$$$ ($$$3\le n \le 2\cdot 10^5$$$) — the number of vertices in the tree $$$T$$$.

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1\le a_i\le 2\cdot 10^5$$$), where the $$$i$$$-th integer represents the $$$a_i$$$ value of the $$$i$$$-th vertex.

The third line contains $$$n$$$ integers $$$b_1, b_2, \ldots, b_n$$$ ($$$1\le b_i\le 2\cdot 10^5$$$), where the $$$i$$$-th integer represents the $$$b_i$$$ value of the $$$i$$$-th vertex.

Then $$$n-1$$$ lines follow, the $$$j$$$-th of them contains four integers $$$x_j,y_j,c_j,d_j$$$ ($$$1\le x_j,y_j\le n,1\le c_j,d_j\le 2\cdot 10^5$$$) representing the edge $$$(x_j,y_j)$$$ and its values $$$c_j$$$ and $$$d_j$$$ respectively. It's guaranteed that edges form a tree.

## Output Format
Print a single integer — the maximum possible cost of $$$T'$$$.

## Examples
```input
3
1 2 2
1 1 2
1 2 2 1
1 3 1 2
```
```output
8
```
-----
```input
5
2 4 2 1 1
2 4 4 4 4
2 5 3 3
3 5 2 4
4 2 5 5
5 1 1 5
```
```output
35
```
-----
```input
6
5 7 10 7 9 4
6 9 7 9 8 5
2 1 5 1
3 2 2 4
4 3 6 3
5 1 7 4
6 5 6 8
```
```output
216
```
-----
```input
5
1000 1000 1 1000 1000
1000 1000 1 1000 1000
1 2 1 1
2 3 1000 1000
3 4 1000 1000
3 5 1000 1000
```
```output
7000000
```

## Note
The tree from the first example is shown in the statement.

The tree from the second example is shown below:

$$$A = 1, B = 18, C = 1, D = 17$$$, so the cost is $$$\min(1,1) \cdot (18 + 17) = 35$$$.

Now solve the problem and return the code.