{"raw_statement":[{"iden":"statement","content":"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.\n\nThis game takes some number of turns to complete. On a turn, Hongcow may do one of two things:\n\n*   Collect tokens. Hongcow collects 1 red token **and** 1 blue token by choosing this option (thus, 2 tokens in total per one operation).\n*   Buy a card. Hongcow chooses some card and spends tokens to purchase it as specified below.\n\nThe _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.\n\nGiven a description of the cards and their costs determine the minimum number of turns Hongcow needs to purchase all cards."},{"iden":"input","content":"The first line of input will contain a single integer _n_ (1 ≤ _n_ ≤ 16).\n\nThe 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)."},{"iden":"output","content":"Output a single integer, denoting the minimum number of turns needed to acquire all the cards."},{"iden":"examples","content":"Input\n\n3\nR 0 1\nB 1 0\nR 1 1\n\nOutput\n\n4\n\nInput\n\n3\nR 3 0\nR 2 0\nR 1 0\n\nOutput\n\n6"},{"iden":"note","content":"For the first sample, Hongcow's four moves are as follows:\n\n1.  Collect tokens\n2.  Buy card 1\n3.  Buy card 2\n4.  Buy card 3\n\nNote, 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:\n\n1.  Collect tokens\n2.  Collect tokens\n3.  Buy card 2\n4.  Collect tokens\n5.  Buy card 3\n6.  Buy card 1\n\nAt 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."}],"translated_statement":[{"iden":"statement","content":"一天，Hongcow 去商店看到一套全新的 #cf_span[n] 张特殊卡片。每张卡片要么是红色，要么是蓝色。他决定立即买下它们。为此，他需要与商店老板玩一个游戏。\n\n这个游戏需要若干轮才能完成。在每一轮中，Hongcow 可以执行以下两种操作之一：\n\n第 #cf_span[i] 张卡片需要 #cf_span[ri] 个红色资源和 #cf_span[bi] 个蓝色资源。假设 Hongcow 目前拥有 #cf_span[A] 张红色卡片和 #cf_span[B] 张蓝色卡片，则购买第 #cf_span[i] 张卡片需要花费 #cf_span[max(ri - A, 0)] 个红色令牌和 #cf_span[max(bi - B, 0)] 个蓝色令牌。注意，只有令牌会被消耗，而卡片将永久属于 Hongcow。每张卡片只能购买一次。\n\n给定卡片及其花费的描述，请确定 Hongcow 购买所有卡片所需的最少轮数。\n\n输入的第一行包含一个整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 16])。\n\n接下来的 #cf_span[n] 行每行包含三个标记：#cf_span[ci]、#cf_span[ri] 和 #cf_span[bi]。#cf_span[ci] 将是 '_R_' 或 '_B_'，表示卡片的颜色为红色或蓝色。#cf_span[ri] 是一个整数，表示获取该卡片所需的红色资源量，#cf_span[bi] 是一个整数，表示获取该卡片所需的蓝色资源量（#cf_span[0 ≤ ri, bi ≤ 107]）。\n\n请输出一个整数，表示获取所有卡片所需的最少轮数。\n\n对于第一个样例，Hongcow 的四步操作如下：\n\n对于第二个样例，一种最优策略如下：\n\n"},{"iden":"input","content":"输入的第一行包含一个整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 16])。接下来的 #cf_span[n] 行每行包含三个标记：#cf_span[ci]、#cf_span[ri] 和 #cf_span[bi]。#cf_span[ci] 将是 '_R_' 或 '_B_'，表示卡片的颜色为红色或蓝色。#cf_span[ri] 是一个整数，表示获取该卡片所需的红色资源量，#cf_span[bi] 是一个整数，表示获取该卡片所需的蓝色资源量（#cf_span[0 ≤ ri, bi ≤ 107]）。"},{"iden":"output","content":"请输出一个整数，表示获取所有卡片所需的最少轮数。"},{"iden":"examples","content":"输入\n3\nR 0 1\nB 1 0\nR 1 1\n输出\n4\n\n输入\n3\nR 3 0\nR 2 0\nR 1 0\n输出\n6"},{"iden":"note","content":"对于第一个样例，Hongcow 的四步操作如下：\n收集令牌\n购买第 #cf_span[1] 张卡片\n购买第 #cf_span[2] 张卡片\n购买第 #cf_span[3] 张卡片\n注意，在第四步时，Hongcow 已经拥有一张红色卡片和一张蓝色卡片，因此无需再收集令牌。\n\n对于第二个样例，一种最优策略如下：\n收集令牌\n收集令牌\n购买第 #cf_span[2] 张卡片\n收集令牌\n购买第 #cf_span[3] 张卡片\n购买第 #cf_span[1] 张卡片\n在第五步时，尽管 Hongcow 拥有红色令牌，但他实际上无需花费，因为他已经拥有一张红色卡片。"}],"sample_group":[],"show_order":[],"formal_statement":"**Definitions:**\n- Let $ n \\in \\mathbb{N} $, $ 1 \\leq n \\leq 16 $, be the number of cards.\n- For each card $ i \\in \\{1, 2, \\dots, n\\} $:\n  - Let $ c_i \\in \\{\\text{R}, \\text{B}\\} $ denote its color.\n  - Let $ r_i \\in \\mathbb{Z}_{\\geq 0} $ denote the red resource requirement.\n  - Let $ b_i \\in \\mathbb{Z}_{\\geq 0} $ denote the blue resource requirement.\n\n**State:**\n- Let $ A \\in \\mathbb{Z}_{\\geq 0} $ be the number of red cards already owned.\n- Let $ B \\in \\mathbb{Z}_{\\geq 0} $ be the number of blue cards already owned.\n- Initially, $ A = 0 $, $ B = 0 $.\n\n**Cost to acquire card $ i $ given current state $ (A, B) $:**\n- Red tokens required: $ \\max(r_i - A, 0) $\n- Blue tokens required: $ \\max(b_i - B, 0) $\n\n**Game mechanics:**\n- Each turn, Hongcow may acquire **exactly one** card $ i $, provided he can pay the required tokens.\n- After acquiring card $ i $:\n  - If $ c_i = \\text{R} $, then $ A \\gets A + 1 $\n  - If $ c_i = \\text{B} $, then $ B \\gets B + 1 $\n- Tokens are consumed and do not accumulate; only cards are retained.\n\n**Objective:**\n- Find the minimum number of turns (i.e., the minimum sequence length) to acquire all $ n $ cards.\n\n**Formal Problem:**\nGiven a set $ S = \\{(c_i, r_i, b_i)\\}_{i=1}^n $, find the minimum $ k \\in \\mathbb{N} $ such that there exists a permutation $ \\pi \\in S_n $ (ordering of card acquisitions) where, defining $ (A_0, B_0) = (0, 0) $ and for each $ t = 1 $ to $ k $:\n\n- Let $ i = \\pi(t) $\n- Cost at step $ t $: $ \\max(r_i - A_{t-1}, 0) $ red tokens and $ \\max(b_i - B_{t-1}, 0) $ blue tokens are paid.\n- Update:\n  - $ A_t = A_{t-1} + \\mathbf{1}_{c_i = \\text{R}} $\n  - $ B_t = B_{t-1} + \\mathbf{1}_{c_i = \\text{B}} $\n\nSuch that $ A_k + B_k = n $, and all cards are acquired.\n\n**Output:** Minimum such $ k $.","simple_statement":null,"has_page_source":false}