Nemo là một chú cá nhỏ vô tư, có khối lượng ban đầu $w_0$. Nemo đáng yêu muốn lớn thật nhanh nên cần ăn nhiều thức ăn nhất có thể. Thức ăn yêu thích nhất của Nemo là những con tôm nhỏ trong biển.
Nemo biết những thông tin sau về thức ăn: có $n$ con tôm trong biển, đánh số từ $1$ đến $n$. Tôm thứ $i$ có khối lượng $w_i$. Xem biển là một hệ tọa độ $X$-$Y$. Ở thời điểm $0$, tôm thứ $i$ ở vị trí $(x_i,y_i)$. Các con tôm chuyển động thẳng đều, tôm thứ $i$ có véc-tơ vận tốc $(p_i,q_i)$, tức là ở thời điểm $t$, vị trí của nó là:
$$(x_i+p_i t,y_i+q_i t)$$
Ở thời điểm $0$, Nemo ở $(x_0,y_0)$. Nó có thể di chuyển tùy ý trong biển nhưng tốc độ không vượt quá $V$. Nemo muốn tổng khối lượng tôm ăn được trong $T$ đơn vị thời gian (bao gồm thời điểm $T$) lớn nhất có thể. Khi Nemo và một con tôm cùng đến một vị trí vào cùng thời điểm, và khối lượng tôm nhỏ hơn khối lượng Nemo lúc đó, Nemo có thể ăn con tôm ấy. Sau khi ăn tôm có khối lượng $w_i$, khối lượng Nemo tăng thêm $w_i$. Lưu ý tôm không ăn Nemo và các con tôm cũng không ăn lẫn nhau.
Nemo muốn bạn giúp lập một kế hoạch lớn lên sao cho tổng khối lượng tôm ăn được lớn nhất có thể.
Dữ liệu vào
Đây là bài nộp đáp án. Tất cả tệp dữ liệu nemo1.in đến nemo10.in đã có trong thư mục bài.
Với mỗi bộ dữ liệu, dòng đầu tiên chứa năm số thực $w_0,V,T,x_0,y_0$, lần lượt là khối lượng ban đầu của Nemo, tốc độ di chuyển tối đa, giới hạn thời gian và vị trí của Nemo ở thời điểm $0$.
Dòng thứ hai chứa số nguyên $n$, là số con tôm trong biển.
Mỗi dòng trong $n$ dòng tiếp theo chứa 5 số thực $w_i,x_i,y_i,p_i,q_i$, lần lượt là khối lượng, vị trí ở thời điểm $0$ và véc-tơ vận tốc của tôm thứ $i$.
Dữ liệu ra
Với 10 tệp đầu vào nemo1.in đến nemo10.in, bạn cần nộp các tệp kết quả tương ứng nemo1.out đến nemo10.out.
Dòng đầu tiên chứa số nguyên $k$, biểu thị Nemo sẽ ăn $k$ con tôm trong kế hoạch của bạn.
Dòng thứ hai chứa số thực $w$, là tổng khối lượng tôm Nemo ăn được trong kế hoạch.
Trong $k$ dòng tiếp theo, mỗi dòng chứa 4 số $t,x,y,s$, biểu thị tại thời điểm $t$, Nemo ăn con tôm số $s$ ở vị trí $(x,y)$. Trong đó $t,x,y$ là số thực, $s$ là số nguyên.
Để bảo đảm độ chính xác của trình kiểm tra, nên in mọi số thực với ít nhất 6 chữ số sau dấu thập phân. Trình kiểm tra coi hai số thực bằng nhau nếu sai số tuyệt đối không vượt quá $10^{-4}$.
Ví dụ
Dữ liệu vào 1
5 1 6 0 0 1 5 2 2 0 0
Dữ liệu ra 1
1 5 5 2 2 1
Ghi chú
Trong ví dụ này, Nemo ăn con tôm số $1$ tại thời điểm $5$ ở vị trí $(2,2)$. Thực tế Nemo có thể đến $(2,2)$ sớm hơn, nhưng bài chỉ yêu cầu tốc độ không vượt quá $V$.
Nhiệm vụ con
Với mỗi bộ dữ liệu, chúng tôi đặt 9 tham số chấm điểm $a_{10},a_9,\ldots,a_2$. Nếu kết quả không hợp lệ, bạn nhận 0 điểm. Nếu hợp lệ, gọi mức tăng khối lượng của Nemo trong phương án của bạn là $w_{user}$; điểm được cho theo bảng sau:
| Điểm | Điều kiện | Điểm | Điều kiện |
|---|---|---|---|
| $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$ |
Nếu thỏa mãn nhiều điều kiện, lấy điểm cao nhất trong các điều kiện thỏa mãn.