A. Ace Race
time limit per test
0.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

In the world of high-speed racing, only the most skilled competitors can navigate the treacherous track to reach the finish line in record time. You are one such racer, aiming to win the prestigious "Ace Race" by reaching the goal as fast as possible.

The race track is a straight path with $$$N$$$ cells, numbered from $$$1$$$ to $$$N$$$ from left to right. You start the race at cell $$$1$$$, and your goal is to reach cell $$$N$$$. You can move to adjacent cells at any time, where cell $$$x$$$ is adjacent to cells $$$x-1$$$ and $$$x+1$$$. Normally, moving from cell $$$x$$$ to cell $$$x+1$$$ or $$$x-1$$$ takes $$$2$$$ seconds.

Along the track, some cells contain powerups that can either help or challenge your progress. Your task is to strategize the use of these powerups and determine the fastest way to reach the finish line.

There are three possible types of cells:

  1. Speed Boost (S t): This cell contains a powerup which, when activated, grants you a speed boost for your next $$$t$$$ moves. When a speed boost is active, you can move to an adjacent cell in just 1 second instead of the usual 2 seconds.
    • Multiple speed boosts can be active simultaneously, and their duration will not stack.
    • e.g. Suppose you start on cell $$$1$$$, activate a speed boost that lasts for your next $$$7$$$ moves, move to cell $$$2$$$, activate a speed boost that lasts for your next $$$4$$$ moves, and move to cell $$$3$$$. You now still have two speed boosts active, one lasts for your next $$$5$$$ moves and one lasts for your next $$$3$$$ moves.
  2. Jump Pad (J d): This cell contains a powerup which, when activated, takes 1 second to teleport you to cell $$$d$$$, bypassing all cells in between. However, any active speed boosts will be removed upon activating a jump pad.
  3. Regular Cell (X): This cell has no powerup.

As the racer, you have complete control over which powerups to use. If you land on a Speed Boost or Jump Pad cell, you may choose whether or not to activate the powerup. Importantly, you have the option to activate the powerup each time you land on the cell, meaning the same powerup can be used multiple times if you return to that cell during your race.

Your challenge is to reach cell $$$N$$$ in the minimum possible time.

Input

The first line contains a single integer $$$N$$$ ($$$2 \leq N \leq 10^5$$$), the number of cells on the race track.

The next $$$N$$$ lines contain the info for each cell. The $$$i$$$-th line describes cell $$$i$$$, it starts with a single uppercase letter $$$C_i$$$, describing the type of the cell $$$i$$$:

  • If $$$C_i = \texttt{S}$$$, then an integer follows: $$$T_i$$$ ($$$1 \leq T_i \leq N$$$), the duration of Speed Boost powerup in cell $$$i$$$.
  • If $$$C_i = \texttt{J}$$$, then an integer follows: $$$D_i$$$ ($$$1 \leq D_i \leq N$$$), the destination cell of Jump Pad powerup in cell $$$i$$$.
  • If $$$C_i = \texttt{X}$$$, then nothing follows.
Output

Output a single integer: the minimum time (in seconds) required to reach cell $$$N$$$.

Examples
Input
8
J 5
X
J 8
X
S 2
X
X
X
Output
4
Input
7
X
X
S 2
S 1
X
J 1
X
Output
10
Note

Consider sample 1, the optimal path is as follows:

  • Start at cell 1.
  • Activate the Jump Pad in cell 1, teleporting to cell 5 (1 second).
  • Activate the Speed Boost in cell 5.
  • Move to cell 4 (1 second).
  • Move to cell 3 (1 second).
  • Activate Jump Pad in cell 3, teleporting to cell 8 (1 second).

The time required to reach the goal is 4 seconds with this path. It can be proven that it is not possible to reach the goal in a shorter time.