Gahui and Music

Gahui wrote a song. When the performers reach a Dal Segno, they act as follows.

• If there is a Segno before the Dal Segno, they return to the Segno and play from that position.
• If there is no Segno before the Dal Segno, they return to the beginning and play from the first measure.

Each Dal Segno takes effect only once. When the song has $n$ measures, the performers stop playing once both of the following conditions hold.

• They have played the $n$-th measure.
• The effect of a Dal Segno has not been triggered.

Gahui wants to place at most $2$ Segno or Dal Segno marks at suitable positions so that the audience's satisfaction is maximized. Also, there must be no part that repeats $3$ or more times. Please help Gahui.

The first line contains the number of measures $n$.

The second line contains the information for each measure, separated by spaces. The $i$-th item describes the $i$-th measure. Each item is given in one of 5 formats.

• A number
  • The audience's satisfaction when the $i$-th measure is played. It is an integer between $-500\,000$ and $500\,000$, inclusive.
• S
  • A position where a Segno can be placed, given at the end bar line of the $i$-th measure.
• DS
  • A position where a Dal Segno can be placed, given at the end bar line of the $i$-th measure.
• S or DS
  • A position where either a Segno or a Dal Segno can be placed, given at the end bar line of the $i$-th measure.
• DS or S
  • A position where either a Dal Segno or a Segno can be placed, given at the end bar line of the $i$-th measure.

Print the answer to the problem.

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

But if a song is to Gahui's taste, you can listen to it many times.