eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

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

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

Лимит времени 1.5 секунда
Лимит использования памяти 256 MiB

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

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

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

Входные данные

Перший рядок містить два цілі числа 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 відповідно.

Выходные данные

В єдиному рядку виведіть «YES», якщо можна сформувати команди відповідно до умови, інакше виведіть «NO».

Пример

Входные данные #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
Входные данные #2
2 5
1 1 1
1 2 4
2 2 1
2 1 4
Выходные данные #2
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 \leq 10;

  2. (30 балів): n \leq 2\,000;

  3. (23 бали): n \leq 30\,000, s_i = 1;

  4. (29 балів): n \leq 30\,000.

Автор Sofia Melnyk