POLSKI SPOJ

Bajtockie Ministerstwo Oświaty postanowiło zreformować krajowy system szkolnictwa, aby podnieść poziom wykształcenia obywateli. Wprowadzono system, w którym poziom wykształcenia wyrażony jest w punktach. Każdy sześciolatek rozpoczyna naukę w jednej ze szkół przeznaczonych dla najmłodszych, mając na koncie 0 BPW (Bajtockich Punktów Wykształcenia). Po jej ukończeniu może kontynuować zdobywanie wiedzy w wybranych przez siebie szkołach. Nauka w każdej szkole trwa określoną dla niej liczbę lat, nie można jej przerwać, a jej ukończenie zwiększa stan konta o określoną dla tej szkoły liczbę BPW. Każdą szkołę można wybrać wiele razy.

Zdobywanie wiedzy można zakończyć na dowolnym poziomie, natomiast dla najzdolniejszych i najambitniejszych młodych obywateli przewidziano wyróżnienie – przyznanie tytułu Bajtora Nauki. Tytuł ten otrzymuje się za zdobycie określonej (lub większej) liczby  p_bn BPW.

Ministerstwo opublikuje wkrótce informacje o każdej z n szkół w Bajtocji na swojej stronie internetowej w precyzyjnie określonym formacie: "KOD_i t_i p_i min_i max_i". I tak na przykład zapis "BAT 208 30 150 159" oznacza, że kształcenie uczniów w Bajtockiej Akademii Technicznej trwa 208 tygodni, jej ukończenie daje 30 BPW, a rozpocząć w niej naukę mogą osoby, które na koncie mają co najmniej 150 BPW i co najwyżej 159 BPW. 

Bajtek jest bardzo zdolnym i ambitnym sześciolatkiem (możemy założyć, że ukończy w normalnym czasie – bez powtarzania klasy – każdą szkołę). Ma zamiar zdobyć tytuł Bajtora Nauki w jak najkrótszym czasie i chciałby wiedzieć ile tygodni na to potrzebuje. Pomóż mu rozwiązać ten problem.

Wejście

Standardowe wejście zawiera uproszczony (bez kodów szkół) opis zreformowanego systemu szkolnictwa w Bajtocji. W pierwszym wierszu zapisane są dwie liczby całkowite n (1 ≤  n ≤ 2*10⁵) i p_bn (1 ≤  p_bn ≤ 4096) oznaczające odpowiednio: liczbę szkół w Bajtocji i liczbę punktów BPW wymaganych do uzyskania tytułu Bajtora Nauki. W kolejnych n wierszach podane są informacje o każdej z n szkół. W i+1 wierszu znajdują się dane dotyczące i-tej szkoły w formacie "t_i p_i min_i max_i" gdzie:

• t_i to liczba tygodni nauki w tej szkole (1 ≤  t_i  ≤ 520),
• p_i to liczba BPW uzyskiwana po ukończeniu nauki w tej szkole (1 ≤ p_i  ≤ 4096),
• min_i to minimalna liczba BPW, którą musi posiadać kandydat na ucznia szkoły (0 ≤  min_i  ≤ 4096),
• max_i to maksymalna liczba BPW, którą może posiadać kandydat na ucznia szkoły (0 ≤  max_i  ≤ 4096),

Wyjście

Jedna liczba całkowita oznaczającą minimalną liczbę tygodni jakie trzeba przeznaczyć na naukę, aby zebrać wystarczającą do uzyskania tytułu Bajtora Nauki liczbę BPW. 

Jeśli uzyskanie tytułu Bajtora Nauki w nowym systemie oświaty jest niemożliwe, to program powinien wypisać jeden wiersz ze słowem NIE.

Przykład 1

Wejście:
3 13
2 4 0 4
2 10 0 0
1 10 5 9

Wyjście:
5

Przykład 2

Wejście:
2 11
3 10 0 5
3 15 15 20

Wyjście:
NIE