INU Sticks

Time limit2sMemory limit1024 MB

Summary

Given N sticks, each with a letter pair (I, N, or U) at its ends and a length, join a subset into the longest chain where touching ends match, flipping allowed.

Level: Medium7 of 10
Topics: Graph, Greedy, Union-find, Implementation
Solved: No attempts yet

Problem

There are N INU sticks.

Each end of an INU stick has one of the letters I, N, or U written on it.

Yeonghyeon wants to join some sticks into the longest possible stick.

Two sticks can be joined only when the letters at the touching ends are the same, and a stick may be flipped over.

What is the length of the longest stick Yeonghyeon can make?

Input

The first line gives the number of sticks N. (1 ≤ N ≤ 105)

The next N lines give the two letters at the ends of each stick and its length, the integer ti. (1 ≤ ti ≤ 103)

Output

Print the length of the longest stick Yeonghyeon can make.

Examples1

Example 1
Input
```
4
II 3
IN 5
UU 7
IN 2
```
Expected output
```
10
```