Nemo ist ein sorgloser kleiner Fisch mit dem Anfangsgewicht $w_0$. Der niedliche Nemo möchte möglichst schnell wachsen und muss dafür möglichst viel Nahrung fressen. Am liebsten frisst er kleine Garnelen aus dem Meer.
Nemo weiß Folgendes über seine Nahrung: Im Meer gibt es $n$ kleine Garnelen, nummeriert von $1$ bis $n$. Garnele $i$ wiegt $w_i$. Wir betrachten das Meer als ein X-Y-Koordinatensystem. Zum Zeitpunkt $0$ befindet sich Garnele $i$ an der Position $(x_i,y_i)$. Die Garnelen bewegen sich geradlinig mit konstanter Geschwindigkeit. Der Geschwindigkeitsvektor von Garnele $i$ ist $(p_i,q_i)$; zum Zeitpunkt $t$ befindet sie sich also an der Position
$$ (x_i+p_i t,y_i+q_i t). $$
Zum Zeitpunkt $0$ ist Nemo an der Position $(x_0,y_0)$. Er darf sich beliebig im Meer bewegen, aber seine Geschwindigkeit darf $V$ nicht überschreiten. Nemo möchte innerhalb von $T$ Zeiteinheiten einschließlich des Zeitpunkts $T$ Garnelen mit möglichst großem Gesamtgewicht fressen. Befinden sich Nemo und eine Garnele zum selben Zeitpunkt am selben Ort und wiegt die Garnele weniger als Nemo zu diesem Zeitpunkt, darf Nemo sie fressen. Frisst Nemo eine Garnele vom Gewicht $w_i$, steigt sein Gewicht um $w_i$. Beachte, dass Garnelen Nemo nicht fressen und sich auch nicht gegenseitig töten.
Nemo möchte, dass du ihm einen Wachstumsplan erstellst, der das Gesamtgewicht der gefressenen Garnelen maximiert.
Eingabe
Dies ist eine Aufgabe, bei der nur die Ausgabedateien eingereicht werden. Alle Eingabedateien nemo1.in bis nemo10.in liegen bereits im Aufgabenverzeichnis.
Für jeden Datensatz enthält die erste Zeile der Eingabedatei fünf reelle Zahlen $w_0,V,T,x_0,y_0$: Nemos Anfangsgewicht, seine maximale Bewegungsgeschwindigkeit, die Zeitgrenze und seine Position zum Zeitpunkt $0$.
Die zweite Zeile enthält eine ganze Zahl $n$, die Anzahl der Garnelen im Meer.
Es folgen $n$ Zeilen mit jeweils fünf reellen Zahlen $w_i,x_i,y_i,p_i,q_i$. Diese geben das Gewicht, die Position zum Zeitpunkt $0$ und den Geschwindigkeitsvektor der $i$-ten Garnele an.
Ausgabe
Für die 10 gegebenen Eingabedateien nemo1.in bis nemo10.in musst du jeweils eine Ausgabedatei nemo1.out bis nemo10.out einreichen.
Die erste Zeile der Ausgabedatei enthält eine ganze Zahl $k$: die Anzahl der Garnelen, die Nemo in deinem Wachstumsplan frisst.
Die zweite Zeile enthält eine reelle Zahl $w$, das Gesamtgewicht der Garnelen, die Nemo in deinem Wachstumsplan frisst.
Es folgen $k$ Zeilen mit jeweils vier Zahlen $t,x,y,s$. Diese bedeuten, dass Nemo zum Zeitpunkt $t$ an der Position $(x,y)$ die Garnele mit der Nummer $s$ frisst. Dabei sind $t,x,y$ reelle Zahlen und $s$ eine ganze Zahl.
Um die Genauigkeit des Prüfprogramms zu gewährleisten, wird empfohlen, alle reellen Zahlen mit mindestens sechs Nachkommastellen auszugeben. Das Prüfprogramm betrachtet zwei reelle Zahlen als gleich, wenn ihr absoluter Unterschied höchstens $10^{-4}$ beträgt.
Beispiele
Eingabe 1
5 1 6 0 0 1 5 2 2 0 0
Ausgabe 1
1 5 5 2 2 1
Hinweis
In diesem Beispiel frisst Nemo zum Zeitpunkt $5$ die Garnele mit der Nummer $1$ an der Position $(2,2)$. Nemo könnte $(2,2)$ tatsächlich schon früher erreichen, aber die Aufgabe verlangt lediglich, dass seine Geschwindigkeit höchstens $V$ beträgt.
Teilaufgaben
Für jeden Datensatz sind neun Bewertungsparameter $a_{10},a_9,\ldots,a_2$ festgelegt. Ist deine Ausgabe ungültig, erhältst du keine Punkte. Andernfalls sei $w_{user}$ Nemos Gewichtszunahme in deinem Plan. Deine Punktzahl ergibt sich aus der folgenden Tabelle:
| Punkte | Bedingung | Punkte | Bedingung |
|---|---|---|---|
| $10$ | $w_{user}\ge a_{10}$ | $5$ | $w_{user}\ge a_5$ |
| $9$ | $w_{user}\ge a_9$ | $4$ | $w_{user}\ge a_4$ |
| $8$ | $w_{user}\ge a_8$ | $3$ | $w_{user}\ge a_3$ |
| $7$ | $w_{user}\ge a_7$ | $2$ | $w_{user}\ge a_2$ |
| $6$ | $w_{user}\ge a_6$ | $1$ | $w_{user}>0$ |
Sind mehrere Bedingungen erfüllt, zählt die höchste zugehörige Punktzahl.