Monopolista

Limit pamięci: 32 MB

Nadszedł długo oczekiwany dzień: do bram Bajtocji w końcu zapukał Internet. Pierwszym etapem modernizacji będzie okablowanie stolicy. Zadania tego bardzo chętnie podejmie się Pewna Znana Firma Telekomunikacyjna, jednak nie jest to takie proste z powodu obowiązujących w Bajtocji przepisów oraz ograniczeń infrastrukturalnych.

W stolicy znajduje się wieżowców, każdy z nich na skrzyżowaniu jednej z ulic i jednej z alej. Ulice biegną z północy na południe, a aleje ze wschodu na zachód. Odległość pomiędzy sąsiednimi alejami oraz sąsiednimi ulicami wynosi jeden bajtometr. Ulice są ponumerowane liczbami całkowitymi, ich numery rosną w kierunku wschodnim. Analogiczną numerację stosujemy dla alej, przy czym numery rosną w kierunku północnym.

Kable łączące budynki można kłaść tylko pod ulicami i alejami. Aby połączyć budynek znajdujący się w punkcie () (tj. na skrzyżowaniu ulicy numer z aleją numer ) z budynkiem w punkcie () trzeba zużyć bajtometrów kabla. Co więcej długość pojedynczego kabla nie może przekraczać bajtometrów i nie można ich łączyć poza budynkami.

Aby nie dopuścić do monopolu, każdy z dostawców może zainstalować na dachu dokładnie jednego z budynków antenę odbiorczo-nadawczą. Będzie ona dostarczać Internet do tych wieżowców, które są bezpośrednio lub pośrednio połączone kablami z budynkiem z anteną.

Prezes PZFT zastanawia się jaka jest maksymalna liczba odbiorców, do których może dostarczyć Internet, oraz co najmniej ilu innych dostawców będzie działać w bajtockiej stolicy, jeśli Internet ma być dostarczony do każdego wieżowca.

Wejście

W pierwszym wierszu standardowego wejścia znajdują się dwie liczby całkowite i (, ) oznaczające odpowiednio liczbę wieżowców oraz maksymalną długość kabla. Wieżowce dla uproszczenia numerujemy kolejnymi liczbami całkowitymi, począwszy od . W kolejnych wierszach znajdują się pozycje wieżowców. Każdy z tych wierszy zawiera dwie liczby całkowite i (), które oznaczają, że -ty wieżowiec znajduje się w punkcie o tych współrzędnych.

Wyjście

Na standardowe wyjście należy wypisać dwie liczby oznaczające odpowiednio minimalną liczbę innych dostawców Internetu, z którymi będzie musiała konkurować PZFT, oraz maksymalną liczbę odbiorców, do których będzie mogła dostarczać Internet.

Przykład

Dla danych wejściowych:

4 2
1 1
3 3
2 2
10 10

poprawną odpowiedzią jest:

1 3

Autor zadania: Richard Ho (zapożyczenie z USACO: Bartosz Górski).