CF744C.Hongcow Buys a Deck of Cards

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.

一天，Hongcow 来到商店，看到了一套全新的、共 $n$ 张的特殊卡片。每张卡片要么是红色，要么是蓝色。他当即决定买下整套卡片。为此，他需要与店主玩一个游戏。

这个游戏需要若干轮才能完成。在每一轮中，Hongcow 可以执行以下两种操作之一：

• 收集代币：Hongcow 选择此操作，即可获得 1 枚红色代币和 1 枚蓝色代币（即每次操作共获得 2 枚代币）。
• 购买一张卡片：Hongcow 选择某张卡片，并按如下规则花费代币来购买它。

第 $i$ 张卡片需要 $r_i$ 个红色资源和 $b_i$ 个蓝色资源。假设 Hongcow 当前已拥有 $A$ 张红色卡片和 $B$ 张蓝色卡片，则购买第 $i$ 张卡片需消耗 $\max(r_i - A,\, 0)$ 枚红色代币和 $\max(b_i - B,\, 0)$ 枚蓝色代币。注意：只有代币会被消耗，而卡片一旦购得便永远归 Hongcow 所有。每张卡片只能购买一次。

给定所有卡片及其资源需求，求 Hongcow 购买全部卡片所需的最少轮数。

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).

输入的第一行包含一个整数 $n$（$1 \leq n \leq 16$）。

接下来的 $n$ 行每行包含三个标记：$c_i$、$r_i$ 和 $b_i$。其中 $c_i$ 为字符 'R' 或 'B'，表示该卡牌的颜色为红色或蓝色；$r_i$ 是一个整数，表示获取该卡牌所需的红色资源数量；$b_i$ 是一个整数，表示获取该卡牌所需的蓝色资源数量（$0 \leq r_i, b_i \leq 10^7$）。

Output a single integer, denoting the minimum number of turns needed to acquire all the cards.

输出一个整数，表示获取所有卡片所需的最少回合数。

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.

对于第一个样例，Hongcow 的四步操作如下：

1. 收集代币
2. 购买卡片 1
3. 购买卡片 2
4. 购买卡片 3

注意：在第四步中，Hongcow 能够购买卡片 3，是因为 Hongcow 已经拥有一张红色卡片和一张蓝色卡片，因此无需再收集代币。

对于第二个样例，一种最优策略如下：

1. 收集代币
2. 收集代币
3. 购买卡片 2
4. 收集代币
5. 购买卡片 3
6. 购买卡片 1

在第五步中，尽管 Hongcow 拥有一个红色代币，但实际上并不需要花费它，因为 Hongcow 已经拥有一张红色卡片。