[BalticOI 2015] Tug of War

拔河（*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$。 对于每个子任务满足的条件如下： | 子任务 | 条件 | 分数 | | :----: | :-----------------------: | :--: | | $1$ | $n\le 10$ | $18$ | | $2$ | $n\le 2\times 10^3$ | $30$ | | $3$ | $n\le 3\times 10^4,s_i=1$ | $23$ | | $4$ | $n\le 3\times 10^4$ | $29$ | ~~注：实际上，拔河并不取决于力量而取决于双方体重。原题的选手力量值应正比于选手体重值。~~ ### 附注 本题翻译搬运自 [LibreOJ](https://loj.ac/problem/2707)，译者为 HeRaNO，在此对原翻译者表示感谢。