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>

using ll = long long;

struct Node {
    int loc;
    int l, r;
    Node() { loc = l = r = -1; }
    Node(int loc, int l, int r) : loc{loc}, l{l}, r{r} {} 
};

struct Point {
    ll x, y;
    Point() {}
    Point(ll x, ll y) : x{x}, y{y} {}

    bool operator < (const Point &p) const {
        return x != p.x ? x < p.x : y < p.y;
    }
};

struct KDTree2D {
    std::vector<Point> p;
    std::vector<Node> T;
    int np = 0;
    
    void init() { T.resize(p.size()); }
    
    int make(int l, int r, int depth)
    {
        if (l >= r) return -1;
        
        int mid = (l + r) / 2;
        int curr = np++;
        
        if (depth % 2 == 0) {
            std::sort(p.begin() + l, p.begin() + r,
                      [](const Point& a, const Point& b) {
                          return a.x < b.x;
                      });
        } else {
            std::sort(p.begin() + l, p.begin() + r,
                      [](const Point& a, const Point& b) {
                          return a.y < b.y;
                      });
        }
        T[curr] = {mid, make(l, mid, depth + 1), make(mid + 1, r, depth + 1)};        
        return curr;
    }

    void add(Point v)
    {
        p.emplace_back(v.x, v.y);
    }    

    bool find(int k, ll sx, ll sy, ll tx, ll ty, int depth)
    {
        ll x = p[T[k].loc].x;
        ll y = p[T[k].loc].y;
        
        if (sx <= x && x <= tx && sy <= y && y <= ty) {
            return 1;
        }
        
        ll res = 0;
        if (depth % 2 == 0) {
            if (T[k].l != -1 && sx <= x) {
                res |= find(T[k].l, sx, sy, tx, ty, depth + 1);
            }

            if (T[k].r != -1 && x <= tx) {
                res |= find(T[k].r, sx, sy, tx, ty, depth + 1);
            }
        } else {
            if (T[k].l != -1 && sy <= y) {
                res |= find(T[k].l, sx, sy, tx, ty, depth + 1);
            }

            if (T[k].r != -1 && y <= ty) {
                res |= find(T[k].r, sx, sy, tx, ty, depth + 1);
            }
        }        
        return res;
    }
};

Point sum(const Point &a, const Point &b)
{
    return Point{a.x + b.x, a.y + b.y};
}

bool find(KDTree2D &kd, int root, ll l, ll r, ll dx = 0, ll dy = 0)
{
    ll sx = l - dx, tx = r - dx;
    ll sy = l - dy, ty = r - dy;
    return kd.find(root, sx, sy, tx, ty, 0);
}

int main()
{
    ll N, A, B;
    std::cin >> N >> A >> B;
    std::vector<std::vector<Point>> p{5};
    for (int i = 0; i < N; i++) {
        ll t, x, y;
        std::cin >> t >> x >> y;
        p[t - 1].emplace_back(x, y);        
    }
    
    for (int i = 0; i < 5; i++) {
        p[i].emplace_back(0, 0);
    }    
    
    sort(p.begin(), p.end(),
         [](const std::vector<Point> &a, const std::vector<Point> &b) {
             return a.size() > b.size();
         });
    
    KDTree2D kd;
    for (Point& v0 : p[0]) {
        for (Point& v1 : p[1]) {            
            kd.add(sum(v0, v1));           
        }
    }
    
    kd.init();
    int root = kd.make(0, kd.p.size(), 0);
    bool res = 0;    
    for (Point& v2 : p[2]) {
        for (Point& v3 : p[3]) {
            for (Point& v4 : p[4]) {
                Point s = sum(sum(v2, v3), v4);
                res |= find(kd, root, A, B, s.x, s.y); 
            }            
        }    
    }    
    std::cout << (res ? "Yes" : "No") << std::endl;
    return 0;
}