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

XIWTPZG - Podróże pana Jana - wycieczka na wschód

Opis

Podczas swoich ostatnich wojaży pan Jan usłyszał legendy, że na wschodzie istniała kiedyś wspaniała cywilizacja. W związku z tym, jako cel swojej następnej podróży obrał właśnie wschód. Postanowił zaplanować tak swoją podróż, aby odwiedzić jak najwięcej miast. Pan Jan ma jednak wrodzoną awersję do kierunku zachodniego, dlatego nie chce nigdy przemieszczać się w tym kierunku (zakładamy, że zachód jest w kierunku malejących x-ów). Każdego dnia pan Jan przemieszcza się z jednego miasta do drugiego. W ciągu jednego dnia nie może jednak przebyć więcej niż k kilometrów. Zaplanuj tak podróż pana Jana, aby odwiedził jak najwięcej miast pamiętając o tym, by nocleg nigdy nie odbył się dwa razy w tym samym mieście (wtedy wycieczka stałaby się nudna). Przez pojedyncze miasto może przejechać dowolną liczbę razy (ale zatrzymać się w nim na nocleg może tylko raz). Wycieczka może skończyć się w dowolnym mieście.

Specyfikacja wejścia

W pierwszej linii pliku wejściowego znajduje się liczba naturalna d (1 ≤ d ≤ 100), określająca liczbę zestawów danych.

W pierszwej linii każdego zestawu danych będą podane 2 liczby: N (1 ≤ N ≤ 1000) określająca liczbę miast oraz k (1 ≤ k ≤ 107). W kolejnych N liniach podane są współrzędne i-tego miasta: xi, yi (0 ≤ xi, yi ≤ 108). W ostatniej linii wejścia będzie podana liczba M określająca numer miasta, z którego pan Jan chciałby rozpocząć wędrówkę (1 ≤ M ≤ N).

Specyfikacja wyjścia

Dla każdego zestawu danych wypisz maksymalną liczbę miast które pan Jan może odwiedzić w ciągu jednej podróży.

Przykład

Wejście

2
4 1
0 0
1 0
1 1
2 0
1
5 2
0 1
2 2
3 1
2 0
2 1
1

Wyjście

3
5

Dodane przez:Michael Suchacz
Data dodania:2010-04-02
Limit czasu wykonania programu:0.130s-0.166s
Limit długości kodu źródłowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: GOSU NODEJS OBJC PERL6 SQLITE VB.NET
Pochodzenie:XI Wiosenny Turniej w Programowaniu Zespołowym
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.