#include <bits/stdc++.h>
#pragma GCC optimize("O3")
using namespace std;
template <class T>
using pq = priority_queue<T>;
template <class T>
using pqg = priority_queue<T, vector<T>, greater<T>>;
int scan() { return getchar(); }
template <class T>
void scan(T a) {
  cin >> a;
}
void scan(int &a) { cin >> a; }
void scan(long long &a) { cin >> a; }
void scan(char &a) { cin >> a; }
void scan(double &a) { cin >> a; }
void scan(long double &a) { cin >> a; }
void scan(char a[]) { scanf("%s", a); }
void scan(string &a) { cin >> a; }
template <class T>
void scan(vector<T> &);
template <class T, size_t size>
void scan(array<T, size> &);
template <class T, class L>
void scan(pair<T, L> &);
template <class T, size_t size>
void scan(T (&)[size]);
template <class T>
void scan(vector<T> &a) {
  for (auto &i : a) scan(i);
}
template <class T>
void scan(deque<T> &a) {
  for (auto &i : a) scan(i);
}
template <class T, size_t size>
void scan(array<T, size> &a) {
  for (auto &i : a) scan(i);
}
template <class T, class L>
void scan(pair<T, L> &p) {
  scan(p.first);
  scan(p.second);
}
template <class T, size_t size>
void scan(T (&a)[size]) {
  for (auto &i : a) scan(i);
}
template <class T>
void scan(T &a) {
  cin >> a;
}
void IN() {}
template <class Head, class... Tail>
void IN(Head &head, Tail &...tail) {
  scan(head);
  IN(tail...);
}
string stin() {
  string s;
  cin >> s;
  return s;
}
template <class T, class S>
inline bool chmax(T &a, S b) {
  if (a < b) {
    a = b;
    return 1;
  }
  return 0;
}
template <class T, class S>
inline bool chmin(T &a, S b) {
  if (a > b) {
    a = b;
    return 1;
  }
  return 0;
}
vector<int> iota(int n) {
  vector<int> a(n);
  iota(begin(a), end(a), 0);
  return a;
}
template <class T>
void UNIQUE(vector<T> &x) {
  sort(begin(x), end(x));
  x.erase(unique(begin(x), end(x)), x.end());
}
int in() {
  int x;
  cin >> x;
  return x;
}
long long lin() {
  unsigned long long x;
  cin >> x;
  return x;
}
void print() { putchar(' '); }
void print(bool a) { cout << a; }
void print(int a) { cout << a; }
void print(long long a) { cout << a; }
void print(char a) { cout << a; }
void print(string &a) { cout << a; }
void print(double a) { cout << a; }
template <class T>
void print(const vector<T> &);
template <class T, size_t size>
void print(const array<T, size> &);
template <class T, class L>
void print(const pair<T, L> &p);
template <class T, size_t size>
void print(const T (&)[size]);
template <class T>
void print(const vector<T> &a) {
  if (a.empty()) return;
  print(a[0]);
  for (auto i = a.begin(); ++i != a.end();) {
    cout << " ";
    print(*i);
  }
  cout << endl;
}
template <class T>
void print(const deque<T> &a) {
  if (a.empty()) return;
  print(a[0]);
  for (auto i = a.begin(); ++i != a.end();) {
    cout << " ";
    print(*i);
  }
}
template <class T, size_t size>
void print(const array<T, size> &a) {
  print(a[0]);
  for (auto i = a.begin(); ++i != a.end();) {
    cout << " ";
    print(*i);
  }
}
template <class T, class L>
void print(const pair<T, L> &p) {
  cout << '(';
  print(p.first);
  cout << ",";
  print(p.second);
  cout << ')';
}
template <class T>
void print(set<T> &x) {
  for (auto e : x) print(e), cout << " ";
  cout << endl;
}
template <class T>
void print(multiset<T> &x) {
  for (auto e : x) print(e), cout << " ";
  cout << endl;
}
template <class T, size_t size>
void print(const T (&a)[size]) {
  print(a[0]);
  for (auto i = a; ++i != end(a);) {
    cout << " ";
    print(*i);
  }
}
template <class T>
void print(const T &a) {
  cout << a;
}
int out() {
  putchar('\n');
  return 0;
}
template <class T>
int out(const T &t) {
  print(t);
  putchar('\n');
  return 0;
}
template <class Head, class... Tail>
int out(const Head &head, const Tail &...tail) {
  print(head);
  putchar(' ');
  out(tail...);
  return 0;
}
long long gcd(long long a, long long b) {
  while (b) {
    long long c = b;
    b = a % b;
    a = c;
  }
  return a;
}
long long lcm(long long a, long long b) {
  if (!a || !b) return 0;
  return a * b / gcd(a, b);
}
vector<pair<long long, long long>> factor(long long x) {
  vector<pair<long long, long long>> ans;
  for (long long i = 2; i * i <= x; i++)
    if (x % i == 0) {
      ans.push_back({i, 1});
      while ((x /= i) % i == 0) ans.back().second++;
    }
  if (x != 1) ans.push_back({x, 1});
  return ans;
}
vector<int> divisor(int x) {
  vector<int> ans;
  for (int i = 1; i * i <= x; i++)
    if (x % i == 0) {
      ans.push_back(i);
      if (i * i != x) ans.push_back(x / i);
    }
  return ans;
}
template <typename T>
void zip(vector<T> &x) {
  vector<T> y = x;
  sort(begin(y), end(y));
  for (int i = 0; i < x.size(); ++i) {
    x[i] = distance((y).begin(), lower_bound(begin(y), end(y), (x[i])));
  }
}
int popcount(long long x) { return __builtin_popcountll(x); }
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int rnd(int n) { return uniform_int_distribution<int>(0, n - 1)(rng); }
template <typename T>
void shuffle(vector<T> &v) {
  for (long long i = v.size() - 1; i >= 1; --i) {
    swap(v[i], v[rnd(i)]);
  }
}
vector<string> YES{"NO", "YES"};
vector<string> Yes{"No", "Yes"};
vector<string> yes{"no", "yes"};
template <class... T>
void err(const T &...) {}
template <typename T>
struct edge {
  int from, to;
  T cost;
  int id;
  edge(int to, T cost) : from(-1), to(to), cost(cost) {}
  edge(int from, int to, T cost) : from(from), to(to), cost(cost) {}
  edge &operator=(const int &x) {
    to = x;
    return *this;
  }
  operator int() const { return to; }
};
template <typename T>
using Edges = vector<edge<T>>;
template <typename T>
using WeightedTree = vector<Edges<T>>;
template <typename T>
using Edges = vector<edge<T>>;
template <typename T>
using WeightedGraph = vector<Edges<T>>;
template <typename T>
using Matrix = vector<vector<T>>;
using Graph = vector<vector<int>>;
using tree = vector<vector<int>>;
tree getTree(int n, int offset = 1) {
  tree res(n);
  for (int i = 0; i < n - 1; i++) {
    int a, b;
    cin >> a >> b;
    a -= offset, b -= offset;
    res[a].emplace_back(b);
    res[b].emplace_back(a);
  }
  return res;
}
template <typename T>
WeightedTree<T> getWeightedTree(int n, int offset = 1) {
  WeightedTree<T> res(n);
  for (int i = 0; i < n - 1; i++) {
    int a, b;
    cin >> a >> b;
    a -= offset, b -= offset;
    T c;
    cin >> c;
    res[a].emplace_back(b, c);
    res[b].emplace_back(a, c);
  }
  return res;
}
Graph getGraph(int n, int m, int offset = 1) {
  Graph res(n);
  for (int i = 0; i < m; ++i) {
    int a, b;
    cin >> a >> b;
    a -= offset, b -= offset;
    res[a].emplace_back(b);
    res[b].emplace_back(a);
  }
  return res;
}
template <typename T>
WeightedGraph<T> getWeightedGraph(int n, int m, int offset = 1) {
  WeightedGraph<T> res(n);
  for (int i = 0; i < m; ++i) {
    int a, b;
    cin >> a >> b;
    T c;
    cin >> c;
    res[a].emplace_back(b, c);
    res[b].emplace_back(a, c);
  }
}
struct Setup_io {
  Setup_io() {
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cout << fixed << setprecision(15);
  }
} setup_io;
template <typename T = int>
struct UnionFind {
  vector<int> data;
  vector<T> sz;
  bool is_default;
  UnionFind(int n) {
    data.assign(n, -1);
    sz.assign(n, 1);
    is_default = true;
  }
  UnionFind(int n, vector<T> &a) {
    data.assign(n, -1);
    sz = a;
    is_default = false;
  }
  bool unite(int x, int y) {
    x = find(x), y = find(y);
    if (x == y) return false;
    if (data[x] > data[y]) swap(x, y);
    data[x] += data[y];
    if (!is_default) sz[x] += sz[y];
    data[y] = x;
    return true;
  }
  bool same(int x, int y) { return find(x) == find(y); }
  int find(int x) {
    if (data[x] < 0) return x;
    return (data[x] = find(data[x]));
  }
  T size(int x) { return (is_default ? -data[find(x)] : sz[find(x)]); }
};
int main() {
  int n;
  IN(n);
  vector<long long> t(n), r(n), b(n);
  long long sumR = 0, sumB = 0;
  for (long long i = 0; i < n; ++i) {
    char c;
    cin >> c;
    t[i] = c == 'R';
    cin >> r[i] >> b[i];
    sumR += r[i], sumB += b[i];
  }
  vector<long long> R(1 << n), B(1 << n);
  for (long long i = 0; i < 1 << n; ++i) {
    for (long long j = 0; j < n; ++j) {
      if (i & (1 << j)) {
        if (t[j])
          R[i]++;
        else
          B[i]++;
      }
    }
  }
  const int N = 241;
  vector<vector<long long>> dp(1 << n, vector<long long>(N, -1));
  dp[0][0] = 0;
  for (long long mask = 0; mask < 1 << n; ++mask) {
    int nr = R[mask], nb = B[mask];
    for (long long i = 0; i < n; ++i) {
      if (mask & 1 << i) continue;
      int tr = min<int>(nr, r[i]), tb = min<int>(nb, b[i]);
      for (long long j = 0; j < N; ++j) {
        if (dp[mask][j] == -1) continue;
        chmax(dp[mask | 1 << i][j + tr], dp[mask][j] + tb);
      }
    }
  }
  long long ans = LLONG_MAX;
  for (long long i = 0; i < N; ++i) {
    if (dp[(1 << n) - 1][i] == -1) continue;
    chmin(ans, n + max(sumR - i, sumB - dp[(1 << n) - 1][i]));
  }
  cout << ans << '\n';
}

### Prompt

Create a solution in cpp for the following problem:

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 ri red resources and bi blue resources. Suppose Hongcow currently has A red cards and B blue cards. Then, the i-th card will require Hongcow to spend max(ri - A, 0) red tokens, and max(bi - 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 ci, ri and bi. ci will be 'R' or 'B', denoting the color of the card as red or blue. ri will be an integer denoting the amount of red resources required to obtain the card, and bi will be an integer denoting the amount of blue resources required to obtain the card (0 ≤ ri, bi ≤ 107).

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.

### Response

```cpp
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
using namespace std;
template <class T>
using pq = priority_queue<T>;
template <class T>
using pqg = priority_queue<T, vector<T>, greater<T>>;
int scan() { return getchar(); }
template <class T>
void scan(T a) {
  cin >> a;
}
void scan(int &a) { cin >> a; }
void scan(long long &a) { cin >> a; }
void scan(char &a) { cin >> a; }
void scan(double &a) { cin >> a; }
void scan(long double &a) { cin >> a; }
void scan(char a[]) { scanf("%s", a); }
void scan(string &a) { cin >> a; }
template <class T>
void scan(vector<T> &);
template <class T, size_t size>
void scan(array<T, size> &);
template <class T, class L>
void scan(pair<T, L> &);
template <class T, size_t size>
void scan(T (&)[size]);
template <class T>
void scan(vector<T> &a) {
  for (auto &i : a) scan(i);
}
template <class T>
void scan(deque<T> &a) {
  for (auto &i : a) scan(i);
}
template <class T, size_t size>
void scan(array<T, size> &a) {
  for (auto &i : a) scan(i);
}
template <class T, class L>
void scan(pair<T, L> &p) {
  scan(p.first);
  scan(p.second);
}
template <class T, size_t size>
void scan(T (&a)[size]) {
  for (auto &i : a) scan(i);
}
template <class T>
void scan(T &a) {
  cin >> a;
}
void IN() {}
template <class Head, class... Tail>
void IN(Head &head, Tail &...tail) {
  scan(head);
  IN(tail...);
}
string stin() {
  string s;
  cin >> s;
  return s;
}
template <class T, class S>
inline bool chmax(T &a, S b) {
  if (a < b) {
    a = b;
    return 1;
  }
  return 0;
}
template <class T, class S>
inline bool chmin(T &a, S b) {
  if (a > b) {
    a = b;
    return 1;
  }
  return 0;
}
vector<int> iota(int n) {
  vector<int> a(n);
  iota(begin(a), end(a), 0);
  return a;
}
template <class T>
void UNIQUE(vector<T> &x) {
  sort(begin(x), end(x));
  x.erase(unique(begin(x), end(x)), x.end());
}
int in() {
  int x;
  cin >> x;
  return x;
}
long long lin() {
  unsigned long long x;
  cin >> x;
  return x;
}
void print() { putchar(' '); }
void print(bool a) { cout << a; }
void print(int a) { cout << a; }
void print(long long a) { cout << a; }
void print(char a) { cout << a; }
void print(string &a) { cout << a; }
void print(double a) { cout << a; }
template <class T>
void print(const vector<T> &);
template <class T, size_t size>
void print(const array<T, size> &);
template <class T, class L>
void print(const pair<T, L> &p);
template <class T, size_t size>
void print(const T (&)[size]);
template <class T>
void print(const vector<T> &a) {
  if (a.empty()) return;
  print(a[0]);
  for (auto i = a.begin(); ++i != a.end();) {
    cout << " ";
    print(*i);
  }
  cout << endl;
}
template <class T>
void print(const deque<T> &a) {
  if (a.empty()) return;
  print(a[0]);
  for (auto i = a.begin(); ++i != a.end();) {
    cout << " ";
    print(*i);
  }
}
template <class T, size_t size>
void print(const array<T, size> &a) {
  print(a[0]);
  for (auto i = a.begin(); ++i != a.end();) {
    cout << " ";
    print(*i);
  }
}
template <class T, class L>
void print(const pair<T, L> &p) {
  cout << '(';
  print(p.first);
  cout << ",";
  print(p.second);
  cout << ')';
}
template <class T>
void print(set<T> &x) {
  for (auto e : x) print(e), cout << " ";
  cout << endl;
}
template <class T>
void print(multiset<T> &x) {
  for (auto e : x) print(e), cout << " ";
  cout << endl;
}
template <class T, size_t size>
void print(const T (&a)[size]) {
  print(a[0]);
  for (auto i = a; ++i != end(a);) {
    cout << " ";
    print(*i);
  }
}
template <class T>
void print(const T &a) {
  cout << a;
}
int out() {
  putchar('\n');
  return 0;
}
template <class T>
int out(const T &t) {
  print(t);
  putchar('\n');
  return 0;
}
template <class Head, class... Tail>
int out(const Head &head, const Tail &...tail) {
  print(head);
  putchar(' ');
  out(tail...);
  return 0;
}
long long gcd(long long a, long long b) {
  while (b) {
    long long c = b;
    b = a % b;
    a = c;
  }
  return a;
}
long long lcm(long long a, long long b) {
  if (!a || !b) return 0;
  return a * b / gcd(a, b);
}
vector<pair<long long, long long>> factor(long long x) {
  vector<pair<long long, long long>> ans;
  for (long long i = 2; i * i <= x; i++)
    if (x % i == 0) {
      ans.push_back({i, 1});
      while ((x /= i) % i == 0) ans.back().second++;
    }
  if (x != 1) ans.push_back({x, 1});
  return ans;
}
vector<int> divisor(int x) {
  vector<int> ans;
  for (int i = 1; i * i <= x; i++)
    if (x % i == 0) {
      ans.push_back(i);
      if (i * i != x) ans.push_back(x / i);
    }
  return ans;
}
template <typename T>
void zip(vector<T> &x) {
  vector<T> y = x;
  sort(begin(y), end(y));
  for (int i = 0; i < x.size(); ++i) {
    x[i] = distance((y).begin(), lower_bound(begin(y), end(y), (x[i])));
  }
}
int popcount(long long x) { return __builtin_popcountll(x); }
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int rnd(int n) { return uniform_int_distribution<int>(0, n - 1)(rng); }
template <typename T>
void shuffle(vector<T> &v) {
  for (long long i = v.size() - 1; i >= 1; --i) {
    swap(v[i], v[rnd(i)]);
  }
}
vector<string> YES{"NO", "YES"};
vector<string> Yes{"No", "Yes"};
vector<string> yes{"no", "yes"};
template <class... T>
void err(const T &...) {}
template <typename T>
struct edge {
  int from, to;
  T cost;
  int id;
  edge(int to, T cost) : from(-1), to(to), cost(cost) {}
  edge(int from, int to, T cost) : from(from), to(to), cost(cost) {}
  edge &operator=(const int &x) {
    to = x;
    return *this;
  }
  operator int() const { return to; }
};
template <typename T>
using Edges = vector<edge<T>>;
template <typename T>
using WeightedTree = vector<Edges<T>>;
template <typename T>
using Edges = vector<edge<T>>;
template <typename T>
using WeightedGraph = vector<Edges<T>>;
template <typename T>
using Matrix = vector<vector<T>>;
using Graph = vector<vector<int>>;
using tree = vector<vector<int>>;
tree getTree(int n, int offset = 1) {
  tree res(n);
  for (int i = 0; i < n - 1; i++) {
    int a, b;
    cin >> a >> b;
    a -= offset, b -= offset;
    res[a].emplace_back(b);
    res[b].emplace_back(a);
  }
  return res;
}
template <typename T>
WeightedTree<T> getWeightedTree(int n, int offset = 1) {
  WeightedTree<T> res(n);
  for (int i = 0; i < n - 1; i++) {
    int a, b;
    cin >> a >> b;
    a -= offset, b -= offset;
    T c;
    cin >> c;
    res[a].emplace_back(b, c);
    res[b].emplace_back(a, c);
  }
  return res;
}
Graph getGraph(int n, int m, int offset = 1) {
  Graph res(n);
  for (int i = 0; i < m; ++i) {
    int a, b;
    cin >> a >> b;
    a -= offset, b -= offset;
    res[a].emplace_back(b);
    res[b].emplace_back(a);
  }
  return res;
}
template <typename T>
WeightedGraph<T> getWeightedGraph(int n, int m, int offset = 1) {
  WeightedGraph<T> res(n);
  for (int i = 0; i < m; ++i) {
    int a, b;
    cin >> a >> b;
    T c;
    cin >> c;
    res[a].emplace_back(b, c);
    res[b].emplace_back(a, c);
  }
}
struct Setup_io {
  Setup_io() {
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cout << fixed << setprecision(15);
  }
} setup_io;
template <typename T = int>
struct UnionFind {
  vector<int> data;
  vector<T> sz;
  bool is_default;
  UnionFind(int n) {
    data.assign(n, -1);
    sz.assign(n, 1);
    is_default = true;
  }
  UnionFind(int n, vector<T> &a) {
    data.assign(n, -1);
    sz = a;
    is_default = false;
  }
  bool unite(int x, int y) {
    x = find(x), y = find(y);
    if (x == y) return false;
    if (data[x] > data[y]) swap(x, y);
    data[x] += data[y];
    if (!is_default) sz[x] += sz[y];
    data[y] = x;
    return true;
  }
  bool same(int x, int y) { return find(x) == find(y); }
  int find(int x) {
    if (data[x] < 0) return x;
    return (data[x] = find(data[x]));
  }
  T size(int x) { return (is_default ? -data[find(x)] : sz[find(x)]); }
};
int main() {
  int n;
  IN(n);
  vector<long long> t(n), r(n), b(n);
  long long sumR = 0, sumB = 0;
  for (long long i = 0; i < n; ++i) {
    char c;
    cin >> c;
    t[i] = c == 'R';
    cin >> r[i] >> b[i];
    sumR += r[i], sumB += b[i];
  }
  vector<long long> R(1 << n), B(1 << n);
  for (long long i = 0; i < 1 << n; ++i) {
    for (long long j = 0; j < n; ++j) {
      if (i & (1 << j)) {
        if (t[j])
          R[i]++;
        else
          B[i]++;
      }
    }
  }
  const int N = 241;
  vector<vector<long long>> dp(1 << n, vector<long long>(N, -1));
  dp[0][0] = 0;
  for (long long mask = 0; mask < 1 << n; ++mask) {
    int nr = R[mask], nb = B[mask];
    for (long long i = 0; i < n; ++i) {
      if (mask & 1 << i) continue;
      int tr = min<int>(nr, r[i]), tb = min<int>(nb, b[i]);
      for (long long j = 0; j < N; ++j) {
        if (dp[mask][j] == -1) continue;
        chmax(dp[mask | 1 << i][j + tr], dp[mask][j] + tb);
      }
    }
  }
  long long ans = LLONG_MAX;
  for (long long i = 0; i < N; ++i) {
    if (dp[(1 << n) - 1][i] == -1) continue;
    chmin(ans, n + max(sumR - i, sumB - dp[(1 << n) - 1][i]));
  }
  cout << ans << '\n';
}

```