Nemo é um peixinho despreocupado, com peso inicial $w_0$. O adorável Nemo quer crescer o mais depressa possível e, por isso, precisa de comer o máximo de alimento que puder. A sua comida favorita são os camarõezinhos do mar.
Nemo conhece as seguintes informações sobre o alimento: existem no mar $n$ camarões, numerados de $1$ a $n$, e o camarão $i$ pesa $w_i$. Considera o mar como um sistema de coordenadas $X$-$Y$. No instante $0$, o camarão $i$ está na posição $(x_i,y_i)$. Os camarões deslocam-se em linha reta com velocidade constante. O vetor velocidade do camarão $i$ é $(p_i,q_i)$, ou seja, no instante $t$, a sua posição é
$$ (x_i+p_i*t,y_i+q_i*t). $$
No instante $0$, Nemo está na posição $(x_0,y_0)$. Pode mover-se livremente pelo mar, mas a sua velocidade não pode exceder $V$. Nemo quer, pelo seu próprio esforço, maximizar o peso total dos camarões que come durante $T$ unidades de tempo, incluindo o instante $T$. Quando Nemo e um camarão chegam à mesma posição ao mesmo tempo, e o peso do camarão é menor do que o peso de Nemo nesse instante, Nemo pode comê-lo. Depois de comer um camarão de peso $w_i$, o peso de Nemo aumenta em $w_i$. Repara que os camarões não comem Nemo nem se matam uns aos outros.
Nemo quer que o ajudes a elaborar um plano de crescimento que maximize o peso total dos camarões que come.
Entrada
Este é um problema em que se submetem apenas as respostas. Todos os ficheiros de entrada, de nemo1.in a nemo10.in, já estão no diretório do problema.
Para cada caso, a primeira linha do ficheiro de entrada contém cinco números reais $w_0,V,T,x_0,y_0$: respetivamente, o peso inicial de Nemo, a sua velocidade máxima, o limite de tempo e a sua posição no instante $0$.
A segunda linha contém um inteiro $n$, que representa o número de camarões no mar.
Seguem-se $n$ linhas, cada uma com cinco números reais $w_i,x_i,y_i,p_i,q_i$: respetivamente, o peso do camarão $i$, a sua posição no instante $0$ e o seu vetor velocidade.
Saída
Para os 10 ficheiros de entrada dados, de nemo1.in a nemo10.in, deves submeter, respetivamente, os ficheiros de saída de nemo1.out a nemo10.out.
A primeira linha do ficheiro de saída contém um inteiro $k$, que indica que Nemo comerá $k$ camarões no teu plano de crescimento.
A segunda linha contém um número real $w$, que representa o peso total dos camarões que Nemo comerá no teu plano.
Seguem-se $k$ linhas, cada uma com quatro números $t,x,y,s$: no instante $t$, Nemo come o camarão de número $s$ na posição $(x,y)$. Aqui, $t,x,y$ são números reais e $s$ é inteiro.
Para garantir a precisão do verificador, recomenda-se apresentar todos os números reais com pelo menos 6 casas decimais. O verificador considera dois números reais iguais se a diferença absoluta entre eles não exceder $10^{-4}$.
Exemplos
Entrada 1
5 1 6 0 0 1 5 2 2 0 0
Saída 1
1 5 5 2 2 1
Nota
Neste exemplo, Nemo come o camarão $1$ no instante $5$, na posição $(2,2)$. Na verdade, Nemo poderia chegar a $(2,2)$ mais cedo, mas o problema apenas exige que a sua velocidade não exceda $V$.
Avaliação
Para cada caso de teste, definimos 9 parâmetros de pontuação, $a_{10},a_9,\ldots,a_2$. Se a saída do concorrente for inválida, a pontuação é zero. Caso contrário, seja $w_{user}$ o aumento do peso de Nemo no teu plano. A tua pontuação é dada pela tabela seguinte:
| Pontuação | Condição | Pontuação | Condição |
|---|---|---|---|
| $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$ |
Se forem satisfeitas várias condições, aplica-se a maior pontuação correspondente.