G

F. Пути в дереве

Дано укоренённое дерево на N вершинах и число X. В каждой вершине записано число — её вес.

Назовём восходящим путь a_i, p (a_i), p(p(a_i)), ..., где p(a) — родитель вершины a. Проще говоря, восходящий путь — это путь, который начинается с некоторой вершины и двигается в сторону корня (не обязательно доходя до него). Путь может состоять из одной вершины. Весом пути назовём суммарный вес вершин на этом пути. Найдите количество восходящих путей с весом X .

Формат ввода

В первой строке дано число вершин n (1 ≤ n ≤ 2⋅10⁵) и число X (−10⁹ ≤ X ≤ 10⁹).

В следующих n строках по одной в строке заданы вершины. i -я вершина задаётся двумя числами — p_i и w_i, записанными через пробел. p_i — это либо номер вершины-родителя вершины i, в этом случае 0 ≤ p_i ≤ n−1, либо −1, если вершина i является корнем.

wi — это вес вершины i (−10⁴ ≤ w_i ≤ 10⁴).

Формат вывода

Выведите одно целое число — количество восходящих путей веса X.

Пример 1

6 3 -1 1 0 1 0 1 1 1 2 2 3 1

3

Пример 2

1 2 -1 1

0