Nemo is a carefree little fish with an initial weight of $w_0$. The cute Nemo hopes to grow as quickly as possible, so it needs to eat as much food as possible. Nemo's favorite food is the shrimp in the sea.
Nemo knows the following about the food: there are $n$ shrimp in the sea, numbered from $1$ to $n$. The weight of the shrimp numbered $i$ is $w_i$. Treating the sea as an $X-Y$ coordinate system, at time $t=0$, the shrimp numbered $i$ is at position $(x_i, y_i)$. The shrimp move in the sea in a straight line at a constant velocity, where the velocity vector of the shrimp numbered $i$ is $(p_i, q_i)$. That is, at time $t$, its position is: $$(x_i + p_i \cdot t, y_i + q_i \cdot t)$$
Nemo is at position $(x_0, y_0)$ at time $t=0$. It can move freely in the sea, but its speed cannot exceed $V$. Nemo hopes to maximize the total weight of the shrimp it eats within $T$ units of time (inclusive of time $T$). When Nemo and a shrimp move to the same position at the same time, and the weight of the shrimp is less than Nemo's current weight, Nemo can eat that shrimp. After Nemo eats a shrimp of weight $w_i$, its weight increases by $w_i$. Note that shrimp do not eat Nemo, and shrimp do not eat each other.
Nemo wants you to help it develop a growth plan to maximize the total weight of the shrimp it eats.
Input
This is an answer-submission problem. The input files nemo1.in through nemo10.in are provided in the problem directory.
For each dataset, the first line of the input file contains five real numbers $w_0, V, T, x_0, y_0$, representing Nemo's initial weight, maximum movement speed, time limit, and Nemo's position at time $t=0$, respectively.
The second line contains an integer $n$, representing the number of shrimp in the sea.
The next $n$ lines each contain five real numbers $w_i, x_i, y_i, p_i, q_i$, representing the weight, position at time $t=0$, and velocity vector of the shrimp numbered $i$, respectively.
Output
For the given 10 input files nemo1.in through nemo10.in, you need to submit your output files nemo1.out through nemo10.out respectively.
The first line of the output file contains an integer $k$, representing the number of shrimp Nemo eats in your growth plan.
The second line contains a real number $w$, representing the total weight of the shrimp Nemo eats in your growth plan.
The next $k$ lines each contain four values $t, x, y, s$, representing that at time $t$, Nemo eats the shrimp numbered $s$ at position $(x, y)$. Here $t, x, y$ are real numbers and $s$ is an integer.
To ensure the precision of the verification process, it is recommended to output real numbers to at least 6 decimal places. In the verification process, two real numbers are considered equal if their absolute difference does not exceed $10^{-4}$.
Examples
Input 1
5 1 6 0 0 1 5 2 2 0 0
Output 1
1 5 5 2 2 1
Note
In this example, Nemo eats shrimp number 1 at position $(2, 2)$ at time $5$. In fact, Nemo could have reached $(2, 2)$ earlier, but the problem only requires that the speed does not exceed $V$.
Subtasks
For each dataset, we have set 9 scoring parameters $a_{10}, a_9, \dots, a_2$. If the contestant's output is invalid, the score is zero. Otherwise, let $w_{user}$ be the increase in Nemo's weight in your plan. Your score will be given by the table below:
| Score | Condition | Score | Condition |
|---|---|---|---|
| 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$ |
If multiple conditions are met, the highest score among the satisfied conditions is taken.
Table 1. Scoring criteria