Tea or Coffee First - Repovive Premier Round 8 | Repovive

24E. Tea or Coffee First

2500 pts2s256 MB

There are $n$ guests. Guest $i$ wants to drink $a_i$ cups of tea and $b_i$ cups of coffee.

Each guest has a fixed preference $c_i$ :

If $c_i=\mathrm{T}$ , they must drink all their tea before drinking any coffee.
If $c_i=\mathrm{C}$ , they must drink all their coffee before drinking any tea.

In one round, you choose one drink and any subset of the guests. Each selected guest receives and drinks exactly one cup of that drink. The other guests drink nothing in that round.

Find the minimum number of rounds needed to serve every guest exactly the requested number of cups, respecting their preferences.

Constraints

$1 \le t \le 100$
$1 \le n \le 2000$
$1 \le a_i,b_i \le 10^9$
$c_i \in \{\mathrm{T},\mathrm{C}\}$
The sum of $n$ over all test cases is at most $2000$ .

Input

t

\left. \begin{array}{l} n \\ a_1 \quad b_1 \quad c_1 \\ a_2 \quad b_2 \quad c_2 \\ \vdots \\ a_n \quad b_n \quad c_n \end{array} \right\} \times t

Output

\left. \begin{array}{l} \mathrm{answer} \end{array} \right\} \times t

Samples

Input

Case 1

1
2 3 T

Case 2

2
1 1 T
1 1 C

Explanation

Case 1

Serve tea in the first two rounds and coffee in the next three rounds. The only guest needs five cups and can drink at most one cup per round, so five rounds are necessary.

Case 2

Use the drink sequence T, C, T. The first guest drinks in rounds $1$ and $2$ , and the second guest drinks in rounds $2$ and $3$ . Two rounds cannot satisfy both opposite preferences.

Output

Case 1

Case 2

Input

Case 1

2
2 1 T
1 3 T

Case 2

Case 3

2
2 3 T
4 1 C

Explanation

Case 1

Use the drink sequence T, T, C, C, C. The first guest drinks in rounds $1,2,3$ , and the second guest drinks in rounds $1,3,4,5$ . At least two tea rounds and three coffee rounds are necessary, so the answer is five.

Case 2

Use the drink sequence T, C, C, T, T, C. The first guest drinks in rounds $1,4,5,6$ , the second in rounds $1,2,3,6$ , and the third in rounds $2,3,4,5$ . At least three tea rounds and three coffee rounds are necessary, so six is optimal.

Case 3

Use the drink sequence C, T, T, T, T, C, C, C. The first guest drinks in rounds $2,3,6,7,8$ , and the second in rounds $1,2,3,4,5$ . Seven rounds would have to consist of exactly four tea rounds and three coffee rounds. The second guest would need a coffee before all four tea rounds, while the first would still need three coffees after drinking tea. This is impossible with only three coffee rounds, so eight is optimal.

Output

Case 1

Case 2

Case 3

There are $n$ guests. Guest $i$ wants to drink $a_i$ cups of tea and $b_i$ cups of coffee.

Each guest has a fixed preference $c_i$ :

If $c_i=\mathrm{T}$ , they must drink all their tea before drinking any coffee.
If $c_i=\mathrm{C}$ , they must drink all their coffee before drinking any tea.

In one round, you choose one drink and any subset of the guests. Each selected guest receives and drinks exactly one cup of that drink. The other guests drink nothing in that round.

Find the minimum number of rounds needed to serve every guest exactly the requested number of cups, respecting their preferences.

$1 \le t \le 100$
$1 \le n \le 2000$
$1 \le a_i,b_i \le 10^9$
$c_i \in \{\mathrm{T},\mathrm{C}\}$
The sum of $n$ over all test cases is at most $2000$ .

t

\left. \begin{array}{l} n \\ a_1 \quad b_1 \quad c_1 \\ a_2 \quad b_2 \quad c_2 \\ \vdots \\ a_n \quad b_n \quad c_n \end{array} \right\} \times t

\left. \begin{array}{l} \mathrm{answer} \end{array} \right\} \times t

Use the drink sequence T, C, T. The first guest drinks in rounds $1$ and $2$ , and the second guest drinks in rounds $2$ and $3$ . Two rounds cannot satisfy both opposite preferences.

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

24E. Tea or Coffee First

Constraints

Input

Output

Samples

24E. Tea or Coffee First

Constraints

Input

Output

Samples