Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

AL_31_06 - KickassTorrents

Zamknięcie serwisu KickassTorrents wywołało totalny chaos wśród amerykańskiej Polonii. Nasi emigranci są zrozpaczeni ponieważ stracili główne źródło dostępu do pirackich nagrań z występami Tadeusza Drozdy. Na szczęście wzdłuż Elston Avenue w Chicago w błyskawicznym tempie uruchomionych zostało n serwerów z kopią serwisu. Każdy z nich jest wyposażony w kartę WiFi o określonym zasięgu d wyrażonym w metrach, za pomocą której komunikuje się z innymi serwerami. Znana jest również odległość x każdego z komputerów od początku Elston Avenue. Ona również wyrażona jest w metrach. Dwa serwery, oznaczmy je jako i oraz j, mogą się ze sobą komunikować poprzez sieć bezprzewodową jeżeli di + dj > |xi - xj|. W przypadku gdy dwa komputery nie mogły komunikować się poprzez WiFi fani Taduesza połączyli je bezpośrednio światłowodem.

Niestety połączenia WiFi są bardzo zawodne, w związku z czym nasi bohaterowie zastanawiają się nad wyłączeniem części serwerów. W działaniu powinien pozostać pewien ich podzbiór, w którym każda para komputerów jest bezpośrednio połączona światłowodem. Fani Tadeusza chcą, aby znaleziony podzbiór był jak największy. Oczywiście dopuszczają oni również sytuację, gdy będzie się on składał z zaledwie jednego serwera.

Pomóż polskim emigrantom i oblicz z ilu komputerów składa się poszukiwany podzbiór oraz ile bezpośrednich połączeń światłowodowych zostało poprowadzonych pomiędzy należącymi do niego serwerami.

Wejście

W pierwszej linii wejścia znajduje się jedna liczba całkowita t ∈ [1;5] określająca liczbę zestawów danych. W kolejnych liniach znajdują się zestawy danych.

W pierwszej linii każdego zestawu danych znajduje się jedna liczba całkowita n ∈ [1;105] oznaczająca liczbę serwerów działających wzdłuż Elston Avenue. W kolejnych n liniach znajdują się po dwie liczby całkowite x ∈ [0;109] i d ∈ [1;109] określające odpowiednio odległość danego komputera od początku ulicy oraz zasięg jego karty WiFi wyrażone w metrach. Gwarantujemy, że odległości x nie powtarzają się w ramach zestawu danych.

Wyjście

Dla każdego zestawu danych należy w osobnej linii wypisać liczebność szukanego zbioru oraz liczbę bezpośrednich połączeń światłowodowych pomiędzy należącymi do niego serwerów.

Przykład

Wejście:

2
3
5 3
2 2
8 2
4
1 1
4 1
7 1
10 1

Wyjście:

2 1
4 6

Dodane przez:Maciej Boniecki
Data dodania:2017-01-06
Limit czasu wykonania programu:1s
Limit długości kodu źródłowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: ASM64 GOSU
Pochodzenie:ALGOLIGA

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.