Sheep Rescue Operation

Interview

Time limit1sMemory limit256 MB

Summary

Given a tree rooted at 1 with sheep or wolf counts per node, find the maximum number of sheep that can reach node 1 along unique paths while each wolf eats at most one entering sheep.

Level: Medium5 of 10
Topics: Tree, Greedy, Graph, Sorting
Solved: No attempts yet

Problem

There is a country made up of N islands. The islands are numbered from 1 to N.

Island 1 has only a lifeboat, and the other islands are inhabited by sheep or wolves.

Unable to keep up with the growing wolf population, the sheep decided to take the lifeboat and move to a country without wolves.

From each island, the path to island 1 is unique, and island i has a bridge leading to island p**i.

The sheep travel along the path to island 1, while the wolves stay on the island where they are and eat any sheep that enter the island. A wolf is agile, so it can always catch a sheep that enters its island. One wolf eats at most one sheep.

How many sheep can reach island 1?

Input

The first line gives the number of islands N (2 ≤ N ≤ 123,456).

Each of the next N-1 lines gives ti, ai, pi (1 ≤ ai ≤ 109, 1 ≤ pi ≤ N), the information for islands 2 through N.

If ti is 'W', island i has ai wolves. If ti is 'S', island i has ai sheep. pi means there is a bridge from island i to island pi.

Output

Print the number of sheep that can be rescued on the first line.

Examples2

Example 1
Input
```
4
S 100 3
W 50 1
S 10 1
```
Expected output
```
60
```

Example 2

Input

Expected output