Problem description

Wyobraź sobie ogromną metropolię nocą, której układ ulic tworzy idealną, nieskończoną szachownicę. W samym centrum tego miejskiego labiryntu, na głównym skrzyżowaniu o współrzędnych (0,0), stoi gmach sztabu Partii Czerwonych. Tej nocy na każdym dostępnym skrzyżowaniu w mieście czuwa jeden działacz partyjny i – co kluczowe – w chwili rozpoczęcia akcji wszyscy oni deklarują wierność właśnie Czerwonym.

Sytuacja w mieście jest jednak napięta, a dotarcie do centrum utrudniają liczne awarie i roboty drogowe. Niektóre skrzyżowania są całkowicie rozkopane; nie można na nich stać ani przez nie przechodzić, co zmusza pieszych do kluczenia i szukania alternatywnych tras. Prezes wezwał wszystkich do swojej siedziby, ale na ten apel odpowiedzą tylko ci, którzy są w stanie dotrzeć do celu, pokonując pieszo maksymalnie S przecznic najkrótszą możliwą drogą, przemieszczając się w każdym kroku jedynie na pole stykające się krawędzią. Osoby te dotrą na spotkanie, wybierając trasę, która jest najkrótszą możliwą drogą do siedziby. Reszta, zniechęcona dystansem, pozostanie na swoich posterunkach.

Największym problemem nie jest jednak logistyka, lecz chwiejna natura samych działaczy. Ruszając ze swojego skrzyżowania, każdy polityk jest Czerwony, ale wystarczy spacer jedną przecznicą, by pod wpływem chwili zmienił barwy na Niebieskie. Po przejściu kolejnego odcinka do następnego skrzyżowania, sentyment powraca i znów staje się Czerwony, by po następnym kroku ponownie przejść na stronę opozycji. Ta polityczna karuzela trwa przez całą drogę, a każdy kolejny odcinek ulicy oznacza zmianę poglądów na przeciwne. Twoim zadaniem jest obliczyć, ilu z tych wędrowców, po pokonaniu plątaniny ulic, ostatecznie zamelduje się u prezesa jako lojalni Czerwoni, a ilu wejdzie do środka jako farbowani Niebiescy.

Wejście

W pierwszym wierszu wejścia znajdują się dwie liczby naturalne N i S oznaczające kolejno liczbę zablokowanych skrzyżowań oraz maksymalną liczbę przecznic, którą politycy są w stanie pokonać. Następne N wierszy zawiera współrzędne remontowanych skrzyżowań. W i–tym z nich znajdują się dwie liczby całkowite X_i, Y_i reprezentujące współrzędne i–tego remonotwanego skrzyżowania.

Wyjście

Dwie liczby całkowite oddzielone spacją: liczba wędrowców, którzy dotrą jako lojalni Czerwoni i liczba wędrowców, którzy dotrą jako farbowani Niebiescy.

Ograniczenia

0 ≤ N ≤ 100 000, 1 ≤ S ≤ 10⁹, |X_i|, |Y_i| < 1 000, (X_i,Y_i) ≠ (X_j,Y_j) dla i ≠ j. Skrzyżowanie, znajdujące się przy głównym gmachu partii, nie jest zablokowane.

Przykład

0 2

9 4

4 5
-1 1
0 -1
0 1
1 0

10 16

4 50000
1 1
-1 -1
1 -1
-1 1

2500099997 2500000000

Ocenianie