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). $$
בזמן $0$, מיקומו של Nemo הוא $(x_0,y_0)$. הוא יכול לנוע בחופשיות בים, אך מהירותו אינה עולה על $V$. הוא רוצה למקסם את המשקל הכולל של החסילונים שיאכל בתוך $T$ יחידות זמן, כולל הזמן $T$ עצמו. כאשר Nemo וחסילון מגיעים לאותו מקום באותו זמן, ומשקל החסילון קטן ממשקלו של Nemo באותו רגע, Nemo יכול לאכול אותו. לאחר שהוא אוכל חסילון במשקל $w_i$, משקלו גדל ב־$w_i$. שימו לב שהחסילונים אינם אוכלים את Nemo, וגם אינם אוכלים זה את זה.
Nemo מבקש שתעזרו לו להכין תוכנית גדילה הממקסמת את המשקל הכולל של החסילונים שיאכל.
קלט
זוהי שאלה שבה מגישים קובצי פלט. כל קובצי הקלט, nemo1.in עד nemo10.in, כבר נמצאים בתיקיית השאלה.
עבור כל מקרה, השורה הראשונה בקובץ הקלט מכילה חמישה מספרים ממשיים $w_0,V,T,x_0,y_0$, המציינים בהתאמה את משקלו ההתחלתי של Nemo, את מהירותו המרבית, את מגבלת הזמן ואת מיקומו בזמן $0$.
השורה השנייה מכילה מספר שלם $n$, המציין את מספר החסילונים בים.
כל אחת מ־$n$ השורות הבאות מכילה חמישה מספרים ממשיים $w_i,x_i,y_i,p_i,q_i$, המציינים בהתאמה את משקל חסילון $i$, את מיקומו בזמן $0$ ואת וקטור המהירות שלו.
פלט
עבור עשרת קובצי הקלט הנתונים, nemo1.in עד nemo10.in, עליכם להגיש בהתאמה את קובצי הפלט nemo1.out עד nemo10.out.
השורה הראשונה בקובץ הפלט מכילה מספר שלם $k$, המציין שבתוכנית הגדילה שלכם Nemo יאכל $k$ חסילונים.
השורה השנייה מכילה מספר ממשי $w$, המציין את המשקל הכולל של החסילונים ש־Nemo יאכל בתוכנית שלכם.
כל אחת מ־$k$ השורות הבאות מכילה ארבעה מספרים $t,x,y,s$, המציינים שבזמן $t$, Nemo אוכל את חסילון $s$ במקום $(x,y)$. כאן $t,x,y$ הם מספרים ממשיים, ו־$s$ הוא מספר שלם.
כדי להבטיח את דיוק תוכנית האימות, מומלץ להדפיס כל מספר ממשי עם לפחות שש ספרות אחרי הנקודה העשרונית. תוכנית האימות תחשיב שני מספרים ממשיים כשווים אם השגיאה המוחלטת ביניהם אינה עולה על $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)$. למעשה, הוא יכול להגיע ל־$(2,2)$ מוקדם יותר, אך השאלה דורשת רק שמהירותו לא תעלה על $V$.
ניקוד
לכל מקרה בדיקה הגדרנו תשעה פרמטרי ניקוד $a_{10},a_9,\ldots,a_2$. אם הפלט שלכם אינו חוקי, תקבלו אפס נקודות. אחרת, נסמן ב־$w_{user}$ את העלייה במשקלו של Nemo בתוכנית שלכם. הניקוד נקבע לפי הטבלה:
| ניקוד | תנאי | ניקוד | תנאי |
|---|---|---|---|
| $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$ |
אם מתקיימים כמה תנאים, יינתן הניקוד הגבוה ביותר מבין התנאים המתקיימים.