You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

拔河（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，在此对原翻译者表示感谢。