Juice

In a favela in Rio de Janeiro, a light finally flickered on. After months of careful work, the residents connected a generator to thousands of extension cords, and the slum lit up with millions of bright lights.

However, the extension cords could not carry enough power to meet the energy demand of every house in the slum. So, before switching on the generator, the engineers had to choose carefully which houses to power and which to leave dark. Their goal was to power as many houses as possible, given each house's energy demand and the capacity of the extension cords.

The generator and the houses are modeled as nodes, and the extension cords as edges connecting them. Each node draws power from exactly one other node, so the whole network forms a tree rooted at the generator. Every node except the generator has a non-negative energy demand. The generator can supply far more power than the total capacity of the cords attached to it, so treat it as an infinite source.

Power reaches a house by traveling along the cords out from the generator. For every cord, the total power flowing through it — that is, the sum of the demands of all powered houses located below that cord — must not exceed the cord's capacity. A house counts as powered only when its full demand is delivered.

Determine the maximum number of houses whose energy demands can be met.

The first line contains a single integer $n$ ($0 \le n \le 1000$), the number of houses.

Each of the next $n$ lines describes one house $i$ (for $i = 1, 2, \dots, n$) with three integers $p_i\ r_i\ c_i$:

• $p_i$ ($0 \le p_i \le n$) is the parent node of house $i$;
• $r_i$ ($0 \le r_i \le 100$) is the energy demand of house $i$;
• $c_i$ ($1 \le c_i \le 100$) is the capacity of the extension cord connecting house $i$ to node $p_i$.

The generator has index $0$.

Print a single integer: the maximum number of houses whose energy demands can be met.