Nemo — безтурботна маленька рибка з початковою вагою $w_0$. Милий Nemo хоче якнайшвидше вирости, тому йому потрібно їсти якомога більше. Найулюбленіша їжа 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). $$
У момент $0$ Nemo перебуває в точці $(x_0,y_0)$. Він може рухатися морем довільно, але зі швидкістю не більшою за $V$. Nemo хоче, щоб сумарна вага креветок, яких він з'їсть протягом $T$ одиниць часу (включно з моментом $T$), була якнайбільшою. Якщо Nemo і креветка одночасно опиняються в одній точці та вага креветки менша за поточну вагу Nemo, він може її з'їсти. З'ївши креветку вагою $w_i$, Nemo збільшує свою вагу на $w_i$. Зверніть увагу: креветки не їдять Nemo й не їдять одна одну.
Допоможіть Nemo скласти план зростання, за якого сумарна вага з'їдених креветок буде якнайбільшою.
Вхідні дані
Це задача з поданням лише відповідей. Усі вхідні файли nemo1.in–nemo10.in уже є в каталозі задачі.
У кожному наборі перший рядок вхідного файлу містить п'ять дійсних чисел $w_0,V,T,x_0,y_0$ — початкову вагу Nemo, найбільшу швидкість руху, обмеження часу та координати Nemo в момент $0$ відповідно.
Другий рядок містить ціле число $n$ — кількість креветок у морі.
Кожен із наступних $n$ рядків містить п'ять дійсних чисел $w_i,x_i,y_i,p_i,q_i$ — вагу креветки $i$, її координати в момент $0$ та вектор швидкості відповідно.
Вихідні дані
Для 10 заданих вхідних файлів nemo1.in–nemo10.in потрібно подати відповідні вихідні файли nemo1.out–nemo10.out.
Перший рядок вихідного файлу містить ціле число $k$ — кількість креветок, яких Nemo з'їсть за вашим планом.
Другий рядок містить дійсне число $w$ — сумарну вагу креветок, яких Nemo з'їсть за вашим планом.
Кожен із наступних $k$ рядків містить чотири числа $t,x,y,s$: у момент $t$ Nemo з'їдає креветку з номером $s$ у точці $(x,y)$. Тут $t,x,y$ — дійсні числа, а $s$ — ціле.
Для точності перевірки рекомендовано виводити всі дійсні числа щонайменше з 6 знаками після десяткової крапки. Перевіряльна програма вважає два дійсні числа рівними, якщо їхня абсолютна різниця не перевищує $10^{-4}$.
Приклади
Вхідні дані 1
5 1 6 0 0 1 5 2 2 0 0
Вихідні дані 1
1 5 5 2 2 1
Пояснення
У цьому прикладі Nemo з'їдає креветку $1$ у момент $5$ у точці $(2,2)$. Насправді Nemo може дістатися $(2,2)$ раніше, але в задачі потрібно лише, щоб його швидкість не перевищувала $V$.
Оцінювання
Для кожного набору задано 9 параметрів оцінювання $a_{10},a_9,\ldots,a_2$. Якщо виведення некоректне, ви отримуєте 0 балів. Інакше нехай приріст ваги Nemo за вашим планом дорівнює $w_{user}$. Ваші бали визначаються таблицею:
| Бали | Умова | Бали | Умова |
|---|---|---|---|
| 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$ |
Якщо виконуються кілька умов, нараховується найбільша відповідна кількість балів.