#2707. 「BalticOI 2015」拔河

内存限制:256 MiB 时间限制:2000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: HeRaNO

题目描述

题目译自 BalticOI 2015 Day2 Tug of War(TUG),原题面见附加文件。
如欲转载翻译,请注明翻译者信息及转载出处。

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

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

组织者现在问你如下的问题:给定一个整数 kkk,能否分出两个队,这两个队各有 nnn 名选手,并且他们站在他们想站的位置(当然不能有两名或以上选手站在同一位置),双方力量和之差不超过 kkk

输入格式

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

接下来 2n2n2n 行,每行描述一个参赛者,这些行中的第 iii 行包含三个正整数 li,ri,sil_i,r_i,s_ili,ri,si,分别表示 iii 号选手有力量 sis_isi,并且想站在左边的 lil_ili 位置或是右边的 rir_iri 位置。

输出格式

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

样例

样例输入 1

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

样例输出 1

YES

样例说明 1

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

样例输入 2

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

样例输出 2

NO

样例说明 2

第二个样例中两位力量值为 444 的选手不得不在一个队中,因此两队最小的力量值之差为 666

数据范围与提示

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

对于全部子任务,k≤20n,1≤li,ri≤n,1≤si≤20k\le 20n,1\le l_i,r_i\le n,1\le s_i\le 20k20n,1li,rin,1si20

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

子任务 条件 分数
111 n≤10n\le 10n10 181818
222 n≤2×103n\le 2\times 10^3n2×103 303030
333 n≤3×104,si=1n\le 3\times 10^4,s_i=1n3×104,si=1 232323
444 n≤3×104n\le 3\times 10^4n3×104 292929

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