Kəndir çəkmə#10494

Kəndir çəkmə

1,5 saniyə

256 meqabayt

Orta

Kəndirdartma — çox populyar bir idman növüdür. Qaydalar sadədir: iki komanda kəndiri müxtəlif istiqamətlərə çəkir. Hər il kəndirdartma üzrə müsabiqə keçirilir və bu müsabiqəyə artıq bir çox iştirakçı qeydiyyatdan keçib. Ledi müsabiqənin əsas təşkilatçısıdır və buna görə də iştirakçıları iki komandaya bölməlidir.

Ümumilikdə $2 n$ iştirakçı qeydiyyatdan keçib, buna görə də hər komandada $n$ iştirakçı olmalıdır. Kəndirin sol tərəfində $n$ nöqtə, sağ tərəfində isə $n$ nöqtə var. Bu nöqtələr iştirakçıların duracağı yerləri xarakterizə edir.

İştirakçılar seçici çıxdılar, hər biri sol tərəfdə və sağ tərəfdə durmaq istədiyi bir yeri seçdi. Bundan əlavə, Ledi hər bir iştirakçının gücünü bilir. Ledi çox həyəcanlandı və iştirakçıları iki komandaya bölə bilmədi. Buna görə də sizdən kömək istəyir. İndi siz çətin bir suala cavab verməlisiniz: $k$ ədədini bilirsiniz, iştirakçıları elə bölmək mümkündürmü ki, hər biri seçdiyi yerlərdən birində dursun, heç bir iki iştirakçı eyni yerdə olmasın və birinci komandanın iştirakçılarının gücünün cəmi ilə ikinci komandanın iştirakçılarının gücünün cəmi arasındakı fərq $k$ -dan çox olmasın?

Giriş

Birinci sətir iki tam ədəd $n$ və $k$ ( $1 \leq n \leq 30000$ 1 \leq n \leq 30\,000, $1 \leq k \leq 20 n$ 1 \leq k \leq 20n) — hər komandadakı iştirakçıların sayı və komandaların güc cəmləri arasındakı maksimal fərqi göstərən ədəd.

Növbəti $2 n$ sətirin hər biri üç tam ədəd $l_{i}$ l_i, $r_{i}$ r_i və $s_{i}$ s_i ( $1 \leq l_{i}, r_{i} \leq n, 1 \leq s_{i} \leq 20$ 1 \leq l_i, r_i \leq n, 1 \leq s_i \leq 20) ehtiva edir ki, bu da $i$ -ci iştirakçının gücünün $s_{i}$ s_i olduğunu, iştirakçı sol komandaya düşərsə $l_{i}$ l_i mövqeyində, sağ komandaya düşərsə $r_{i}$ r_i mövqeyində durmaq istədiyini göstərir.

Çıxış

Yeganə sətirdə "YES" yazın, əgər şərtə uyğun komandalar formalaşdırmaq mümkündürsə, əks halda "NO" yazın.

Nümunələr

Nümunə 1

Nümunə 2

Qeyd

Birinci nümunədə $1, 3, 6$ və $7$ oyunçularını sol tərəfdə (komandanın gücü $1 + 8 + 2 + 1 = 12$ 1 + 8 + 2 + 1 = 12) və $2, 4, 5$ və $8$ iştirakçılarını sağ tərəfdə (komandanın gücü $2 + 2 + 5 + 2 = 11$ 2 + 2 + 5 + 2 = 11) götürmək olar. Güc fərqi $1$ -ə bərabərdir.

İkinci nümunədə hər iki $4$ gücündə olan oyunçu eyni komandada olmalıdır, buna görə də minimal güc fərqi $6$ olacaq.

Bal hesablama

( $18$ bal): $n \leq 10$ n \leq 10;
( $30$ bal): $n \leq 2000$ n \leq 2\,000;
( $23$ bal): $n \leq 30000$ n \leq 30\,000, $s_{i} = 1$ s_i = 1;
( $29$ bal): $n \leq 30000$ n \leq 30\,000.