#include <bits/stdc++.h>
using namespace std;
namespace {
using Integer = long long;
template <class T, class S>
istream& operator>>(istream& is, pair<T, S>& p) {
  return is >> p.first >> p.second;
}
template <class T>
istream& operator>>(istream& is, vector<T>& vec) {
  for (T& val : vec) is >> val;
  return is;
}
template <class T>
istream& operator,(istream& is, T& val) {
  return is >> val;
}
template <class T, class S>
ostream& operator<<(ostream& os, const pair<T, S>& p) {
  return os << p.first << " " << p.second;
}
template <class T>
ostream& operator<<(ostream& os, const vector<T>& vec) {
  for (size_t i = 0; i < vec.size(); i++)
    os << vec[i] << (i == vec.size() - 1 ? "" : " ");
  return os;
}
template <class T>
ostream& operator,(ostream& os, const T& val) {
  return os << " " << val;
}
template <class H>
void print(const H& head) {
  cout << head;
}
template <class H, class... T>
void print(const H& head, const T&... tail) {
  cout << head << " ";
  print(tail...);
}
template <class... T>
void println(const T&... values) {
  print(values...);
  cout << endl;
}
template <class H>
void eprint(const H& head) {
  cerr << head;
}
template <class H, class... T>
void eprint(const H& head, const T&... tail) {
  cerr << head << " ";
  eprint(tail...);
}
template <class... T>
void eprintln(const T&... values) {
  eprint(values...);
  cerr << endl;
}
class range {
  Integer start_, end_, step_;

 public:
  struct range_iterator {
    Integer val, step_;
    range_iterator(Integer v, Integer step) : val(v), step_(step) {}
    Integer operator*() { return val; }
    void operator++() { val += step_; }
    bool operator!=(range_iterator& x) {
      return step_ > 0 ? val < x.val : val > x.val;
    }
  };
  range(Integer len) : start_(0), end_(len), step_(1) {}
  range(Integer start, Integer end) : start_(start), end_(end), step_(1) {}
  range(Integer start, Integer end, Integer step)
      : start_(start), end_(end), step_(step) {}
  range_iterator begin() { return range_iterator(start_, step_); }
  range_iterator end() { return range_iterator(end_, step_); }
};
inline string operator"" _s(const char* str, size_t size) {
  return move(string(str));
}
constexpr Integer my_pow(Integer x, Integer k, Integer z = 1) {
  return k == 0    ? z
         : k == 1  ? z * x
         : (k & 1) ? my_pow(x * x, k >> 1, z * x)
                   : my_pow(x * x, k >> 1, z);
}
constexpr Integer my_pow_mod(Integer x, Integer k, Integer M, Integer z = 1) {
  return k == 0    ? z % M
         : k == 1  ? z * x % M
         : (k & 1) ? my_pow_mod(x * x % M, k >> 1, M, z * x % M)
                   : my_pow_mod(x * x % M, k >> 1, M, z);
}
constexpr unsigned long long operator"" _ten(unsigned long long value) {
  return my_pow(10, value);
}
inline int k_bit(Integer x, int k) { return (x >> k) & 1; }
mt19937 mt(chrono::duration_cast<chrono::nanoseconds>(
               chrono::steady_clock::now().time_since_epoch())
               .count());
template <class T>
string join(const vector<T>& v, const string& sep) {
  stringstream ss;
  for (size_t i = 0; i < v.size(); i++) {
    if (i > 0) ss << sep;
    ss << v[i];
  }
  return ss.str();
}
inline string operator*(string s, int k) {
  string ret;
  while (k) {
    if (k & 1) ret += s;
    s += s;
    k >>= 1;
  }
  return ret;
}
}  // namespace
constexpr long long mod = 9_ten + 7;
template <class Value = int>
class SegmentTree {
  int n;
  vector<Value> V;
  Value DEFAULT_VALUE;
  static Value default_evaluate(Value a, Value b) { return max(a, b); }
  function<Value(Value, Value)> evaluate;
  Value RangeEvaluation(int a, int b, int at, int l, int r) {
    if (r <= a || b <= l) return DEFAULT_VALUE;
    if (a <= l && r <= b)
      return V[at];
    else {
      Value val_left = RangeEvaluation(a, b, at * 2 + 1, l, (l + r) / 2);
      Value val_right = RangeEvaluation(a, b, at * 2 + 2, (l + r) / 2, r);
      return evaluate(val_left, val_right);
    }
  }

 public:
  SegmentTree(int size, Value DEFAULT = 0,
              function<Value(Value, Value)> eval = default_evaluate) {
    DEFAULT_VALUE = DEFAULT;
    evaluate = eval;
    n = 1;
    while (n < size) n <<= 1;
    V = vector<Value>(2 * n - 1, DEFAULT_VALUE);
  }
  void update(int at, Value new_val) {
    at += n - 1;
    V[at] = new_val;
    while (at > 0) {
      at = (at - 1) / 2;
      V[at] = evaluate(V[at * 2 + 1], V[at * 2 + 2]);
    }
  }
  Value RangeEvaluation(int l, int r) {
    if (l >= r) return DEFAULT_VALUE;
    if (l >= n) return DEFAULT_VALUE;
    return RangeEvaluation(l, r, 0, 0, n);
  }
};
int main() {
  int n, c, d;
  cin >> n, c, d;
  vector<pair<int, int>> cc, dd;
  int mx_c = -1000000, mx_d = -1000000;
  for (auto i : range(n)) {
    int x, y;
    string s;
    cin >> x, y, s;
    if (s == "C") {
      if (y > c) continue;
      cc.push_back({x, y});
      mx_c = max<int>(mx_c, x);
    } else if (s == "D") {
      if (y > d) continue;
      dd.push_back({x, y});
      mx_d = max<int>(mx_d, x);
    } else {
      abort();
    }
  }
  int ans = 0;
  ans = max(ans, mx_c + mx_d);
  vector<vector<int>> vc(100010), vd(100010);
  for (int i = 0; i < cc.size(); i++) {
    vc[cc[i].second].push_back(cc[i].first);
  }
  for (int i = 0; i < dd.size(); i++) {
    vd[dd[i].second].push_back(dd[i].first);
  }
  SegmentTree<int> tc(100010), td(100010);
  for (int i = 0; i < vc.size(); i++) {
    if (vc[i].size() == 0) continue;
    sort(vc[i].rbegin(), vc[i].rend());
    tc.update(i, vc[i][0]);
  }
  for (int i = 0; i < vd.size(); i++) {
    if (vd[i].size() == 0) continue;
    sort(vd[i].rbegin(), vd[i].rend());
    td.update(i, vd[i][0]);
  }
  for (int t = 0; t < 2; t++) {
    for (int i = 1; i < c; i++) {
      int rc = min(i, c - i);
      if (rc <= 0) continue;
      if (vc[i].size() == 0) continue;
      if (rc > i) continue;
      if (rc == i) {
        int l_max = tc.RangeEvaluation(0, rc);
        if (l_max != 0) ans = max(ans, l_max + vc[i][0]);
        if (vc[i].size() >= 2) {
          ans = max(ans, vc[i][0] + vc[i][1]);
        }
      } else {
        int l_max = tc.RangeEvaluation(0, rc + 1);
        if (l_max != 0) ans = max(ans, l_max + vc[i][0]);
      }
    }
    swap(c, d);
    swap(vc, vd);
    swap(tc, td);
  }
  assert(ans >= 0);
  println(ans);
  return 0;
}

### Prompt

Construct a Cpp code solution to the problem outlined:

Arkady plays Gardenscapes a lot. Arkady wants to build two new fountains. There are n available fountains, for each fountain its beauty and cost are known. There are two types of money in the game: coins and diamonds, so each fountain cost can be either in coins or diamonds. No money changes between the types are allowed.

Help Arkady to find two fountains with maximum total beauty so that he can buy both at the same time.

Input

The first line contains three integers n, c and d (2 ≤ n ≤ 100 000, 0 ≤ c, d ≤ 100 000) — the number of fountains, the number of coins and diamonds Arkady has.

The next n lines describe fountains. Each of these lines contain two integers bi and pi (1 ≤ bi, pi ≤ 100 000) — the beauty and the cost of the i-th fountain, and then a letter "C" or "D", describing in which type of money is the cost of fountain i: in coins or in diamonds, respectively.

Output

Print the maximum total beauty of exactly two fountains Arkady can build. If he can't build two fountains, print 0.

Examples

Input

3 7 6
10 8 C
4 3 C
5 6 D


Output

9


Input

2 4 5
2 5 C
2 1 D


Output

0


Input

3 10 10
5 5 C
5 5 C
10 11 D


Output

10

Note

In the first example Arkady should build the second fountain with beauty 4, which costs 3 coins. The first fountain he can't build because he don't have enough coins. Also Arkady should build the third fountain with beauty 5 which costs 6 diamonds. Thus the total beauty of built fountains is 9.

In the second example there are two fountains, but Arkady can't build both of them, because he needs 5 coins for the first fountain, and Arkady has only 4 coins. 

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
namespace {
using Integer = long long;
template <class T, class S>
istream& operator>>(istream& is, pair<T, S>& p) {
  return is >> p.first >> p.second;
}
template <class T>
istream& operator>>(istream& is, vector<T>& vec) {
  for (T& val : vec) is >> val;
  return is;
}
template <class T>
istream& operator,(istream& is, T& val) {
  return is >> val;
}
template <class T, class S>
ostream& operator<<(ostream& os, const pair<T, S>& p) {
  return os << p.first << " " << p.second;
}
template <class T>
ostream& operator<<(ostream& os, const vector<T>& vec) {
  for (size_t i = 0; i < vec.size(); i++)
    os << vec[i] << (i == vec.size() - 1 ? "" : " ");
  return os;
}
template <class T>
ostream& operator,(ostream& os, const T& val) {
  return os << " " << val;
}
template <class H>
void print(const H& head) {
  cout << head;
}
template <class H, class... T>
void print(const H& head, const T&... tail) {
  cout << head << " ";
  print(tail...);
}
template <class... T>
void println(const T&... values) {
  print(values...);
  cout << endl;
}
template <class H>
void eprint(const H& head) {
  cerr << head;
}
template <class H, class... T>
void eprint(const H& head, const T&... tail) {
  cerr << head << " ";
  eprint(tail...);
}
template <class... T>
void eprintln(const T&... values) {
  eprint(values...);
  cerr << endl;
}
class range {
  Integer start_, end_, step_;

 public:
  struct range_iterator {
    Integer val, step_;
    range_iterator(Integer v, Integer step) : val(v), step_(step) {}
    Integer operator*() { return val; }
    void operator++() { val += step_; }
    bool operator!=(range_iterator& x) {
      return step_ > 0 ? val < x.val : val > x.val;
    }
  };
  range(Integer len) : start_(0), end_(len), step_(1) {}
  range(Integer start, Integer end) : start_(start), end_(end), step_(1) {}
  range(Integer start, Integer end, Integer step)
      : start_(start), end_(end), step_(step) {}
  range_iterator begin() { return range_iterator(start_, step_); }
  range_iterator end() { return range_iterator(end_, step_); }
};
inline string operator"" _s(const char* str, size_t size) {
  return move(string(str));
}
constexpr Integer my_pow(Integer x, Integer k, Integer z = 1) {
  return k == 0    ? z
         : k == 1  ? z * x
         : (k & 1) ? my_pow(x * x, k >> 1, z * x)
                   : my_pow(x * x, k >> 1, z);
}
constexpr Integer my_pow_mod(Integer x, Integer k, Integer M, Integer z = 1) {
  return k == 0    ? z % M
         : k == 1  ? z * x % M
         : (k & 1) ? my_pow_mod(x * x % M, k >> 1, M, z * x % M)
                   : my_pow_mod(x * x % M, k >> 1, M, z);
}
constexpr unsigned long long operator"" _ten(unsigned long long value) {
  return my_pow(10, value);
}
inline int k_bit(Integer x, int k) { return (x >> k) & 1; }
mt19937 mt(chrono::duration_cast<chrono::nanoseconds>(
               chrono::steady_clock::now().time_since_epoch())
               .count());
template <class T>
string join(const vector<T>& v, const string& sep) {
  stringstream ss;
  for (size_t i = 0; i < v.size(); i++) {
    if (i > 0) ss << sep;
    ss << v[i];
  }
  return ss.str();
}
inline string operator*(string s, int k) {
  string ret;
  while (k) {
    if (k & 1) ret += s;
    s += s;
    k >>= 1;
  }
  return ret;
}
}  // namespace
constexpr long long mod = 9_ten + 7;
template <class Value = int>
class SegmentTree {
  int n;
  vector<Value> V;
  Value DEFAULT_VALUE;
  static Value default_evaluate(Value a, Value b) { return max(a, b); }
  function<Value(Value, Value)> evaluate;
  Value RangeEvaluation(int a, int b, int at, int l, int r) {
    if (r <= a || b <= l) return DEFAULT_VALUE;
    if (a <= l && r <= b)
      return V[at];
    else {
      Value val_left = RangeEvaluation(a, b, at * 2 + 1, l, (l + r) / 2);
      Value val_right = RangeEvaluation(a, b, at * 2 + 2, (l + r) / 2, r);
      return evaluate(val_left, val_right);
    }
  }

 public:
  SegmentTree(int size, Value DEFAULT = 0,
              function<Value(Value, Value)> eval = default_evaluate) {
    DEFAULT_VALUE = DEFAULT;
    evaluate = eval;
    n = 1;
    while (n < size) n <<= 1;
    V = vector<Value>(2 * n - 1, DEFAULT_VALUE);
  }
  void update(int at, Value new_val) {
    at += n - 1;
    V[at] = new_val;
    while (at > 0) {
      at = (at - 1) / 2;
      V[at] = evaluate(V[at * 2 + 1], V[at * 2 + 2]);
    }
  }
  Value RangeEvaluation(int l, int r) {
    if (l >= r) return DEFAULT_VALUE;
    if (l >= n) return DEFAULT_VALUE;
    return RangeEvaluation(l, r, 0, 0, n);
  }
};
int main() {
  int n, c, d;
  cin >> n, c, d;
  vector<pair<int, int>> cc, dd;
  int mx_c = -1000000, mx_d = -1000000;
  for (auto i : range(n)) {
    int x, y;
    string s;
    cin >> x, y, s;
    if (s == "C") {
      if (y > c) continue;
      cc.push_back({x, y});
      mx_c = max<int>(mx_c, x);
    } else if (s == "D") {
      if (y > d) continue;
      dd.push_back({x, y});
      mx_d = max<int>(mx_d, x);
    } else {
      abort();
    }
  }
  int ans = 0;
  ans = max(ans, mx_c + mx_d);
  vector<vector<int>> vc(100010), vd(100010);
  for (int i = 0; i < cc.size(); i++) {
    vc[cc[i].second].push_back(cc[i].first);
  }
  for (int i = 0; i < dd.size(); i++) {
    vd[dd[i].second].push_back(dd[i].first);
  }
  SegmentTree<int> tc(100010), td(100010);
  for (int i = 0; i < vc.size(); i++) {
    if (vc[i].size() == 0) continue;
    sort(vc[i].rbegin(), vc[i].rend());
    tc.update(i, vc[i][0]);
  }
  for (int i = 0; i < vd.size(); i++) {
    if (vd[i].size() == 0) continue;
    sort(vd[i].rbegin(), vd[i].rend());
    td.update(i, vd[i][0]);
  }
  for (int t = 0; t < 2; t++) {
    for (int i = 1; i < c; i++) {
      int rc = min(i, c - i);
      if (rc <= 0) continue;
      if (vc[i].size() == 0) continue;
      if (rc > i) continue;
      if (rc == i) {
        int l_max = tc.RangeEvaluation(0, rc);
        if (l_max != 0) ans = max(ans, l_max + vc[i][0]);
        if (vc[i].size() >= 2) {
          ans = max(ans, vc[i][0] + vc[i][1]);
        }
      } else {
        int l_max = tc.RangeEvaluation(0, rc + 1);
        if (l_max != 0) ans = max(ans, l_max + vc[i][0]);
      }
    }
    swap(c, d);
    swap(vc, vd);
    swap(tc, td);
  }
  assert(ans >= 0);
  println(ans);
  return 0;
}

```