|Codeforces Round #385 (Div. 1)|
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:
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 ≤ 107).
Output a single integer, denoting the minimum number of turns needed to acquire all the cards.
R 0 1
B 1 0
R 1 1
R 3 0
R 2 0
R 1 0
For the first sample, Hongcow's four moves are as follows:
For the second sample, one optimal strategy is as follows: