Sparing w Programowaniu Zespołowym Politechnika Poznańska, 13.03.2004

Opis

Granica między Bajtocją a Bajtolandią ma kształt linii prostej. W celu zwiększenia bezpieczeństwa swojego kraju, król Bajtolandii rozkazał umieścić wzdłuż granicy N jednostek wojskowych. Położenia tych jednostek dla uproszczenia utożsamiamy z punktami na prostej, posiadającymi całkowitoliczbową współrzędną.

W związku z zaistniałą sytuacją, król Bajtocji - podejrzliwie nastawiony w stosunku do króla Bajtolandii - postanowił - również w celu zwiększenia bezpieczeństwa swojego kraju - umieścić przy granicy wieżę obserwacyjną. Jako że w tej chwili król ma ograniczone fundusze, może sobie pozwolić tylko na wybudowanie jednej wieży o zasięgu widoczności e - jeżeli wybudowałby ją w punkcie o współrzędnej k, to obszar poddany obserwacji odpowiadałby przedziałowi na prostej [k-e,k+e] (czyli obustronnie domkniętemu przedziałowi od k-e do k+e). Jesteś nadwornym programistą Bajtocji - pomóż królowi i powiedz, gdzie należy wybudować wieżę tak, żeby jak najwięcej bajtolandzkich jednostek zostało poddanych obserwacji. Jeżeli istnieje więcej niż jedno położenie spełniające wymagania króla, należy - na bezdyskusyjny rozkaz króla - podać położenie o możliwie najmniejszej współrzędnej. Możliwa jest sytuacja, żeby więcej niż jedna jednostka stacjonowała w tym samym punkcie granicy.

Zadanie

Napisz program, który mając dane położenia jednostek wojskowych Bajtolandii poda najlepsze możliwe położenie wieży obserwacyjnej dla króla Bajtocji i obliczy, ile jednostek zostanie przez nią poddanych obserwacji.

Specyfikacja wejścia

W pierwszym wierszu wejścia podana jest dodatnia liczba całkowita D (1 ≤ D ≤ 30), oznaczająca liczbę zestawów testowych, które dalej pojawią się na wejściu. W pierwszym wierszu każdego zestawu danych znajdują się dwie liczby całkowite N i e (1 ≤ N ≤ 50.000, 0 ≤ e ≤ 700.000.000), oddzielone pojedynczym odstępem i oznaczające odpowiednio liczbę jednostek wojskowych Bajtolandii oraz zasięg widoczności wieży, którą król Bajtocji chce wybudować. W kolejnych N wierszach znajdują się opisy jednostek w postaci pojedynczych liczb całkowitych (z obustronnie domkniętego przedziału od -700.000.000 do 700.000.000), będące ich współrzędnymi na prostej obrazującej granicę między państwami.

Specyfikacja wyjścia

Dla każdego zestawu należy w osobnej linii wyjścia wypisać dwie liczby całkowite oddzielone pojedynczym odstępem i oznaczające odpowiednio najlepsze położenie wieży obserwacyjnej (zgodne z wymaganiami króla) oraz liczbę jednostek wojskowych, które mogą być obserwowane z wieży.

Przykład

2
4 1
1
2
3
4
3 3
-2
3
6

2 3
0 2