Find People Covered by Insurance in Family Tree

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.

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:

The first line contains two integers N and M, separated by a space.

The i-th line (1≤i≤M) of the following M lines contains two integers xi and yi, separated by a space.

Output

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

Sample Input 1

5 2
1 2
2 3

Sample Output 1

5

Sample Input 2

10 3
1 2
2 3
3 1

Sample Output 2

9

Sample Input 3

3 1
1 3

Sample Output 3

3