Alyona decided to go on a diet and went to the forest to get some apples. There she unexpectedly found a magic rooted tree with root in the vertex 1, every vertex and every edge of which has a number written on.

The girl noticed that some of the tree's vertices are sad, so she decided to play with them. Let's call vertex v sad if there is a vertex u in subtree of vertex v such that dist(v,?u)?>?au, where au is the number written on vertex u, dist(v,?u) is the sum of the numbers written on the edges on the path from v to u.

Leaves of a tree are vertices connected to a single vertex by a single edge, but the root of a tree is a leaf if and only if the tree consists of a single vertex — root.

Thus Alyona decided to remove some of tree leaves until there will be no any sad vertex left in the tree. What is the minimum number of leaves Alyona needs to remove?

In the first line of the input integer n (1?≤?n?≤?105) is given — the number of vertices in the tree.

In the second line the sequence of n integers a1,?a2,?...,?an (1?≤?ai?≤?109) is given, where ai is the number written on vertex i.

The next n?-?1 lines describe tree edges: ith of them consists of two integers pi and ci (1?≤?pi?≤?n, ?-?109?≤?ci?≤?109), meaning that there is an edge connecting vertices i?+?1 and pi with number ci written on it.

PRint the only integer — the minimum number of leaves Alyona needs to remove such that there will be no any sad vertex left in the tree.

988 22 83 14 95 91 98 53 113 247 -81 671 649 655 126 -803 8output
5Note
The following image represents possible process of removing leaves from the tree:
題目大意：給你一棵n個頂點的數，然后每個點會有一個值，點于點之間有權重，把葉到任意祖宗的路權重和大于點值的點刪去，需要最少幾步
數據范圍： n (1?≤?n?≤?105)(頂點個數),a1,?a2,?...,?an (1?≤?ai?≤?109)(各點值),pi,ci (1?≤?pi?≤?n, ?-?109?≤?ci?≤?109),pi(點編號),ci(點與點之間的權值)
解題思路:一開始想用鄰接表，但是不能開那么大的，所以就放棄了，之后想用三個數組去存，但是個人感覺太難以理解，不太好弄，意外發現vector，他是一個靈活的數組，然后用多少取多少，每次壓入棧的是對應的連接點和兩點之間的權值，然后從根開始遍歷，不斷沿著路線下去，當查到不符合條件的時候返回0，相當于不存在，之后函數返回的值是存在的點，與點總數比較即可