Tỉa Nhánh

Minh đang quản lý một mạng máy chủ phân cấp có cấu trúc dạng cây gồm $n$ đỉnh, với gốc đặt tại đỉnh $1$. Mỗi đỉnh và mỗi cạnh trên cây đều được gán một số nguyên.

Một đỉnh $v$ được gọi là đỉnh quá tải nếu tồn tại một đỉnh $u$ thuộc cây con của đỉnh $v$ sao cho $dist(v, u) > a_u$, trong đó $a_u$ là giá trị được gán cho đỉnh $u$, còn $dist(v, u)$ là tổng trọng số các cạnh trên đường đi từ $v$ đến $u$.

Lá của cây là các đỉnh chỉ nối với đúng một đỉnh khác bằng một cạnh duy nhất. Đỉnh gốc của cây được coi là một lá khi và chỉ khi cây chỉ còn lại đúng một đỉnh gốc duy nhất.

Để hệ thống hoạt động ổn định, Minh muốn loại bỏ dần một số lá của cây cho đến khi không còn đỉnh quá tải nào. Tại mỗi bước, Minh chỉ được phép chọn một đỉnh hiện đang là lá và xóa đỉnh đó khỏi cây.

Hãy xác định số lượng lá tối thiểu mà Minh cần xóa để cây không còn đỉnh quá tải nào.

Dữ liệu vào

Dòng đầu tiên chứa số nguyên $n$ ($1 ≤ n ≤ 10^5$), biểu thị số lượng đỉnh của cây.

Dòng thứ hai chứa dãy gồm $n$ số nguyên $a_1, a_2, ..., a_n$ ($1 ≤ a_i ≤ 10^9$), trong đó $a_i$ là giá trị được gán cho đỉnh $i$.

Trong $n - 1$ dòng tiếp theo, dòng thứ $i$ chứa hai số nguyên $p_i$ ($1 ≤ p_i ≤ n$) và $c_i$ ($-10^9 ≤ c_i ≤ 10^9$), mô tả một cạnh nối giữa đỉnh $i + 1$ và đỉnh $p_i$ với trọng số $c_i$. Dữ liệu đảm bảo đồ thị đã cho tạo thành một cây có gốc tại đỉnh $1$.

Kết quả

In ra một số nguyên duy nhất là số lượng lá tối thiểu cần xóa để cây không còn bất kỳ đỉnh quá tải nào.

Chấm điểm

Subtask 1 (30 points). $n ≤ 2000$

Subtask 2 (30 points). $c_i ≥ 0$

Subtask 3 (40 points). $1 ≤ n ≤ 10^5$

Ví dụ

Input

9
88 22 83 14 95 91 98 53 11
3 24
7 -8
1 67
1 64
9 65
5 12
6 -80
3 8

Output

5

Ghi chú

Ở ví dụ trên, quá trình loại bỏ các đỉnh lá có thể được thực hiện lần lượt theo thứ tự: xóa đỉnh lá $4$, xóa đỉnh lá $2$, xóa đỉnh lá $8$, xóa đỉnh lá $6$, rồi xóa đỉnh lá $9$. Tổng cộng cần xóa $5$ lá. Cây còn lại gồm các đỉnh ${1, 3, 5, 7}$ và không còn đỉnh nào bị quá tải.