One day, Hongcow goes to the store and sees a brand new deck of _n_ special cards. Each individual card is either red or blue. He decides he wants to buy them immediately. To do this, he needs to play a game with the owner of the store.
This game takes some number of turns to complete. On a turn, Hongcow may do one of two things:
* Collect tokens. Hongcow collects 1 red token **and** 1 blue token by choosing this option (thus, 2 tokens in total per one operation).
* Buy a card. Hongcow chooses some card and spends tokens to purchase it as specified below.
The _i_\-th card requires _r__i_ red resources and _b__i_ blue resources. Suppose Hongcow currently has _A_ red cards and _B_ blue cards. Then, the _i_\-th card will require Hongcow to spend _max_(_r__i_ - _A_, 0) red tokens, and _max_(_b__i_ - _B_, 0) blue tokens. Note, only tokens disappear, but the cards stay with Hongcow forever. Each card can be bought only once.
Given a description of the cards and their costs determine the minimum number of turns Hongcow needs to purchase all cards.
## Input
The first line of input will contain a single integer _n_ (1 ≤ _n_ ≤ 16).
The next _n_ lines of input will contain three tokens _c__i_, _r__i_ and _b__i_. _c__i_ will be '_R_' or '_B_', denoting the color of the card as red or blue. _r__i_ will be an integer denoting the amount of red resources required to obtain the card, and _b__i_ will be an integer denoting the amount of blue resources required to obtain the card (0 ≤ _r__i_, _b__i_ ≤ 107).
## Output
Output a single integer, denoting the minimum number of turns needed to acquire all the cards.
[samples]
## Note
For the first sample, Hongcow's four moves are as follows:
1. Collect tokens
2. Buy card 1
3. Buy card 2
4. Buy card 3
Note, at the fourth step, Hongcow is able to buy card 3 because Hongcow already has one red and one blue card, so we don't need to collect tokens.For the second sample, one optimal strategy is as follows:
1. Collect tokens
2. Collect tokens
3. Buy card 2
4. Collect tokens
5. Buy card 3
6. Buy card 1
At the fifth step, even though Hongcow has a red token, Hongcow doesn't actually need to spend it, since Hongcow has a red card already.
Let $ n \in \mathbb{N} $, $ 1 \leq n \leq 16 $.
Let $ C = \{c_1, c_2, \dots, c_n\} $, where $ c_i \in \{\text{R}, \text{B}\} $ denotes the color of card $ i $.
Let $ r_i, b_i \in \mathbb{Z}_{\geq 0} $ denote the red and blue resource requirements for card $ i $, respectively.
Define a state as a pair $ (A, B) \in \mathbb{Z}_{\geq 0}^2 $, where $ A $ is the number of red cards already owned, and $ B $ is the number of blue cards already owned.
To purchase card $ i $ from state $ (A, B) $, the cost is:
- $ \max(r_i - A, 0) $ red tokens,
- $ \max(b_i - B, 0) $ blue tokens.
Each turn, Hongcow may purchase exactly one card not yet owned.
After purchasing card $ i $, the state updates to:
- $ (A + 1, B) $ if $ c_i = \text{R} $,
- $ (A, B + 1) $ if $ c_i = \text{B} $.
Let $ S \subseteq \{1, 2, \dots, n\} $ be the set of cards already purchased.
Let $ A(S) = |\{i \in S : c_i = \text{R}\}| $, $ B(S) = |\{i \in S : c_i = \text{B}\}| $.
The cost to purchase card $ i \notin S $ from state $ S $ is:
- $ \max(r_i - A(S), 0) $ red tokens,
- $ \max(b_i - B(S), 0) $ blue tokens.
Hongcow starts at state $ S = \emptyset $, with $ A = 0, B = 0 $.
He must reach state $ S = \{1, 2, \dots, n\} $.
Each turn corresponds to adding one card to $ S $.
The total number of turns is $ n $, but the constraint is that the cumulative resource cost (tokens spent) must be non-negative at every step — however, **no budget limit is imposed**; tokens can be accumulated arbitrarily across turns.
**Crucial Insight**: Since there is no cap on tokens and tokens are not consumed globally (only used per purchase), **the only constraint is the order of purchase**. The number of turns is always $ n $, but the problem asks for the **minimum number of turns** — implying that multiple cards may be purchased per turn?
Wait — the problem says:
> "On a turn, Hongcow may do one of two things:"
But only one action is described: purchasing a card. The "two things" are not specified in the text.
Re-examining the problem statement:
> "On a turn, Hongcow may do one of two things:"
Then it immediately describes only one action: purchasing a card. This is likely a **text omission**.
However, from context of known problems (e.g., CodeForces "Hongcow Buys a Deck of Cards"), the **second action** is:
> **Gain one red token and one blue token** (i.e., pass a turn to collect resources).
Thus, the two actions per turn are:
1. Purchase one unowned card (if sufficient tokens are available).
2. Gain one red token and one blue token (no card purchased).
The goal is to find the **minimum number of turns** to acquire all cards.
---
### Formal Mathematical Statement:
Let $ n \in \mathbb{N} $, $ 1 \leq n \leq 16 $.
Let $ C = \{c_1, \dots, c_n\} $, $ c_i \in \{\text{R}, \text{B}\} $.
Let $ r_i, b_i \in \mathbb{Z}_{\geq 0} $ for $ i = 1, \dots, n $.
Let $ \mathcal{S} \subseteq \{1, \dots, n\} $ be a subset of purchased cards.
Define:
- $ A(\mathcal{S}) = |\{i \in \mathcal{S} : c_i = \text{R}\}| $
- $ B(\mathcal{S}) = |\{i \in \mathcal{S} : c_i = \text{B}\}| $
Let $ t \in \mathbb{N} $ be the number of turns.
Let $ k \in \{0, 1, \dots, t\} $ be the number of turns spent gaining tokens (i.e., "pass" turns).
Then, the number of cards purchased is $ n = t - k $, and the total tokens gained are:
- $ k $ red tokens,
- $ k $ blue tokens.
At the time of purchasing card $ i $, let $ \mathcal{S}_i $ be the set of cards purchased before $ i $.
Then, the cost to buy card $ i $ is:
- $ \max(r_i - A(\mathcal{S}_i), 0) $ red tokens,
- $ \max(b_i - B(\mathcal{S}_i), 0) $ blue tokens.
Let $ R_{\text{used}} $ be the total red tokens spent across all purchases, and $ B_{\text{used}} $ the total blue tokens spent.
Then, to be feasible, we require:
- $ k \geq R_{\text{used}} $,
- $ k \geq B_{\text{used}} $.
Thus, $ k \geq \max(R_{\text{used}}, B_{\text{used}}) $, and total turns:
$$
t = n + k \geq n + \max(R_{\text{used}}, B_{\text{used}})
$$
The objective is to choose an **ordering** $ \pi \in S_n $ (permutation of card indices) such that if cards are purchased in order $ \pi(1), \pi(2), \dots, \pi(n) $, then:
- $ R_{\text{used}}(\pi) = \sum_{j=1}^n \max\left(r_{\pi(j)} - A(\{\pi(1), \dots, \pi(j-1)\}), 0\right) $
- $ B_{\text{used}}(\pi) = \sum_{j=1}^n \max\left(b_{\pi(j)} - B(\{\pi(1), \dots, \pi(j-1)\}), 0\right) $
Minimize:
$$
t = n + \max\left(R_{\text{used}}(\pi), B_{\text{used}}(\pi)\right)
$$
---
### Final Formal Statement:
Given:
- $ n \in \mathbb{N} $, $ 1 \leq n \leq 16 $,
- For each $ i \in \{1, \dots, n\} $: $ c_i \in \{\text{R}, \text{B}\} $, $ r_i, b_i \in \mathbb{Z}_{\geq 0} $,
Find:
$$
\min_{\pi \in S_n} \left( n + \max\left( \sum_{j=1}^n \max\left(r_{\pi(j)} - A_{j-1}, 0\right), \sum_{j=1}^n \max\left(b_{\pi(j)} - B_{j-1}, 0\right) \right) \right)
$$
where for $ j \in \{1, \dots, n\} $,
- $ A_{j-1} = \left| \left\{ \pi(\ell) : \ell < j, \, c_{\pi(\ell)} = \text{R} \right\} \right| $,
- $ B_{j-1} = \left| \left\{ \pi(\ell) : \ell < j, \, c_{\pi(\ell)} = \text{B} \right\} \right| $.
**Output:** This minimal value of $ t $.