INU 막대기
시간 제한2초메모리 제한1024 MB
양 끝에 I, N, U 중 하나가 적힌 N개의 막대가 길이와 함께 주어질 때, 맞닿는 끝의 글자가 같도록 뒤집어 가며 이어 붙여 만들 수 있는 가장 긴 막대의 길이를 구한다.
문제
N개의 INU 막대기가 있다.
INU 막대기의 양 끝에는 각각 I, N, U 중 하나가 적혀 있다.
영현이는 몇 개의 막대기를 연결해 가장 긴 막대기를 만들려 한다.
막대기는 접합면에 적힌 글자가 같을 때만 연결할 수 있고, 뒤집어서 사용할 수도 있다.
영현이가 만들 수 있는 가장 긴 막대기의 길이는 얼마인가?
입력
첫 줄에 막대기의 개수 N이 주어진다. (1 ≤ N ≤ 105)
다음 N줄에 각 막대기의 양 끝에 적힌 두 알파벳과 길이 정수 ti가 주어진다. (1 ≤ ti ≤ 103)
출력
영현이가 만들 수 있는 가장 긴 막대기의 길이를 출력한다.