{"problem":{"name":"E. Hongcow Buys a Deck of Cards","description":{"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","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF745E"},"statements":[{"statement_type":"Markdown","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.\n\n## Input\n\nThe 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).\n\n## Output\n\nOutput a single integer, denoting the minimum number of turns needed to acquire all the cards.\n\n[samples]\n\n## Note\n\nFor 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.","is_translate":false,"language":"English"},{"statement_type":"Markdown","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## Input\n\n输入的第一行包含一个整数 #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]）。\n\n## Output\n\n输出一个整数，表示获取所有卡片所需的最少轮数。\n\n[samples]\n\n## Note\n\n对于第一个样例，Hongcow 的四步操作如下：\n收集代币\n购买第 #cf_span[1] 张卡片\n购买第 #cf_span[2] 张卡片\n购买第 #cf_span[3] 张卡片\n注意，在第四步，Hongcow 能够购买第 #cf_span[3] 张卡片，因为他已经拥有一张红卡和一张蓝卡，因此无需再收集代币。\n\n对于第二个样例，一种最优策略如下：\n收集代币\n收集代币\n购买第 #cf_span[2] 张卡片\n收集代币\n购买第 #cf_span[3] 张卡片\n购买第 #cf_span[1] 张卡片\n在第五步，尽管 Hongcow 拥有红色代币，但他实际上无需花费，因为他已经拥有一张红卡。","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"Let $ n \\in \\mathbb{N} $, $ 1 \\leq n \\leq 16 $.  \nLet $ C = \\{c_1, c_2, \\dots, c_n\\} $, where $ c_i \\in \\{\\text{R}, \\text{B}\\} $ denotes the color of card $ i $.  \nLet $ r_i, b_i \\in \\mathbb{Z}_{\\geq 0} $ denote the red and blue resource requirements for card $ i $, respectively.\n\nDefine 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.\n\nTo purchase card $ i $ from state $ (A, B) $, the cost is:\n- $ \\max(r_i - A, 0) $ red tokens,\n- $ \\max(b_i - B, 0) $ blue tokens.\n\nEach turn, Hongcow may purchase exactly one card not yet owned.  \nAfter purchasing card $ i $, the state updates to:\n- $ (A + 1, B) $ if $ c_i = \\text{R} $,\n- $ (A, B + 1) $ if $ c_i = \\text{B} $.\n\nLet $ S \\subseteq \\{1, 2, \\dots, n\\} $ be the set of cards already purchased.  \nLet $ A(S) = |\\{i \\in S : c_i = \\text{R}\\}| $, $ B(S) = |\\{i \\in S : c_i = \\text{B}\\}| $.\n\nThe cost to purchase card $ i \\notin S $ from state $ S $ is:\n- $ \\max(r_i - A(S), 0) $ red tokens,\n- $ \\max(b_i - B(S), 0) $ blue tokens.\n\nHongcow starts at state $ S = \\emptyset $, with $ A = 0, B = 0 $.  \nHe must reach state $ S = \\{1, 2, \\dots, n\\} $.\n\nEach turn corresponds to adding one card to $ S $.  \nThe 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.\n\n**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? \n\nWait — the problem says:  \n> \"On a turn, Hongcow may do one of two things:\"\n\nBut only one action is described: purchasing a card. The \"two things\" are not specified in the text.\n\nRe-examining the problem statement:  \n> \"On a turn, Hongcow may do one of two things:\"\n\nThen it immediately describes only one action: purchasing a card. This is likely a **text omission**.\n\nHowever, from context of known problems (e.g., CodeForces \"Hongcow Buys a Deck of Cards\"), the **second action** is:  \n> **Gain one red token and one blue token** (i.e., pass a turn to collect resources).\n\nThus, the two actions per turn are:\n1. Purchase one unowned card (if sufficient tokens are available).\n2. Gain one red token and one blue token (no card purchased).\n\nThe goal is to find the **minimum number of turns** to acquire all cards.\n\n---\n\n### Formal Mathematical Statement:\n\nLet $ n \\in \\mathbb{N} $, $ 1 \\leq n \\leq 16 $.  \nLet $ C = \\{c_1, \\dots, c_n\\} $, $ c_i \\in \\{\\text{R}, \\text{B}\\} $.  \nLet $ r_i, b_i \\in \\mathbb{Z}_{\\geq 0} $ for $ i = 1, \\dots, n $.\n\nLet $ \\mathcal{S} \\subseteq \\{1, \\dots, n\\} $ be a subset of purchased cards.  \nDefine:\n- $ A(\\mathcal{S}) = |\\{i \\in \\mathcal{S} : c_i = \\text{R}\\}| $\n- $ B(\\mathcal{S}) = |\\{i \\in \\mathcal{S} : c_i = \\text{B}\\}| $\n\nLet $ t \\in \\mathbb{N} $ be the number of turns.  \nLet $ k \\in \\{0, 1, \\dots, t\\} $ be the number of turns spent gaining tokens (i.e., \"pass\" turns).  \nThen, the number of cards purchased is $ n = t - k $, and the total tokens gained are:\n- $ k $ red tokens,\n- $ k $ blue tokens.\n\nAt the time of purchasing card $ i $, let $ \\mathcal{S}_i $ be the set of cards purchased before $ i $.  \nThen, the cost to buy card $ i $ is:\n- $ \\max(r_i - A(\\mathcal{S}_i), 0) $ red tokens,\n- $ \\max(b_i - B(\\mathcal{S}_i), 0) $ blue tokens.\n\nLet $ R_{\\text{used}} $ be the total red tokens spent across all purchases, and $ B_{\\text{used}} $ the total blue tokens spent.\n\nThen, to be feasible, we require:\n- $ k \\geq R_{\\text{used}} $,\n- $ k \\geq B_{\\text{used}} $.\n\nThus, $ k \\geq \\max(R_{\\text{used}}, B_{\\text{used}}) $, and total turns:\n$$\nt = n + k \\geq n + \\max(R_{\\text{used}}, B_{\\text{used}})\n$$\n\nThe 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:\n- $ R_{\\text{used}}(\\pi) = \\sum_{j=1}^n \\max\\left(r_{\\pi(j)} - A(\\{\\pi(1), \\dots, \\pi(j-1)\\}), 0\\right) $\n- $ B_{\\text{used}}(\\pi) = \\sum_{j=1}^n \\max\\left(b_{\\pi(j)} - B(\\{\\pi(1), \\dots, \\pi(j-1)\\}), 0\\right) $\n\nMinimize:\n$$\nt = n + \\max\\left(R_{\\text{used}}(\\pi), B_{\\text{used}}(\\pi)\\right)\n$$\n\n---\n\n### Final Formal Statement:\n\nGiven:\n- $ n \\in \\mathbb{N} $, $ 1 \\leq n \\leq 16 $,\n- For each $ i \\in \\{1, \\dots, n\\} $: $ c_i \\in \\{\\text{R}, \\text{B}\\} $, $ r_i, b_i \\in \\mathbb{Z}_{\\geq 0} $,\n\nFind:\n$$\n\\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)\n$$\nwhere for $ j \\in \\{1, \\dots, n\\} $,\n- $ A_{j-1} = \\left| \\left\\{ \\pi(\\ell) : \\ell < j, \\, c_{\\pi(\\ell)} = \\text{R} \\right\\} \\right| $,\n- $ B_{j-1} = \\left| \\left\\{ \\pi(\\ell) : \\ell < j, \\, c_{\\pi(\\ell)} = \\text{B} \\right\\} \\right| $.\n\n**Output:** This minimal value of $ t $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF745E","tags":["dp"],"sample_group":[["3\nR 0 1\nB 1 0\nR 1 1","4"],["3\nR 3 0\nR 2 0\nR 1 0","6"]],"created_at":"2026-03-03 11:00:39"}}