No tag edit access

C. Hongcow Buys a Deck of Cards

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputOne 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.

Input

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

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

Examples

Input

3

R 0 1

B 1 0

R 1 1

Output

4

Input

3

R 3 0

R 2 0

R 1 0

Output

6

Note

For the first sample, Hongcow's four moves are as follows:

- Collect tokens
- Buy card 1
- Buy card 2
- Buy card 3

For the second sample, one optimal strategy is as follows:

- Collect tokens
- Collect tokens
- Buy card 2
- Collect tokens
- Buy card 3
- Buy card 1

Codeforces (c) Copyright 2010-2017 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jun/23/2017 16:51:00 (c4).

Desktop version, switch to mobile version.

User lists

Name |
---|