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

MWP8_1H - W blasku reflektorów

Pracujesz w galerii sztuki współczesnej jako specjalista od oświetlenia. Twoim zadaniem jest ustawienie n reflektorów, tak aby oświetliły jak najwięcej z m eksponatów. Wszystkie lampy są zawieszone pod sufitem w punkcie rx, ry. Każdy reflektor świeci cienką, nierozpraszającą się, wiązką światła, oświetlając wszystkie eksponaty znajdujące się na jej drodze.

Twoim zadaniem jest obliczenie ile maksymalnie z m eksponatów możesz oświetlić korzystając z n reflektorów.

Wejście

W pierwszej linii wejścia znajduje się jedna liczba całkowita t określająca liczbę zestawów danych.

W pierwszej linii każdego zestawu danych znajdują się cztery liczby całkowite rx, ry ∈ [-109;109], n ∈ [1;105] i m ∈ [1;105] opisane powyżej. W kolejnych m liniach znajdują się po dwie liczby całkowite x, y ∈ [-109;109] określające współrzędne kolejnych eksponatów.

Gwarantujemy, że suma n ze wszystkich zestawów danych jest mniejsza bądź równa 105.

Wyjście

Dla każdego zestawu danych należy w osobnej linii wypisać maksymalną liczbę eksponatów jakie możesz oświetlić.

Przykład

Wejście:

1
1 0 2 6
0 2
9 4
2 2
7 3
3 1
3 4

Wyjście:

5

Wyjaśnienie do przykładu:

Wiązką światła z pierwszego reflektora możemy oświetlić eksponaty o współrzędnych: 2,2 oraz 3,4 zaś wiązką światła z drugiego reflektora eksponaty: 3,1 7,3 oraz 9,4.


Dodane przez:Maciej Boniecki
Data dodania:2016-03-12
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 JS-MONKEY
Pochodzenie:VIII Mistrzostwa WWSI w Programowaniu
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.