Market

Time Limit: 2 Seconds
Memory Limit: 65536 KB

There's a fruit market in Byteland. The salesmen there only sell apples.

There are `n` salesmen in the fruit market and the `i`-th salesman will sell at most `w`_{i} apples. Every salesman has an immediate manager `p`_{i} except one salesman who is the boss of the market. A salesman `A` is said to be the superior of another salesman `B` if at least one of the followings is true:

- Salesman
`A` is the immediate manager of salesman `B`.
- Salesman
`B` has an immediate manager salesman `C` such that salesman `A` is the superior of salesman `C`.

The market will not have a managerial cycle. That is, there will not exist a salesman who is the superior of his/her own immediate manager.

We will call salesman `x` a subordinate of another salesman `y`, if either `y` is an immediate manager of `x`, or the immediate manager of `x` is a subordinate to salesman `y`. In particular, subordinates of the boss are all other salesmen of the market. Let the degree of the boss be 0. Then if the degree of `i`-th salesman is `k`, the immediate subordinates of `i`-th salesman will have degree `k` + 1.

Today, `m` buyers come to market for apples. The `i`-th buyer will buy at most `c`_{i} apples only from the `x`_{i}-th salesman and his subordinates whose degree is no larger than `x`_{i}-th salesman's degree plus `d`_{i}.

The boss wants to know how many apples can be sold in salesmen's best effort (i.e. the maximum number).

#### Input

There are multiple test cases. The first line of input contains an integer T indicating the number of test cases. For each test case:

The first line contains two integers `n` and `m` (1 ≤ `n`, `m` ≤ 10000) — the number of salesmen and the number of buyers.

The second line contains `n` integers `w`_{1}, `w`_{2}, ..., `w`_{n} (1 ≤ `w`_{i} ≤ 10^{5}). Every `w`_{i} denotes the number of apples that `i`-th salesman can sell.

The next line contains `n` integers `p`_{i} (1 ≤ `p`_{i} ≤ `n` or `p`_{i} = -1). Every `p`_{i} denotes the immediate manager for the `i`-th salesman. If `p`_{i} is -1, that means that the `i`-th salesman does not have an immediate manager.

Each of the next `m` lines contains three integers `c`_{i}, `x`_{i} and `d`_{i} (1 ≤ `c`_{i} ≤ 10^{5}, 1 ≤ `x`_{i} ≤ `n`, 0 ≤ `d`_{i} ≤ n) — the information of `i`-th buyer.

It is guaranteed that the total number of salesmen in the input doesn't exceed 10^{5}, and the total number of buyers also doesn't exceed 10^{5}. The number of test cases in the input doesn't exceed 500.

#### Output

For each test case, output a single integer denoting the maximum number of apples can be sold.

#### Sample Input

1
4 2
1 2 3 4
-1 1 2 3
3 2 1
5 1 1

#### Sample Output

6

Author:

**LIN, Xi**
Source:

**ZOJ Monthly, October 2015**
Submit
Status