Evacuation

A terrible thing has happened. Doctor Octavius has taken over an industrial laboratory. The laboratory consists of $n$ rooms, some of which are connected by corridors. There are $n-1$ corridors, and every room can be reached from every other room. In other words, the laboratory is a tree with $n$ vertices. Each corridor has a travel time $l_i$, which is the time needed to go from one end of the corridor to the other. Corridors can be walked in both directions.

Each room holds exactly one person. Doctor Octavius plans to kill all of them, but he has given them a chance to survive. The exits are located at the leaves of this tree. A leaf is a vertex with degree $0$ or $1$. A person who reaches an exit escapes from Doctor Octavius's tentacles. Each corridor has a detonator set by the villain. Each detonator has a time $t_i$ at which it explodes. Once a detonator explodes, nobody can move through its corridor anymore, and anyone inside that corridor at that moment dies. If a person reaches the far end of the corridor at the moment of the explosion, they survive.

Spider-Man cannot reach these people in time, so they must save themselves. Find the maximum number of people who can escape.

The first line contains one integer $n$ ($1 \le n \le 100000$), the number of rooms. Each of the next $n-1$ lines contains four integers $a_i$, $b_i$, $l_i$, and $t_i$ ($1 \le a_i, b_i \le n$; $1 \le l_i \le 10000$; $1 \le t_i \le 10^9$). These are the two rooms connected by the corridor, the time needed to walk through it, and the moment its detonator explodes.

It is guaranteed that the laboratory is a tree.

Print one integer, the maximum number of people who can escape.

In the first example, the person in room 5 runs to room 4, and the person in room 3 runs to the same room. That person arrives exactly at the moment of the explosion, but still survives.

In the second example, the person in room 4 runs to room 2, and the person in room 1 runs to room 5. The person in room 3 does not make it out.