Insurance Coverage: Calculate Covered Family Members - Algorithm Problem

Insurance Coverage: Calculating Covered Family Members

Given a family with a hierarchical structure where each person has a parent, and each person can purchase insurance that covers themselves and their descendants for a specific number of generations, the task is to calculate the total number of family members covered by at least one insurance policy.

Problem Statement

There is a family consisting of person 1, person 2, ..., and person N. For i≥2, person i's parent is person p_i.

They bought insurance M times. For i=1,2,…,M, person x_i bought the i-th insurance, which covers that person and their descendants in the next y_i generations.

Task

Determine how many people are covered by at least one insurance.

Constraints

• 2≤N≤3×10⁵
• 1≤M≤3×10⁵
• 1≤p_i≤i-1
• 1≤x_i≤N
• 1≤y_i≤3×10⁵
• All input values are integers.

Input

The input is given from Standard Input in the following format:

N M
p1 p2 ... pN
x1 y1
x2 y2
...
xM yM

Output

Print the number of people covered by at least one insurance.

Sample Input 1

3 2
1 2
2 2
3 1

Sample Output 1

3

Sample Input 2

5 3
1 2 2
2 2
3 1
4 3

Sample Output 2

5

Note

In Sample Input 1, person 1 buys the first insurance, covering person 1 and their descendants for 2 generations. Then, person 2 buys the second insurance, covering person 2 and their descendants for 2 generations. Therefore, all 3 people are covered by at least one insurance.

In Sample Input 2, person 1 buys the first insurance, covering person 1 and their descendants for 2 generations. Then, person 2 buys the second insurance, covering person 2 and their descendants for 2 generations. Finally, person 2 buys the third insurance, covering person 4 and their descendants for 3 generations. Therefore, all 5 people are covered by at least one insurance.