가희와 음악

가희는 곡 하나를 만들었습니다. 달세뇨를 만나면 연주자들은 아래와 같이 행동합니다.

• 달세뇨 앞에 세뇨가 있으면, 세뇨로 돌아가서 그 위치부터 연주합니다.
• 달세뇨 앞에 세뇨가 없으면, 맨 처음으로 돌아가서 첫 번째 마디부터 연주합니다.

각각의 달세뇨는 $1$번만 효과가 적용됩니다. 곡의 마디 수가 $n$개일 때, 아래 두 조건을 모두 만족하면 연주자들은 연주를 종료합니다.

• $n$번째 마디를 연주했습니다.
• 달세뇨의 효과가 발동되지 않았습니다.

가희는 곡에 세뇨나 달세뇨를 많아야 $2$개의 위치에 적절히 넣어서 관객들의 만족도를 최대로 만들고 싶습니다. 또한 $3$번 이상 반복되는 부분이 없도록 하고 싶습니다. 가희를 도와주세요.

첫 번째 줄에 악보 마디의 수 $n$이 주어집니다.

두 번째 줄에 마디에 대한 정보가 공백으로 구분되어 주어집니다. $i$번째로 주어지는 정보는 $i$번째 마디에 대한 정보입니다. 각 마디의 정보는 아래 5가지 형식 중 하나로 주어집니다.

• 수
  • $i$번째 마디를 연주했을 때 관객들의 만족도이며, $-500\,000$ 이상 $500\,000$ 이하의 값입니다.
• S
  • 세뇨를 넣을 수 있는 자리이며, $i$번째 마디의 끝 세로선에 주어집니다.
• DS
  • 달세뇨를 넣을 수 있는 자리이며, $i$번째 마디의 끝 세로선에 주어집니다.
• S or DS
  • 세뇨 또는 달세뇨를 넣을 수 있는 자리이며, $i$번째 마디의 끝 세로선에 주어집니다.
• DS or S
  • 달세뇨 또는 세뇨를 넣을 수 있는 자리이며, $i$번째 마디의 끝 세로선에 주어집니다.

문제의 정답을 출력합니다.

• $1 \le n \le 500\,000$

그렇지만 가희 취향의 노래라면 여러 번 반복해서 들을 수 있잖아요.