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*<sub class="lower-index">*i*</sub> red resources and *b*<sub class="lower-index">*i*</sub> 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*<sub class="lower-index">*i*</sub> - *A*, 0) red tokens, and *max*(*b*<sub class="lower-index">*i*</sub> - *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*<sub class="lower-index">*i*</sub>, *r*<sub class="lower-index">*i*</sub> and *b*<sub class="lower-index">*i*</sub>. *c*<sub class="lower-index">*i*</sub> will be 'R' or 'B', denoting the color of the card as red or blue. *r*<sub class="lower-index">*i*</sub> will be an integer denoting the amount of red resources required to obtain the card, and *b*<sub class="lower-index">*i*</sub> will be an integer denoting the amount of blue resources required to obtain the card (0 ≤ *r*<sub class="lower-index">*i*</sub>, *b*<sub class="lower-index">*i*</sub> ≤ 10<sup class="upper-index">7</sup>).
For the first sample, Hongcow's four moves are as follows: 
 1.  Collect tokens 1.  Buy card 1 1.  Buy card 2 1.  Buy card 3 
For the second sample, one optimal strategy is as follows: 
 1.  Collect tokens 1.  Collect tokens 1.  Buy card 2 1.  Collect tokens 1.  Buy card 3 1.  Buy card 1
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
 
struct t
{
    char c;
    int a, b;
    t(char c, int a, int b): c(c), a(a), b(b) {}
    t() {}
};
 
int n;
vector <t> e;
 
double temp;
double t0 = 1000;
 
double gen_rand()
{
    int x = rand() + 1, y = rand() + 1;
    x %= y;
    return x / (double) y;
}
 
int get_ans()
{
    int r = 0, b = 0;
    int R = 0, B = 0;
    int ans = 0;
    for (int i = 0; i < n; i++)
    {
        int need = max(max(0, max(0, e[i].a - R) - r), max(0, max(0, e[i].b - B) - b));
        ans += need;
        r -= max(0, max(0, e[i].a - R));
        b -= max(0, max(0, e[i].b - B));
        r += need;
        b += need;
        ans++;
        if (e[i].c == 'R')
        {
            R++;
        }
        else
        {
            B++;
        }
    }
    return ans;
}
 
int main()
{
#ifdef ONPC
    freopen("a.in", "r", stdin);
    //freopen("a.out", "w", stdout);
#else
    //freopen("a.in", "r", stdin);
    //freopen("a.out", "w", stdout);
#endif
    srand(time(NULL));
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        char c;
        int r, b;
        cin >> c >> r >> b;
        e.push_back({c, r, b});
    }
    random_shuffle(e.begin(), e.end());
    temp = t0;
    int ans = INT_MAX;
    while (1)
    {
        if (clock() / (double) CLOCKS_PER_SEC >= 1.9)
        {
            cout << ans << endl;
            return 0;
        }
        int cur = get_ans();
        ans = min(ans, cur);
        vector <t> was = e;
        for (int i = 0; i < n * temp / t0; i++)
        {
            swap(e[rand() % n], e[rand() % n]);
        }
        int now = get_ans();
        ans = min(ans, now);
        if (now < cur)
        {
            cur = now;
        }
        else
        {
            e = was;
        }
        temp *= 0.9999;
    }
    cout << ans << endl;
}