Hongcow Buys a Deck of Cards

题意翻译

Hongcow 在玩游戏，它需要收集 $n$ 张卡牌。 第 $i$ 张卡片有一种颜色 $\texttt{R}$ 或者 $\texttt{B}$，对应红色或者蓝色。它需要 $r_i$ 个红宝石和 $b_i$ 个蓝宝石才能收集。 但是如果 Hongcow 现在有 $A$ 张红色卡片和 $B$ 张蓝色卡片，它只需要花费 $\max(r_i-A,0)$ 个红宝石和 $\max(b_i-B,0)$ 个蓝宝石就可以收集第 $i$ 张卡片。 每一轮，Hongcow 可以做以下操作之一： + 获得一个红宝石和一个蓝宝石。 + 买一张卡片。 Hongcow 想要尽量快地收集所有卡牌。 它问你至少需要多少回合。 $1\le n\le 16,0\le r_i,b_i\le 10^7$。

题目描述

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.

输入输出格式

输入格式

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}<=10^{7} $ ).

输出格式

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

输入输出样例

输入样例 #1

3
R 0 1
B 1 0
R 1 1

输出样例 #1

4

输入样例 #2

3
R 3 0
R 2 0
R 1 0

输出样例 #2

6

说明

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.