Nemo es un pececillo despreocupado cuyo peso inicial es $w_0$. El adorable Nemo quiere crecer lo más rápido posible, por lo que necesita comer tanto alimento como pueda. Su comida favorita son los camarones del mar.
Nemo conoce la siguiente información sobre su comida. Hay $n$ camarones en el mar, numerados de $1$ a $n$, y el peso del camarón $i$ es $w_i$. Consideramos el mar como un sistema de coordenadas $X$-$Y$. En el instante $0$, el camarón $i$ se encuentra en $(x_i,y_i)$. Los camarones se mueven en línea recta a velocidad constante. El vector de velocidad del camarón $i$ es $(p_i,q_i)$, por lo que, en el instante $t$, su posición es
$$(x_i+p_i\cdot t, y_i+q_i\cdot t).$$
En el instante $0$, Nemo se encuentra en $(x_0,y_0)$. Puede moverse libremente por el mar, pero su rapidez no puede superar $V$. Nemo quiere maximizar el peso total de los camarones que come durante $T$ unidades de tiempo (incluido el instante $T$). Cuando Nemo y un camarón se encuentran simultáneamente en la misma posición, y el peso del camarón es menor que el peso de Nemo en ese momento, Nemo puede comérselo. Después de comer un camarón de peso $w_i$, su peso aumenta en $w_i$. Ten en cuenta que los camarones no se comen a Nemo ni se comen entre sí.
Nemo quiere que lo ayudes a elaborar un plan de crecimiento que maximice el peso total de los camarones que come.
Entrada
Este es un problema de solo salida. Todos los datos de entrada, nemo1.in a nemo10.in, ya se encuentran en el directorio del problema.
Para cada conjunto de datos, la primera línea del archivo de entrada contiene cinco números reales $w_0,V,T,x_0,y_0$. Representan, respectivamente, el peso inicial de Nemo, su rapidez máxima de movimiento, el límite de tiempo y su posición en el instante $0$.
La segunda línea contiene un entero $n$, que indica el número de camarones del mar.
Las siguientes $n$ líneas contienen cinco números reales cada una: $w_i,x_i,y_i,p_i,q_i$, que representan, respectivamente, el peso del camarón $i$, su posición en el instante $0$ y su vector de velocidad.
Salida
Para los 10 archivos de entrada dados, nemo1.in a nemo10.in, debes entregar los archivos de salida correspondientes, nemo1.out a nemo10.out.
La primera línea del archivo de salida contiene un entero $k$, que indica que Nemo comerá $k$ camarones en tu plan de crecimiento.
La segunda línea contiene un número real $w$, que indica el peso total de los camarones que Nemo comerá en tu plan.
Las siguientes $k$ líneas contienen cuatro números cada una: $t,x,y,s$. Indican que, en el instante $t$, Nemo come el camarón $s$ en la posición $(x,y)$. Aquí $t,x,y$ son números reales y $s$ es un entero.
Para asegurar la precisión del verificador, se recomienda imprimir todos los números reales con al menos 6 cifras después del punto decimal. El verificador considera iguales dos números reales si su diferencia absoluta no supera $10^{-4}$.
Ejemplos
Entrada 1
5 1 6 0 0 1 5 2 2 0 0
Salida 1
1 5 5 2 2 1
Nota
En este ejemplo, Nemo come el camarón $1$ en el instante $5$, en la posición $(2,2)$. En realidad, Nemo puede llegar a $(2,2)$ antes, pero el problema solo exige que su rapidez no supere $V$.
Subtareas
Para cada conjunto de datos, se establecen 9 parámetros de puntuación $a_{10},a_9,\ldots,a_2$. Si tu salida no es válida, obtienes cero puntos. En caso contrario, si el aumento de peso de Nemo en tu plan es $w_{\mathrm{user}}$, tu puntuación viene dada por la siguiente tabla:
| Puntuación | Condición | Puntuación | Condición |
|---|---|---|---|
| $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$ |
Si se satisfacen varias condiciones, se toma la mayor puntuación entre ellas.