C. Алёна и дерево
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Алёна решила сесть на диету и пошла в лес за яблоками. Внезапно она обнаружила волшебное корневое дерево с корнем в вершине 1, на каждом ребре и в каждой вершине которого записаны некоторые числа.

Девочка заметила, что некоторые вершины дерева грустят, поэтому она решила с ними поиграть. Назовем вершину v грустной, если в ее поддереве найдется вершина u, такая что dist(v, u) > au, где au — число, записанное в вершине u, а dist(v, u) — сумма чисел на ребрах на пути от v до u.

Листьями дерева называются вершины, соединенные ребром ровно с одной вершиной, а корень дерева является листом тогда и только тогда, когда дерево состоит из единственной вершины-корня.

Алёна решила удалять листья дерева до тех пор, пока все вершины не перестанут грустить. Какое минимальное количество листьев нужно удалить Алёне?

Входные данные

В первой строке входных данных записано целое число n (1 ≤ n ≤ 105) — количество вершин в дереве.

Во второй строке входных данных заданы n целых чисел a1, a2, ..., an (1 ≤ ai ≤ 109), где ai — число, записанное в вершине i.

В следующих n - 1 строках описываются ребра дерева: в i-й из этих строк записана пара чисел pi и ci (1 ≤ pi ≤ n,  - 109 ≤ ci ≤ 109), означающих, что вершины i + 1 и pi дерева соединены ребром, на котором записано число ci.

Выходные данные

Выведите минимальное количество листьев, которое требуется удалить Алёне, чтобы не осталось ни одной грустной вершины.

Пример
Входные данные
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
Выходные данные
5
Примечание

Процесс удаления листьев дерева из первого примера может выглядеть так: