가희와 음악

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

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

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

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

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

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

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

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

문제의 정답을 출력해 주세요.

• $1 ≤ n ≤ 500\,000$

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