줄다리기

바이트랜드에서 줄다리기는 인기가 아주 많은 종목이다. 규칙은 간단하다. 두 팀이 하나의 밧줄을 서로 반대 방향으로 당긴다. 해마다 열리는 바이트랜드 자선 줄다리기 대회가 곧 시작되고, 많은 사람이 참가 신청을 했다. 공정 경기 위원인 당신이 할 일은 경기가 오래 이어지도록 참가자를 두 팀으로 나누는 것이다.

신청한 참가자는 모두 $2n$명이므로 각 팀은 $n$명으로 이루어진다. 밧줄에는 왼쪽에 자리가 $n$개, 오른쪽에 자리가 $n$개 있다. 바이트랜드의 줄다리기 고수는 까다로워서, 참가자마다 서고 싶은 자리가 왼쪽에 하나, 오른쪽에 하나로 정해져 있다. 각 참가자의 힘도 이미 알고 있다.

주최 측이 정수 $k$를 하나 정해 놓고 묻는다. 두 팀이 각각 $n$명이고, 모든 참가자가 자신이 원하는 두 자리 중 한 곳에 서며(한 자리에 두 명이 설 수는 없다), 두 팀의 힘의 합의 차이가 $k$ 이하가 되도록 팀을 나눌 수 있는가?

첫째 줄에 밧줄 한쪽의 자리 수를 나타내는 양의 정수 $n$과 두 팀의 힘의 차이로 허용되는 최댓값을 나타내는 정수 $k$가 주어진다($1 \le n \le 1000$, $0 \le k \le 20n$). 참가자에게는 1번부터 $2n$번까지 번호를 매긴다.

다음 $2n$개의 줄에는 참가자의 정보가 한 명씩 주어진다. 그중 $i$번째 줄에는 세 양의 정수 $l_i$, $r_i$, $s_i$가 주어진다($1 \le l_i, r_i \le n$, $1 \le s_i \le 20$). $i$번 참가자의 힘은 $s_i$이고, 이 참가자는 밧줄 왼쪽의 $l_i$번 자리와 오른쪽의 $r_i$번 자리 중 한 곳에만 설 수 있다.

첫째 줄에 위 조건을 모두 만족하는 두 팀을 만들 수 있으면 YES를, 만들 수 없으면 NO를 출력한다.

첫 번째 예제에서는 1, 3, 6, 7번 참가자를 왼쪽에 세우고(힘의 합 $1 + 8 + 2 + 1 = 12$) 2, 4, 5, 8번 참가자를 오른쪽에 세우면 된다(힘의 합 $2 + 2 + 5 + 2 = 11$). 두 팀의 힘의 차이는 1이다.

두 번째 예제에서는 힘이 4인 두 참가자가 반드시 같은 팀에 들어가므로, 두 팀의 힘의 차이는 아무리 줄여도 6이다.