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) $$
Nemo の時刻 $0$ の位置は $(x_0,y_0)$ です。海の中を自由に移動できますが、速度は $V$ 以下です。Nemo は $T$ 単位時間以内（時刻 $T$ を含みます）に食べる小エビの重さの総和を、できるだけ大きくしたいと思っています。Nemo と小エビが同じ時刻に同じ位置におり、その小エビの重さがその時点の Nemo の体重より小さければ、Nemo はその小エビを食べられます。重さ $w_i$ の小エビを食べると、Nemo の体重は $w_i$ 増えます。小エビは Nemo を食べず、小エビ同士も食べ合わないことに注意してください。
Nemo が食べる小エビの重さの総和をできるだけ大きくする、成長計画を作ってください。
入力
これは出力のみを提出する問題です。すべての入力データ nemo1.in から nemo10.in は、問題ディレクトリにあります。
各入力ファイルの 1 行目には、5 つの実数 $w_0,V,T,x_0,y_0$ が与えられ、Nemo の初期体重、最大速度、時間制限、時刻 $0$ の位置をそれぞれ表します。
2 行目には、海にいる小エビの個数を表す整数 $n$ が与えられます。
続く $n$ 行には、それぞれ 5 つの実数 $w_i,x_i,y_i,p_i,q_i$ が与えられ、$i$ 番の小エビの重さ、時刻 $0$ の位置、速度ベクトルを表します。
出力
10 個の入力ファイル nemo1.in から nemo10.in に対し、それぞれ出力ファイル nemo1.out から nemo10.out を提出してください。
1 行目には、成長計画の中で Nemo が食べる小エビの個数を表す整数 $k$ を出力してください。
2 行目には、成長計画の中で Nemo が食べる小エビの重さの総和を表す実数 $w$ を出力してください。
続く $k$ 行には、それぞれ 4 つの数 $t,x,y,s$ を出力してください。これは、時刻 $t$ に Nemo が位置 $(x,y)$ で $s$ 番の小エビを食べることを表します。$t,x,y$ は実数、$s$ は整数です。
検証プログラムの精度を保つため、すべての実数は少なくとも小数点以下 6 桁まで出力することを推奨します。検証プログラムでは、2 つの実数の絶対誤差が $10^{-4}$ 以下なら、等しいものとみなします。
入出力例
入力 1
5 1 6 0 0 1 5 2 2 0 0
出力 1
1 5 5 2 2 1
注記
この例では、Nemo は時刻 $5$ に位置 $(2,2)$ で $1$ 番の小エビを食べます。実際にはもっと早く $(2,2)$ に到達できますが、問題では速度が $V$ 以下であることだけを要求しています。
小課題
各テストデータには、9 個の採点パラメータ $a_{10},a_9,\ldots,a_2$ を設定しています。出力が不正なら 0 点です。それ以外の場合、計画による Nemo の体重増加量を $w_{user}$ とすると、得点は次の表で与えられます。
| 得点 | 条件 | 得点 | 条件 |
|---|---|---|---|
| $10$ | $w_{user} \geq a_{10}$ | $5$ | $w_{user} \geq a_5$ |
| $9$ | $w_{user} \geq a_9$ | $4$ | $w_{user} \geq a_4$ |
| $8$ | $w_{user} \geq a_8$ | $3$ | $w_{user} \geq a_3$ |
| $7$ | $w_{user} \geq a_7$ | $2$ | $w_{user} \geq a_2$ |
| $6$ | $w_{user} \geq a_6$ | $1$ | $w_{user}>0$ |
複数の条件を満たす場合は、満たす条件の中で最も高い得点を採用します。