Antivirus#13068

Antivirus

1.5 seconds
256 megabytes

Ostap's computer has folders, numbered from to . Folder is the root, and every other folder (2 \le i \le n) lies directly inside folder a_i; it is guaranteed that a_i < i.

Ostap ran the antivirus times. The -th run checks folder c_j and all folders inside it that lie no deeper than d_j levels from c_j.

Formally, folder is checked by the -th run if can be reached from c_j by moving from a folder to a folder that lies directly inside it, at most d_j times. In particular, folder c_j is always checked by the -th run, even when d_j = 0.

The same folder could be checked multiple times. Find the number of folders checked by at least one run.

Input

The first line contains two integers and (2 \le n \le 3 \cdot 10^5, 1 \le k \le 3 \cdot 10^5) — the number of folders and the number of antivirus runs.

The second line contains n - 1 integers a_2, a_3, \ldots, a_n (1 \le a_i < i), where a_i is the folder in which folder was created.

Each of the next lines contains two integers c_j and d_j (1 \le c_j \le n, 0 \le d_j \le 3 \cdot 10^5) — the folder and the depth of the -th run.

Output

Print a single integer — the number of folders checked by at least one run.

Examples

Example 1

Loading
Loading

Example 2

Loading
Loading

Note

In the first example, folder contains folders and , folder contains folders and , folder contains folder , and folder contains folders and . The first run checks folders , , and (blue color); the second checks only folder (green color); the third checks only folder (red color), because it has no other folders inside it. In total, folders are checked.

In the second example, the first run checks folders , , , and , the second checks folder , the third checks folder , and the fourth checks folder . Folder is not checked, so the answer is .