题目描述

拔河（Tug of War）在 Byteland 是十分受欢迎的运动。规则十分简单：两队以相反方向拉绳子。一年一度的 Byteland 拔河比赛将要进行，并且许多选手都报名参加了。作为公平竞赛专员，你的工作是把选手们划分为两个队伍，使得这个比赛能够进行很长时间。

由于一共 $2n$ 名选手报名参赛，所以一个队有 $n$ 名队员。一根绳上左右两边各有 $n$ 个点。Byteland 的拔河精英们都很挑剔，每个参赛选手在左右两边都有一个他们想要站的位置。此外，你知道每一个参赛选手的力量值。

组织者现在问你如下的问题：给定一个整数 $k$，能否分出两个队，这两个队各有 $n$ 名选手，并且他们站在他们想站的位置（当然不能有两名或以上选手站在同一位置），双方力量和之差不超过 $k$？

输入格式

输入的第一行有两个正整数 $n,k$，分别表示绳子每一侧的位置数和两队的最大力量差。为了简单，我们把参赛者编号为 $1$ 到 $2n$。

接下来 $2n$ 行，每行描述一个参赛者，这些行中的第 $i$ 行包含三个正整数 $l_i,r_i,s_i$，分别表示 $i$ 号选手有力量 $s_i$，并且想站在左边的 $l_i$ 位置或是右边的 $r_i$ 位置。

输出格式

你的程序应在第一行输出一个单词 YES 或 NO，表示是否有可能建立两支符合上述条件的队伍。

4 1
1 1 1
2 1 2
2 2 8
1 2 2
3 3 5
3 3 2
4 4 1
4 4 2

YES

2 5
1 1 1
1 2 4
2 2 1
2 1 4

NO

提示

样例解释 1

第一个样例中我们可以安排 $1,3,6,7$ 号选手站在左边（这个队伍力量值为 $1+8+2+1=12$），并安排 $2,4,5,8$ 号选手站在右边（这个队伍力量值为 $2+2+5+2=11$）。力量值的差为 $1$。

样例解释 2

第二个样例中两位力量值为 $4$ 的选手不得不在一个队中，因此两队最小的力量值之差为 $6$。

子任务

以下子任务与评测无关，仅供参考。

本题采用子任务式测评，只有一个子任务内所有测试点均正确才可获得此子任务的分数。

对于全部子任务，$k\le 20n,1\le l_i,r_i\le n,1\le s_i\le 20$。

对于每个子任务满足的条件如下：

注：实际上，拔河并不取决于力量而取决于双方体重。原题的选手力量值应正比于选手体重值。

附注

本题翻译搬运自 LibreOJ，译者为 HeRaNO，在此对原翻译者表示感谢。