Problem: Problem

Gaccho is enthusiastic about the popular game Zombie Hunter. In this game, there are 5 types of armor dedicated to the head, torso, arms, hips, and legs, and the player character (PC) operated by Gaccho can have up to 1 armor for each part of the body. Can be equipped.
In addition, the weight and defense power are set for each armor, and when the total weight of the armor equipped on the PC is A or more and B or less, and the total defense power is also A or more and B or less. The PC can activate the skill.

Gaccho has N pieces of armor. Find out if your PC can activate your skills by choosing the right armor to equip.

Constraints

The input satisfies the following conditions.

* 1 ≤ N ≤ 500
* 1 ≤ A ≤ B ≤ 1012
* 1 ≤ ti ≤ 5
* −1012 ≤ xi, yi ≤ 1012

Input

The input is given in the following format.


N A B
t1 x1 y1
t2 x2 y2
...
tN xN yN


All inputs are given as integers.
The first line gives you the number of armor N you own and the two integers A and B used to activate the skill.
Information on N pieces of armor is given to the N lines that continue from the second line. ti, xi, yi represent the type, weight, and defense of the i-th armor, respectively.

Armor type The ti value indicates that 1 is head armor, 2 is torso armor, 3 is arm armor, 4 is waist armor, and 5 is foot armor.

Output

Output "Yes" if the skill can be activated, and "No" if it cannot be activated on one line.

Examples

Input

7 10 11
1 1 0
1 0 1
2 2 2
3 3 5
4 1 3
5 1 3
5 5 -1


Output

Yes


Input

7 10 10
1 1 0
1 0 1
2 2 2
3 3 5
4 1 3
5 1 3
5 5 -1


Output

No

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;

using VI = vector<int>;
using VVI = vector<VI>;
using PII = pair<int, int>;
using LL = long long;
using VL = vector<LL>;
using VVL = vector<VL>;
using PLL = pair<LL, LL>;
using VS = vector<string>;

#define ALL(a)  begin((a)),end((a))
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define SZ(a) int((a).size())
#define SORT(c) sort(ALL((c)))
#define RSORT(c) sort(RALL((c)))

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)

#define FF first
#define SS second
template<class S, class T>
istream& operator>>(istream& is, pair<S,T>& p){
  return is >> p.FF >> p.SS;
}
template<class S, class T>
ostream& operator<<(ostream& os, const pair<S,T>& p){
  return os << p.FF << " " << p.SS;
}
template<class T>
void maxi(T& x, T y){
  if(x < y) x = y;
}
template<class T>
void mini(T& x, T y){
  if(x > y) x = y;
}


const double EPS = 1e-10;
const double PI  = acos(-1.0);
const LL MOD = 1e9+7;
const LL INF = 1e18;

class SegT{
private:
  VL dat[2 * (1 << 17) - 1]; // = 131072
  int NN;

  void merge(VL& dst, const VL& s1, const VL& s2){
	for(int i1=0,i2=0;i1<SZ(s1)||i2<SZ(s2);){
	  if(i1 == SZ(s1)){
		dst.push_back(s2[i2++]);
	  }
	  else if(i2 == SZ(s2)){
		dst.push_back(s1[i1++]);
	  }
	  else{
		if(s1[i1] < s2[i2])
		  dst.push_back(s1[i1++]);
		else
		  dst.push_back(s2[i2++]);
	  }
	}
  }
  
public:
  SegT(int n_, VVL& xs){
	NN = 1;
	while(NN < n_) NN <<= 1;
	for(int i=0;i<n_;++i){
	  dat[NN-1+i] = xs[i];
	  SORT(dat[NN-1+i]);
	}
	for(int i=NN-2;i>=0;--i){
	  merge(dat[i], dat[i*2+1], dat[i*2+2]);
	}
  }

  bool query(int a, int b, LL lb, LL ub, int k, int l, int r){
	if(r <= a || b <= l) return false;

	if(a <= l && r <= b){
	  auto it = lower_bound(ALL(dat[k]), lb);
	  return it != end(dat[k]) && *it <= ub;
	}
	else{
	  if(query(a, b, lb, ub, k*2+1, l, (l+r)/2))
		return true;
	  return query(a, b, lb, ub, k*2+2, (l+r)/2, r);
	}
  }
  int query(int a, int b, LL lb, LL ub){
	return query(a, b, lb, ub, 0, 0, NN);
  }
};


LL N, A, B;
vector<PLL> xs[5];

int main(){
  cin.tie(0);
  ios_base::sync_with_stdio(false);

  cin >> N >> A >> B;
  REP(i,N){
	LL t, a, b;
	cin >> t >> a >> b;
	xs[t-1].EB(a,b);
  }
  
  set<PLL> S, T, tmp;
  S.insert(MP(0,0));
  REP(i,3){
	tmp = S;
	for(auto&& p: S)
	  for(auto&& x: xs[i]){
		tmp.insert(MP(x.FF+p.FF, x.SS+p.SS));
	  }
	S = tmp;
  }
  T.insert(MP(0,0));
  FOR(i,3,5){
	tmp = T;
	for(auto&& p: T)
	  for(auto&& x: xs[i]){
		tmp.insert(MP(x.FF+p.FF, x.SS+p.SS));
	  }
	T = tmp;
  }
  tmp.clear();

  vector<LL> xx;
  for(auto&& p: T)
	xx.PB(p.FF);
  xx.PB(-INF);
  xx.PB(INF);
  SORT(xx);
  xx.erase(unique(ALL(xx)), end(xx));

  int M = SZ(xx);
  map<LL,int> idx;
  REP(i,M) idx[xx[i]] = i;
  
  VVL dat(M);
  for(auto&& p: T)
	dat[idx[p.FF]].PB(p.SS);

  SegT seg(M, dat);
  for(auto&& p: S){
	int lx = idx.lower_bound(A-p.FF)->SS;
	int rx = idx.upper_bound(B-p.FF)->SS;
	if(seg.query(lx, rx, A-p.SS, B-p.SS)){
	  cout << "Yes" << endl;
	  return 0;
	}
  }
  cout << "No" << endl;

  return 0;
}