Nemo — беззаботная маленькая рыбка с начальным весом $w_0$. Милый Nemo хочет как можно быстрее вырасти, поэтому ему нужно есть как можно больше. Его любимая еда — маленькие морские креветки.
Nemo знает о своей еде следующее. В море есть $n$ креветок, пронумерованных от $1$ до $n$; вес креветки $i$ равен $w_i$. Рассмотрим море как систему координат $X$–$Y$. В момент $0$ креветка $i$ находится в точке $(x_i,y_i)$. Креветки движутся равномерно и прямолинейно. Вектор скорости креветки $i$ равен $(p_i,q_i)$, поэтому в момент $t$ её положение равно
$$ (x_i+p_i t,y_i+q_i t). $$
В момент $0$ Nemo находится в точке $(x_0,y_0)$ и может произвольно перемещаться по морю со скоростью не выше $V$. Он хочет съесть креветок с как можно большим суммарным весом за $T$ единиц времени, включая момент $T$. Если Nemo и некоторая креветка одновременно оказываются в одной точке и вес креветки меньше текущего веса Nemo, он может её съесть. Съев креветку веса $w_i$, он увеличивает свой вес на $w_i$. Обратите внимание: креветки не едят Nemo и не едят друг друга.
Nemo просит вас помочь ему составить план роста, чтобы суммарный вес съеденных креветок был наибольшим.
Входные данные
Это задача с отправкой только ответов. Все входные данные nemo1.in–nemo10.in находятся в каталоге задачи.
Для каждого набора первая строка входного файла содержит пять вещественных чисел $w_0,V,T,x_0,y_0$ — начальный вес Nemo, максимальную скорость, ограничение времени и положение Nemo в момент $0$ соответственно.
Вторая строка содержит целое число $n$ — количество креветок в море.
Следующие $n$ строк содержат по 5 вещественных чисел $w_i,x_i,y_i,p_i,q_i$ — вес креветки $i$, её положение в момент $0$ и вектор скорости соответственно.
Выходные данные
Для 10 заданных входных файлов nemo1.in–nemo10.in нужно отправить соответствующие выходные файлы nemo1.out–nemo10.out.
Первая строка выходного файла содержит целое число $k$: согласно вашему плану роста Nemo съест $k$ креветок.
Вторая строка содержит вещественное число $w$ — суммарный вес креветок, съеденных Nemo согласно вашему плану.
Следующие $k$ строк содержат по 4 числа $t,x,y,s$, означающих, что в момент $t$ Nemo съел креветку номер $s$ в точке $(x,y)$. Здесь $t,x,y$ — вещественные числа, а $s$ — целое.
Для обеспечения точности проверяющей программы рекомендуется выводить все вещественные числа как минимум с 6 знаками после десятичной точки. Проверяющая программа считает два вещественных числа равными, если их абсолютная разность не превышает $10^{-4}$.
Примеры
Входные данные 1
5 1 6 0 0 1 5 2 2 0 0
Выходные данные 1
1 5 5 2 2 1
Примечание
В этом примере Nemo съедает креветку номер $1$ в момент $5$ в точке $(2,2)$. В действительности он может добраться до $(2,2)$ раньше, однако требуется лишь, чтобы его скорость не превышала $V$.
Подзадачи
Для каждого набора данных заданы 9 параметров оценки $a_{10},a_9,\ldots,a_2$. Если вывод участника некорректен, начисляется ноль баллов. Иначе, пусть в вашем плане прирост веса Nemo равен $w_{user}$. Тогда ваш балл определяется следующей таблицей:
| Балл | Условие | Балл | Условие |
|---|---|---|---|
| 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$ |
Если выполнено несколько условий, берётся наибольший балл среди выполненных условий.