e-olymp
favorite We need a little bit of your help to keep things running, click on this banner to learn more
Competitions

Ukrainian Selection Camp to the European Girls' Olympiad in Informatics 2021

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

Перетягування канату~--- дуже популярний спорт. Правила прості: дві команди тягнуть канат в різні сторони. Щорічно проходить конкурс по перетягуванню канату, на який вже записалось багато учасників. Леді є головним організатором конкурсу, і тому їй потрібно розділити учасників на дві команди. Всього зареєструвалось $2n$ учасників, тому в кожній команді має бути по $n$ учасників. У канату є $n$ точок з лівої сторони, та $n$ точок з правої. Ці точки характеризують місця, де будуть стояти учасники. Учасники виявились вибагливими, кожен вибрав рівно одне місце ліворуч та рівно одне місце праворуч, на яких цей учасник хоче стояти. Окрім того, Леді знає силу кожного учасника. Леді перенервувала, і не змогла розподілити учасників на дві команди. Тому вона просить у Вас допомоги. Тепер Ви маєте відповісти на складне питання: Ви знаєте число $k$, чи можливо розподілити учасників на дві команди так, щоб кожен стояв на одному з вибраних місць, у жодних двох учасників не було одного місця на двох, а різниця між сумою сил учасників першої команди та суми сил учасників другої команди не перевищувала $k$? \InputFile Перший рядок містить два цілі числа $n$ та $k$ ($1 \leq n \leq 30\,000$, $1 \leq k \leq 20n$)~--- кількість учасників у кожній команді, та число, яке позначає максимальну різницю, що може бути між сумою сил команд. Кожен з наступних $2n$ рядків містить по три цілі числа $l_i$, $r_i$ та $s_i$ ($1 \leq l_i, r_i \leq n, 1 \leq s_i \leq 20$), що означає, що у $i$-го учасника сила рівна $s_i$, якщо учасник потрапить в ліву команду, то бажає стояти на позиції $l_i$, а якщо в праву, то в позиції $r_i$ відповідно. \OutputFile В єдиному рядку виведіть <<\t{YES}>>, якщо можна сформувати команди відповідно до умови, інакше виведіть <<\t{NO}>>. \Note В першому прикладі можна взяти $1, 3, 6$ та $7$ гравців ліворуч (сила команди рівна $1 + 8 + 2 + 1 = 12$), а учасників $2, 4, 5$ та $8$ праворуч (сила команди буде $2 + 2 + 5 + 2 = 11$). Різниця в силах дорівнює $1$. В другому прикладі обоє гравців з силами $4$ мають бути в одній команді, тому мінімальна різниця сил буде $6$. \Scoring \begin{enumerate} \item ($18$ балів): $n \leq 10$; \item ($30$ балів): $n \leq 2\,000$; \item ($23$ бали): $n \leq 30\,000$, $s_i = 1$; \item ($29$ балів): $n \leq 30\,000$. \end{enumerate}
Time limit 1.5 second
Memory limit 256 MiB
Input example #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
Output example #1
YES
Input example #2
2 5
1 1 1
1 2 4
2 2 1
2 1 4
Output example #2
NO
Author Sofia Melnyk