Drużyny [A]

Limit pamięci: 128 MB

Magister Bajtocki jest najbardziej lubianym nauczycielem wychowania fizycznego w Szkole Podstawowej nr 64 im. Komiwojażera Bajtazara w Bajtocji. Na każdych zajęciach, po przeprowadzeniu krótkiej rozgrzewki, pyta uczniów w jaką grę zespołową chcieliby grać, a następnie pomaga im podzielić się na drużyny.

Podczas zbiórki uczniowie ustawiają się w szereg, numerując się tym samym kolejnymi liczbami od do . Mgr Bajtocki tworzy drużyny tak, aby każda z nich stanowiła spójny fragment szeregu. Każdy z uczniów musi należeć do jednej z drużyn.

Nauczyciel dobrze zna swoich uczniów i wie, że uczeń o numerze będzie zadowolony z podziału tylko wtedy, gdy liczba zawodników w jego drużynie będzie nie mniejsza niż oraz nie większa niż .

Mgr Bajtocki zastanawia się, czy da się podzielić uczniów na drużyny tak, aby każdy z nich był zadowolony. Jeśli jest to możliwe, chciałby poznać maksymalną możliwą liczbę powstałych drużyn, a także liczbę podziałów realizujących to maksimum.

Wejście

W pierwszym wierszu wejścia znajduje się jedna liczba całkowita (), oznaczająca liczbę uczniów. Kolejne wierszy opisuje preferencje uczniów: -ty z tych wierszy zawiera dwie liczby całkowite (), oznaczające, że uczeń o numerze będzie zadowolony, gdy liczba zawodników w jego drużynie będzie należała do przedziału .

Wyjście

Jeśli da się podzielić uczniów według procedury mgra Bajtockiego tak, aby każdy z nich był zadowolony, na wyjście należy wypisać dwie liczby całkowite oddzielone pojedynczym odstępem - maksymalną liczbę drużyn i liczbę podziałów realizujących to maksimum. Drugą z tych liczb należy wypisać modulo .

Jeśli uczniów nie da się podzielić zgodnie z powyższymi wymogami, na wyjście należy wypisać słowo NIE.

Przykład

Dla danych wejściowych:

9
1 4
2 5
3 4
1 5
1 1
2 5
3 5
1 3
1 1

poprawną odpowiedzią jest:

5 2

natomiast dla danych wejściowych:

2
1 1
2 2

poprawnym wynikiem jest:

NIE

Autor zadania: Adam Karczmarz.