A. Apple Business
time limit per test
6 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Chitanda owns a farm with $$$n$$$ apple trees on it, labeled by $$$1,2,\dots,n$$$, the $$$i$$$-th apple tree has $$$a_i$$$ apples. There are $$$n-1$$$ bidirectional roads connecting them. For all $$$i \gt 1$$$, an apple tree number $$$i$$$ is connected by a road to the apple tree number $$$\lfloor\frac{i}{2}\rfloor$$$. So the map of the farm is also like a tree.

Apple business is booming. There are $$$m$$$ requests, labeled by $$$1,2,\dots,m$$$. For the $$$i$$$-th request, Chitanda can sell the customer at most $$$c_i$$$ apples, and the customer will pay $$$w_i$$$ dollars for each apple. Unfortunately, different customers have different preferences. Specifically, for the $$$i$$$-th request, the customer will give two integers $$$u_i$$$ and $$$v_i$$$, denoting he only accepts apples from trees on the shortest path from the $$$u_i$$$-th apple tree to the $$$v_i$$$-th apple tree on the map(include $$$u_i$$$ and $$$v_i$$$).

Assume the root of the map is the $$$1$$$-th apple tree. It is amazing that $$$u_i$$$ is always $$$v_i$$$'s ancestor or $$$u_i=v_i$$$.

The farm may not be able to sell $$$c_i$$$ apples to each customer. Please write a program to help Chitanda sell apples that will maximize his profits.

Input

The first line of the input contains an integer $$$T(1\leq T\leq 1000)$$$, denoting the number of test cases.

In each test case, there are two integers $$$n,m(1\leq n,m\leq 100000)$$$ in the first line, denoting the number of apple trees and requests.

In the second line, there are $$$n$$$ integers $$$a_1,a_2,...,a_n(1\leq a_i\leq 10^9)$$$, denoting the number of apples on each apple tree.

For the next $$$m$$$ lines, each line contains four integers $$$u_i,v_i,c_i,w_i(1\leq u_i,v_i\leq n,1\leq c_i\leq 10^9,1\leq w_i\leq 10^4)$$$, denoting each request. It is guaranteed that $$$u_i$$$ is $$$v_i$$$'s ancestor or $$$u_i=v_i$$$.

It is guaranteed that $$$\sum n\leq 10^6$$$ and $$$\sum m\leq 10^6$$$.

Output

For each test case, print a single line containing an integer, denoting the maximum profits.

Example
Input
1
5 3
2 1 3 1 1
2 5 2 3
2 4 2 4
1 2 3 1
Output
13