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).