Hongcow Buys a Deck of Cards

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:

• 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⁷).

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:

1. Collect tokens
2. Buy card 1
3. Buy card 2
4. Buy card 3

Note, 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:

1. Collect tokens
2. Collect tokens
3. Buy card 2
4. Collect tokens
5. Buy card 3
6. Buy card 1

At 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.

#include <bits/stdc++.h>

using namespace std;

const int N = 77777;
const int MAX = 300;

int f[N][MAX];
int cR[N], cB[N];
int r[N], b[N];
bool type[N];

int main() {
int n;
scanf("%d", &n);
for (int i = 0; i < n; i++) {
    char ch = getchar();
    while (ch != 'R' && ch != 'B') {
      ch = getchar();
    }
    type[i] = (ch == 'R');
    scanf("%d %d", r + i, b + i);
  }
  for (int t = 0; t < (1 << n); t++) {
    cR[t] = cB[t] = 0;
    for (int i = 0; i < n; i++) {
      if (t & (1 << i)) {
        cR[t] += (type[i] == true);
        cB[t] += (type[i] == false);
      }
    }
  }
  for (int t = 0; t < (1 << n); t++) {
    for (int ar = 0; ar < MAX; ar++) {
      f[t][ar] = -1;
    }
  }
  f[0][0] = 0;
  for (int t = 0; t < (1 << n); t++) {
    for (int ar = 0; ar < MAX; ar++) {
      int ft = f[t][ar];
      if (ft == -1) {
        continue;
      }
      for (int i = 0; i < n; i++) {
        if (t & (1 << i)) {
          continue;
        }
        int new_ar = ar + min(r[i], cR[t]);
        int new_ab = ft + min(b[i], cB[t]);
        if (new_ab > f[t + (1 << i)][new_ar]) {
          f[t + (1 << i)][new_ar] = new_ab;
        }
      }
    }
  }
  int allR = 0, allB = 0;
  for (int i = 0; i < n; i++) {
    allR += r[i];
    allB += b[i];
  }
  int ans = max(allR, allB);
  for (int ar = 0; ar < MAX; ar++) {
    int ab = f[(1 << n) - 1][ar];
    if (ab == -1) {
      continue;
    }
    ans = min(ans, max(allR - ar, allB - ab));
  }
  printf("%d\n", ans + n);
  return 0;
}