N הקטן הוא מנהל מחסן ירקות, האחראי לתכנון תוכנית המכירות של הירקות.
במחסן מאוחסנים $n$ סוגי ירקות. N הקטן צריך להתחשב במאפיינים של כל סוג ובמכלול הגורמים כדי לתכנן תוכנית מכירות סבירה שתניב את ההכנסה המרבית.
מכירת יחידה אחת של ירק מסוג $i$ מניבה הכנסה של $a_i$.
בפרט, מכיוון שהמדיניות מעודדת סוחרים לגוון את המכירות, המכירה הראשונה של ירק מסוג $i$ מניבה גם הכנסה נוספת של $s_i$.
בתחילת הפעילות המלאי של ירק מסוג $i$ הוא $c_i$ יחידות.
אולם הירקות נשמרים לזמן מוגבל מאוד, וברגע שהם מתקלקלים אי אפשר למכור אותם. N הקטן החכם כבר חישב מתי כל יחידה תתקלקל: לירק מסוג $i$ יש ערך שימור $x_i$, ובסוף כל יום מתקלקלות $x_i$ יחידות, עד שכל הירקות מתקלקלים. (שימו לב: זמן הקלקול של כל יחידה קבוע ואינו משתנה בעקבות המכירות.)
באופן פורמלי: לכל מספר שלם חיובי $d$ המקיים $d\times x_i\le c_i$, יש $x_i$ יחידות שיתקלקלו בסוף היום ה־$d$.
בפרט, אם $(d-1)\times x_i\le c_i<d\times x_i$, אז $c_i-(d-1)\times x_i$ יחידות יתקלקלו בסוף היום ה־$d$.
שימו לב שכאשר $x_i=0$, פירוש הדבר שירקות מסוג זה אינם מתקלקלים.
בנוסף, הכמות הכוללת של ירקות שניתן למכור בכל יום מוגבלת ואינה יכולה לעלות על $m$ יחידות.
כעת ל־N הקטן יש $k$ שאלות שבהן הוא מבקש את עזרתכם. כל שאלה היא מהצורה הבאה: עבור $p_j$ נתון, אם מוכרים במשך $p_j$ ימים, מהי ההכנסה המרבית שאפשר להשיג?
קלט
קראו את הנתונים מהקובץ vegetables.in.
השורה הראשונה מכילה שלושה מספרים שלמים חיוביים $n,m,k$, המציינים, בהתאמה, את מספר סוגי הירקות, את החסם העליון על כמות הירקות הכוללת שניתן למכור ביום, ואת מספר השאלות של N הקטן.
כל אחת מ־$n$ השורות הבאות מכילה ארבעה מספרים שלמים אי־שליליים, המתארים את מאפייניו של סוג ירק אחד. לפי הסדר הם $a_i,s_i,c_i,x_i$, שמשמעותם מוסברת לעיל.
כל אחת מ־$k$ השורות הבאות מכילה מספר שלם אי־שלילי $p_j$, שמשמעותו מוסברת לעיל.
פלט
כתבו את הפלט לקובץ vegetables.out.
הדפיסו $k$ שורות, שבכל אחת מהן מספר שלם אחד. המספר בשורה ה־$i$ הוא התשובה לשאלה ה־$i$.
דוגמאות
קלט 1
2 3 2 3 3 3 3 2 5 8 3 1 3
פלט 1
16 27
דוגמה 2
ראו את הקבצים vegetables/vegetables2.in ו־vegetables/vegetables2.ans בתיקיית המתחרה.
דוגמה 3
ראו את הקבצים vegetables/vegetables3.in ו־vegetables/vegetables3.ans בתיקיית המתחרה.
הסבר לדוגמה 1
יש שני סוגי ירקות:
מכירת יחידה מהסוג הראשון מניבה הכנסה של $3$, ובמכירה הראשונה מסוג זה מתקבלת הכנסה נוספת של $3$. יש $3$ יחידות מהסוג הזה, וכולן מתקלקלות בסוף היום הראשון.
מכירת יחידה מהסוג השני מניבה הכנסה של $2$, ובמכירה הראשונה מסוג זה מתקבלת הכנסה נוספת של $5$. יש $8$ יחידות מהסוג הזה: $3$ מתקלקלות בסוף היום הראשון, $3$ בסוף היום השני ו־$2$ בסוף היום השלישי.
כאשר מוכרים במשך יום אחד בלבד, יש למכור $2$ יחידות מהסוג הראשון ויחידה אחת מהסוג השני.
במקרה זה, ההכנסה ממכירת הסוג הראשון היא $2\times3+3$, וההכנסה ממכירת הסוג השני היא $1\times2+5$. ההכנסה הכוללת היא $(2\times3+3)+(1\times2+5)=16$.
כאשר מוכרים במשך $3$ ימים בלבד, ביום הראשון יש למכור $3$ יחידות מהסוג הראשון, ביום השני $3$ יחידות מהסוג השני (בוחרים למכור את $3$ היחידות שיתקלקלו בסוף היום השני), וביום השלישי $2$ יחידות מהסוג השני.
במקרה זה, ההכנסה ממכירת הסוג הראשון היא $3\times3+3$, וההכנסה ממכירת הסוג השני היא $(3+2)\times2+5$. ההכנסה הכוללת היא $(3\times3+3)+[(3+2)\times2+5]=27$.
תתי־משימות
| מספר הבדיקה | $n$ | $m$ | $p_j$ | תכונה 1 | תכונה 2 |
|---|---|---|---|---|---|
| $1$ | $\le2$ | $\le10$ | $\le1000$ | לא | לא |
| $2$ | $\le3$ | $\le10$ | $\le1000$ | לא | לא |
| $3$ | $\le4$ | $\le10$ | $\le1000$ | לא | לא |
| $4$ | $\le1000$ | $\le10$ | $\le2$ | לא | לא |
| $5$ | $\le1000$ | $\le10$ | $\le3$ | לא | לא |
| $6$ | $\le1000$ | $\le10$ | $\le4$ | לא | לא |
| $7$ | $\le4$ | $\le1$ | $\le4$ | לא | לא |
| $8$ | $\le6$ | $\le2$ | $\le6$ | לא | לא |
| $9$ | $\le8$ | $\le1$ | $\le8$ | לא | לא |
| $10$ | $\le10$ | $\le2$ | $\le10$ | לא | לא |
| $11$ | $\le20$ | $\le3$ | $\le20$ | לא | לא |
| $12$ | $\le100$ | $\le10$ | $\le100$ | כן | לא |
| $13$ | $\le100$ | $\le10$ | $\le100$ | לא | כן |
| $14$ | $\le100$ | $\le10$ | $\le100$ | לא | לא |
| $15$ | $\le100$ | $\le10$ | $\le100$ | לא | לא |
| $16$ | $\le1000$ | $\le10$ | $\le1000$ | כן | כן |
| $17$ | $\le1000$ | $\le10$ | $\le1000$ | כן | לא |
| $18$ | $\le1000$ | $\le10$ | $\le1000$ | לא | כן |
| $19$ | $\le1000$ | $\le10$ | $\le1000$ | לא | לא |
| $20$ | $\le1000$ | $\le10$ | $\le1000$ | לא | לא |
| $21$ | $\le100000$ | $\le10$ | $\le100000$ | כן | כן |
| $22$ | $\le100000$ | $\le10$ | $\le100000$ | כן | לא |
| $23$ | $\le100000$ | $\le10$ | $\le100000$ | לא | כן |
| $24$ | $\le100000$ | $\le10$ | $\le100000$ | לא | לא |
| $25$ | $\le100000$ | $\le10$ | $\le100000$ | לא | לא |
תכונה 1: כל ערכי $s_i$ הם $0$.
תכונה 2: כל ערכי $x_i$ הם $0$.
לכל נתוני הבדיקה מובטח שערכי $p_j$ ב־$k$ השאילתות שונים זה מזה.
לכל נתוני הבדיקה מובטח $0<a_i,c_i\le10^9$, $0\le s_i,x_i\le10^9$.