23847번 - INU 막대기

문제

N개의 INU 막대기가 있다.

INU 막대기의 양 끝에는 각각 I, N, U 중 하나가 적혀있다.

영현이는 몇 개의 막대기를 연결하여 가장 긴 막대기를 만들려 한다.

막대기는 접합면에 적힌 글자가 동일한 경우만 연결할 수 있고, 뒤집어서 사용하는 것이 가능하다.

영현이가 만들 수 있는 가장 긴 막대기의 길이는 얼마인가?

입력

첫 줄에 막대기의 개수 N이 주어진다. (1 ≤ N ≤ 10⁵)

다음N줄에 각 막대기의 각 양쪽 끝에 적힌 두 알파벳과 길이 정수 t_i 가 주어진다. (1 ≤ t_i ≤ 10³)

출력

영현이가 만들 수 있는 가장 긴 막대기의 길이를 출력한다.

제한

힌트