Thu hoạch cam

Ngân rất thích ăn cam. Trong làng của Ngân có một cây cam cổ thụ với \(n\) vị trí đặc biệt (gọi là các đỉnh), đánh số từ \(1\) đến \(n\); đỉnh \(1\) là gốc cây. Các đỉnh được nối với nhau bởi \(n - 1\) nhánh, tạo thành một cây có gốc tại đỉnh \(1\).

Mỗi đỉnh khác gốc có thể có tối đa một quả cam. Hiện tại là ngày \(0\) và chưa quả nào chín. Quả cam thứ \(j\) mọc ở đỉnh \(v_j\), chỉ chín đúng vào ngày \(d_j\), và nếu được hái đúng ngày đó thì mang lại độ ngọt \(w_j\).

Để hái cam, mỗi ngày Ngân có thể cắt một số nhánh bất kỳ (có thể không cắt nhánh nào). Sau khi cắt, phần cây vẫn nối với gốc được giữ lại, còn mọi phần bị tách khỏi gốc sẽ rơi xuống đất. Ngân thu được tất cả các quả cam chín đúng vào ngày hôm đó nằm trong các phần vừa rơi; các quả chưa chín hoặc đã quá ngày chín trong phần đó đều bị bỏ đi.

Hãy tính tổng độ ngọt lớn nhất mà Ngân có thể thu được.

Input

• Dòng đầu tiên chứa ba số nguyên \(n\), \(m\), \(k\) \((2 \le n \le 10^5,\ 1 \le m \le n - 1,\ 1 \le k \le 10^5)\) — số đỉnh, số quả cam và ngày chín muộn nhất có thể.
• \(n - 1\) dòng tiếp theo, dòng thứ \(i - 1\) (với \(2 \le i \le n\)) chứa số nguyên \(p_i\) \((1 \le p_i \le i - 1)\) — đỉnh cha của đỉnh \(i\).
• \(m\) dòng cuối, mỗi dòng chứa ba số nguyên \(v_j\), \(d_j\), \(w_j\) \((2 \le v_j \le n,\ 1 \le d_j \le k,\ 1 \le w_j \le 10^9)\) — vị trí, ngày chín và độ ngọt của quả cam thứ \(j\).

Dữ liệu đảm bảo các giá trị \(v_j\) đôi một khác nhau.

Output

In ra một số nguyên duy nhất là tổng độ ngọt lớn nhất có thể thu được.

Subtask

• Subtask 1 (\(9\%\) số điểm): \(n, k \le 20\) và \(w_j = 1\) với mọi \(j\).
• Subtask 2 (\(15\%\) số điểm): \(p_i = i - 1\) với mọi \(i\) và \(w_j = 1\) với mọi \(j\).
• Subtask 3 (\(15\%\) số điểm): \(k \le 2\).
• Subtask 4 (\(28\%\) số điểm): \(m \le 1000\).
• Subtask 5 (\(33\%\) số điểm): không có ràng buộc gì thêm.

Sample Input 1

6 4 10
1
2
1
4
4
3 4 5
4 7 2
5 4 1
6 9 3

Sample Output 1

9

Notes

Một cách thu hoạch tối ưu: ngày \(4\) cắt nhánh nối đỉnh \(3\) (thu quả ở đỉnh \(3\), độ ngọt \(5\)) và nhánh nối đỉnh \(5\) (độ ngọt \(1\)); ngày \(9\) cắt nhánh nối đỉnh \(4\), cả phần gồm đỉnh \(4\) và \(6\) rơi xuống, thu quả ở đỉnh \(6\) (độ ngọt \(3\)). Quả ở đỉnh \(4\) đã quá ngày chín nên bị bỏ. Tổng độ ngọt là \(5 + 1 + 3 = 9\).