Nemo to beztroska mała rybka o początkowej masie $w_0$. Uroczy Nemo chce jak najszybciej rosnąć, więc musi zjadać jak najwięcej pożywienia. Jego ulubionym pokarmem są małe krewetki żyjące w morzu.
Nemo wie o pożywieniu następujące rzeczy: w morzu znajduje się $n$ krewetek, ponumerowanych od $1$ do $n$, a krewetka numer $i$ waży $w_i$. Traktujemy morze jako układ współrzędnych $X$–$Y$. W chwili $0$ krewetka numer $i$ znajduje się w punkcie $(x_i,y_i)$. Krewetki poruszają się ruchem jednostajnym prostoliniowym; wektor prędkości krewetki numer $i$ wynosi $(p_i,q_i)$, zatem w chwili $t$ jej położenie to
$$ (x_i+p_i*t,y_i+q_i*t). $$
W chwili $0$ Nemo znajduje się w punkcie $(x_0,y_0)$. Może poruszać się po morzu dowolnie, ale z prędkością nie większą niż $V$. Chce, aby łączna masa krewetek zjedzonych w czasie $T$ jednostek czasu (włącznie z chwilą $T$) była jak największa. Jeśli Nemo i krewetka znajdą się jednocześnie w tym samym miejscu, a masa krewetki jest mniejsza od aktualnej masy Nemo, może on ją zjeść. Po zjedzeniu krewetki o masie $w_i$ masa Nemo wzrasta o $w_i$. Uwaga: krewetki nie zjadają Nemo ani siebie nawzajem.
Nemo prosi cię o opracowanie planu wzrostu, który zmaksymalizuje łączną masę zjedzonych krewetek.
Wejście
Jest to zadanie typu output-only. Wszystkie dane wejściowe nemo1.in–nemo10.in znajdują się w katalogu zadania.
Pierwszy wiersz każdego pliku wejściowego zawiera pięć liczb rzeczywistych $w_0,V,T,x_0,y_0$: początkową masę Nemo, jego maksymalną prędkość, limit czasu oraz jego położenie w chwili $0$.
Drugi wiersz zawiera liczbę całkowitą $n$, oznaczającą liczbę krewetek w morzu.
Każdy z następnych $n$ wierszy zawiera pięć liczb rzeczywistych $w_i,x_i,y_i,p_i,q_i$: masę krewetki numer $i$, jej położenie w chwili $0$ oraz wektor prędkości.
Wyjście
Dla podanych $10$ plików wejściowych nemo1.in–nemo10.in należy zgłosić odpowiednio pliki wyjściowe nemo1.out–nemo10.out.
Pierwszy wiersz pliku wyjściowego zawiera liczbę całkowitą $k$, oznaczającą, że w twoim planie Nemo zje $k$ krewetek.
Drugi wiersz zawiera liczbę rzeczywistą $w$: łączną masę krewetek zjedzonych przez Nemo w twoim planie.
Każdy z następnych $k$ wierszy zawiera cztery liczby $t,x,y,s$. Oznaczają one, że w chwili $t$ Nemo zjada w punkcie $(x,y)$ krewetkę numer $s$. Liczby $t,x,y$ są rzeczywiste, a $s$ jest całkowite.
Aby zapewnić dokładność weryfikatora, zaleca się wypisywanie wszystkich liczb rzeczywistych z co najmniej sześcioma cyframi po przecinku. Weryfikator uznaje dwie liczby rzeczywiste za równe, jeśli ich różnica bezwzględna nie przekracza $10^{-4}$.
Przykład
Wejście 1
5 1 6 0 0 1 5 2 2 0 0
Wyjście 1
1 5 5 2 2 1
Uwagi
W tym przykładzie Nemo zjada krewetkę numer $1$ w chwili $5$ w punkcie $(2,2)$. Mógłby dotrzeć do $(2,2)$ wcześniej, ale zadanie wymaga jedynie, aby jego prędkość nie przekraczała $V$.
Podzadania
Dla każdego zestawu danych ustalono dziewięć parametrów punktacji $a_{10},a_9,\ldots,a_2$. Niepoprawne wyjście otrzymuje zero punktów. W przeciwnym razie niech $w_{\mathrm{user}}$ oznacza przyrost masy Nemo w twoim planie. Punktację określa poniższa tabela:
| Punkty | Warunek | Punkty | Warunek |
|---|---|---|---|
| $10$ | $w_{\mathrm{user}}\ge a_{10}$ | $5$ | $w_{\mathrm{user}}\ge a_5$ |
| $9$ | $w_{\mathrm{user}}\ge a_9$ | $4$ | $w_{\mathrm{user}}\ge a_4$ |
| $8$ | $w_{\mathrm{user}}\ge a_8$ | $3$ | $w_{\mathrm{user}}\ge a_3$ |
| $7$ | $w_{\mathrm{user}}\ge a_7$ | $2$ | $w_{\mathrm{user}}\ge a_2$ |
| $6$ | $w_{\mathrm{user}}\ge a_6$ | $1$ | $w_{\mathrm{user}}>0$ |
Jeśli spełnionych jest kilka warunków, przyznaje się najwyższą odpowiadającą im liczbę punktów.