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 <iostream>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;
typedef long long int lli;
bool comp(const vector<pair<lli, lli> > &a, const vector<pair<lli, lli> > &b){
    return a.size() < b.size();
}

int main(){
    int n;
    lli a,b;
    cin >> n >> a >> b;
    vector<vector<pair<lli, lli> > > wv(5);
    for(int i=0; i<n; i++){
        lli t,x,y;
        cin >> t >> x >> y;
        t--;
        wv[t].push_back(make_pair(x, y));
    }
    sort(wv.begin(), wv.end(), comp);
    for(int i=0; i<5; i++){
        wv[i].push_back(make_pair(0, 0));
    }

    vector<pair<lli, lli> > en1, en2;
    for(int i=0; i<(int)wv[0].size(); i++){
        for(int j=0; j<(int)wv[1].size(); j++){
            for(int k=0; k<(int)wv[2].size(); k++){
                lli w = wv[0][i].first +wv[1][j].first +wv[2][k].first;
                lli v = wv[0][i].second +wv[1][j].second +wv[2][k].second;
                en1.push_back(make_pair(w, v));
            }
        }
    }
    for(int i=0; i<(int)wv[3].size(); i++){
        for(int j=0; j<(int)wv[4].size(); j++){
            lli w = wv[3][i].first +wv[4][j].first;
            lli v = wv[3][i].second +wv[4][j].second;
            en2.push_back(make_pair(w, v));
        }
    }
    sort(en1.begin(), en1.end());
    sort(en2.begin(), en2.end());

    bool yes = false;
    multiset<lli> validrange;
    int end = en2.size()-1;
    int begin = end; //逆半開
    for(int i=0; i<(int)en1.size(); i++){
        while(begin >= 0 && en2[begin].first +en1[i].first >= a){
            validrange.insert(en2[begin].second);
            begin--;
        }
        while(end > begin && en2[end].first +en1[i].first > b){
            validrange.erase(validrange.find(en2[end].second));
            end--;
        }
        auto itr = validrange.lower_bound(a -en1[i].second);
        if(itr != validrange.end() && *itr +en1[i].second <= b){
            yes = true;
            break;
        }
    }

    if(yes){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }
    return 0;
}