有一天,红牛去商店,看到一副全新的n张特殊卡牌。每张卡片都是红色或蓝色的。他决定立即购买它们。为此,他需要与商店老板玩游戏。
这个游戏需要一些回合才能完成。在转弯时,红牛可能会做以下两件事之一:
- 收集代币。通过选择此选项,红牛会收集 1 个红色代币和 1 个蓝色代币(因此,每次操作总共会收集 2 个代币)。
- 购买一张卡。红牛选择一些卡并花费代币购买它,如下所示。
第i张卡需要ri红色资源和bi蓝色资源。假设红牛目前有A红牌和B蓝牌。然后,第 i 张卡将要求红牛花费 max(ri - A, 0) 个红色代币和 max(bi - B, 0) 个蓝色代币。注意,只有代币会消失,但卡片会永远留在红牛身边。每张卡只能购买一次。
给定卡牌的描述及其成本决定了红牛购买所有卡牌所需的最少回合数。
输入
输入的第一行将包含一个整数 n (1 ≤ n ≤ 16)。
接下来的 n 行输入将包含三个标记 ci、ri 和 bi。 ci 将为“R”或“B”,表示卡片的颜色为红色或蓝色。 ri 为整数,表示获得卡牌所需的红色资源量,bi 为整数,表示获得卡牌所需的蓝色资源量(0 ≤ ri,bi ≤ 107)。
输出
输出一个整数,表示获得所有牌所需的最小回合数。
示例
输入 #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
注意
对于第一个样本,红牛的四步棋如下:
1.收集代币
2.购买卡1
3.购买卡2
4.购买卡3
对于第二个样本,一种最佳策略如下:
1.收集代币
2.收集代币
3.购买卡2
4.收集代币
5.购买卡3
6.购买卡1