Перетягування канату

Перетягування канату — дуже популярний спорт. Правила прості: дві команди тягнуть канат в різні сторони. Щорічно проходить конкурс по перетягуванню канату, на який вже записалось багато учасників. Леді є головним організатором конкурсу, і тому їй потрібно розділити учасників на дві команди.

Всього зареєструвалось $2n$ учасників, тому в кожній команді має бути по $n$ учасників. У канату є $n$ точок з лівої сторони, та $n$ точок з правої. Ці точки характеризують місця, де будуть стояти учасники.

Учасники виявились вибагливими, кожен вибрав рівно одне місце ліворуч та рівно одне місце праворуч, на яких цей учасник хоче стояти. Окрім того, Леді знає силу кожного учасника. Леді перенервувала, і не змогла розподілити учасників на дві команди. Тому вона просить у Вас допомоги. Тепер Ви маєте відповісти на складне питання: Ви знаєте число $k$, чи можливо розподілити учасників на дві команди так, щоб кожен стояв на одному з вибраних місць, у жодних двох учасників не було одного місця на двох, а різниця між сумою сил учасників першої команди та суми сил учасників другої команди не перевищувала $k$?

Вхідні дані

Перший рядок містить два цілі числа $n$ та $k$ ($1\le n\le 30000$, $1\le k\le 20n$) — кількість учасників у кожній команді, та число, яке позначає максимальну різницю, що може бути між сумою сил команд.

Кожен з наступних $2n$ рядків містить по три цілі числа $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$.

Оцінювання

1. ($18$ балів): $n\le 10$;

2. ($30$ балів): $n\le 2000$;

3. ($23$ бали): $n\le 30000$, $s_i=1$;

4. ($29$ балів): $n\le 30000$.