Opposite Workflows - Repovive Standard Round 7 | Repovive

22B. Opposite Workflows

1000 pts2s256 MB

A workshop has two machines, $A$ and $B$ , and needs to prepare $n$ pieces.

Piece $i$ must be processed for $a_i$ minutes on each machine. Its processing order is determined by $s_i$ :

If $s_i$ is A, it must be processed on machine $A$ first, then on machine $B$ .
If $s_i$ is B, it must be processed on machine $B$ first, then on machine $A$ .

Each machine can process at most one piece at a time. Once processing a piece on a machine starts, it cannot be interrupted. A piece may wait between its two stages. The machines may work simultaneously on different pieces.

All pieces are available at time $0$ . You may choose when to start each stage, subject to these rules.

Find the minimum time by which all pieces can finish processing on both machines.

Constraints

$1 \le t \le 10^4$
$1 \le n \le 2 \times 10^5$
$1 \le a_i \le 10^9$
$s_i$ is either A or B.
The sum of $n$ over all test cases is at most $2 \times 10^5$ .

Input

t

\left. \begin{array}{l} n \\ a_1 \quad s_1 \\ a_2 \quad s_2 \\ \vdots \\ a_n \quad s_n \end{array} \right\} \times t

Output

\left. \begin{array}{l} \text{minimum completion time} \end{array} \right\} \times t

Samples

Input

Case 1

1
4 A

Case 2

2
3 A
3 B

Explanation

Case 1

The only piece needs 4 minutes on A followed by 4 minutes on B, so it finishes at time 8.

Case 2

Process piece 1 on A and piece 2 on B from time 0 to time 3. Then swap the pieces between the machines and process them from time 3 to time 6. Each piece needs 6 minutes in total, so finishing earlier is impossible.

Output

Case 1

Case 2

Input

Case 1

3
2 A
2 A
2 A

Case 2

3
6 A
2 B
1 B

Case 3

3
3 A
2 A
4 B

Explanation

Case 1

A processes pieces 1, 2, and 3 during $[0, 2]$ , $[2, 4]$ , and $[4, 6]$ . B processes them during $[2, 4]$ , $[4, 6]$ , and $[6, 8]$ . Machine B cannot start before time 2 and needs 6 minutes of processing, so finishing earlier than time 8 is impossible.

Case 2

A processes piece 1 during $[0, 6]$ , piece 2 during $[6, 8]$ , and piece 3 during $[8, 9]$ . B processes piece 2 during $[0, 2]$ , piece 3 during $[2, 3]$ , and piece 1 during $[6, 12]$ . Piece 1 alone needs 12 minutes across its two stages, so this schedule is optimal.

Case 3

A processes pieces 1, 2, and 3 during $[0, 3]$ , $[3, 5]$ , and $[5, 9]$ . B processes pieces 3, 1, and 2 during $[0, 4]$ , $[4, 7]$ , and $[7, 9]$ . Each machine has 9 minutes of work, so this schedule is optimal.

Output

Case 1

Case 2

Case 3

A workshop has two machines, $A$ and $B$ , and needs to prepare $n$ pieces.

Piece $i$ must be processed for $a_i$ minutes on each machine. Its processing order is determined by $s_i$ :

If $s_i$ is A, it must be processed on machine $A$ first, then on machine $B$ .
If $s_i$ is B, it must be processed on machine $B$ first, then on machine $A$ .

All pieces are available at time $0$ . You may choose when to start each stage, subject to these rules.

Find the minimum time by which all pieces can finish processing on both machines.

$1 \le t \le 10^4$
$1 \le n \le 2 \times 10^5$
$1 \le a_i \le 10^9$
$s_i$ is either A or B.
The sum of $n$ over all test cases is at most $2 \times 10^5$ .

t

\left. \begin{array}{l} n \\ a_1 \quad s_1 \\ a_2 \quad s_2 \\ \vdots \\ a_n \quad s_n \end{array} \right\} \times t

\left. \begin{array}{l} \text{minimum completion time} \end{array} \right\} \times t

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

22B. Opposite Workflows

Constraints

Input

Output

Samples

22B. Opposite Workflows

Constraints

Input

Output

Samples