小 N verwaltet ein Gemüselager und ist für die Planung des Gemüseverkaufs verantwortlich.
Im Gemüselager werden insgesamt $n$ Gemüsesorten gelagert. 小 N muss anhand ihrer unterschiedlichen Eigenschaften unter Berücksichtigung aller Faktoren einen sinnvollen Verkaufsplan entwerfen, um möglichst hohe Einnahmen zu erzielen.
Beim Verkauf einer Einheit der $i$-ten Gemüsesorte erzielt man Einnahmen von $a_i$.
Da die Politik einen vielfältigen Verkauf fördert, erhält man beim ersten Verkauf der $i$-ten Gemüsesorte zusätzlich Einnahmen von $s_i$.
Zu Geschäftsbeginn beträgt der Bestand der $i$-ten Gemüsesorte $c_i$ Einheiten.
Die Haltbarkeit von Gemüse ist jedoch sehr begrenzt. Sobald es verdorben ist, kann es nicht mehr verkauft werden. Der schlaue 小 N hat bereits berechnet, wann jede einzelne Einheit verdirbt: Für die $i$-te Gemüsesorte gibt es einen Haltbarkeitswert $x_i$. Am Ende jedes Tages verderben $x_i$ Einheiten, bis alle Einheiten verdorben sind. (Beachte: Der Zeitpunkt, zu dem eine einzelne Einheit verdirbt, ist fest und ändert sich durch Verkäufe nicht.)
Formal gilt: Für jede positive ganze Zahl $d$ mit $d \times x_i \le c_i$ verderben $x_i$ Einheiten am Ende des $d$-ten Tages.
Insbesondere verderben im Fall $(d-1)\times x_i\le c_i<d\times x_i$ genau $c_i-(d-1)\times x_i$ Einheiten am Ende des $d$-ten Tages.
Beachte, dass $x_i=0$ bedeutet, dass diese Gemüsesorte nicht verdirbt.
Zugleich ist die Gesamtmenge des täglich verkauften Gemüses begrenzt: Sie darf höchstens $m$ Einheiten betragen.
Nun hat 小 N insgesamt $k$ Fragen, bei deren Berechnung du helfen sollst. Jede Frage lautet: Wie hoch sind für ein gegebenes $p_j$ die maximal möglichen Einnahmen, wenn $p_j$ Tage lang verkauft werden soll?
Eingabe
Lies die Daten aus der Datei vegetables.in.
Die erste Zeile enthält drei positive ganze Zahlen $n,m,k$: die Anzahl der Gemüsesorten, die Obergrenze der täglich verkaufbaren Gesamtmenge und die Anzahl der Fragen von 小 N.
Die folgenden $n$ Zeilen enthalten jeweils vier nichtnegative ganze Zahlen, die eine Gemüsesorte beschreiben: in dieser Reihenfolge $a_i,s_i,c_i,x_i$, mit der oben angegebenen Bedeutung.
Die folgenden $k$ Zeilen enthalten jeweils eine nichtnegative ganze Zahl $p_j$ mit der oben angegebenen Bedeutung.
Ausgabe
Schreibe die Ausgabe in die Datei vegetables.out.
Gib $k$ Zeilen mit jeweils einer ganzen Zahl aus. Die Zahl in der $i$-ten Zeile ist die Antwort auf die $i$-te Frage.
Beispiele
Eingabe 1
2 3 2 3 3 3 3 2 5 8 3 1 3
Ausgabe 1
16 27
Beispiel 2
Siehe vegetables/vegetables2.in und vegetables/vegetables2.ans im Teilnehmerverzeichnis.
Beispiel 3
Siehe vegetables/vegetables3.in und vegetables/vegetables3.ans im Teilnehmerverzeichnis.
Hinweis zu Beispiel 1
Es gibt zwei Gemüsesorten:
Beim Verkauf der ersten Sorte erhält man pro Einheit Einnahmen von $3$ und beim ersten Verkauf zusätzlich $3$. Es gibt insgesamt $3$ Einheiten dieser Sorte; sie verderben alle am Ende des ersten Tages.
Beim Verkauf der zweiten Sorte erhält man pro Einheit Einnahmen von $2$ und beim ersten Verkauf zusätzlich $5$. Es gibt insgesamt $8$ Einheiten dieser Sorte: $3$ verderben am Ende des ersten Tages, $3$ am Ende des zweiten Tages und $2$ am Ende des dritten Tages.
Wenn nur einen Tag lang verkauft wird, sollte man $2$ Einheiten der ersten und $1$ Einheit der zweiten Sorte verkaufen.
Dabei betragen die Einnahmen aus der ersten Sorte $2\times3+3$, aus der zweiten Sorte $1\times2+5$ und insgesamt $(2\times3+3)+(1\times2+5)=16$.
Wenn nur drei Tage lang verkauft wird, sollte man am ersten Tag $3$ Einheiten der ersten Sorte, am zweiten Tag $3$ Einheiten der zweiten Sorte (dabei wählt man die $3$ Einheiten, die am Ende des zweiten Tages verderben) und am dritten Tag $2$ Einheiten der zweiten Sorte verkaufen.
Dabei betragen die Einnahmen aus der ersten Sorte $3\times3+3$, aus der zweiten Sorte $(3+2)\times2+5$ und insgesamt $(3\times3+3)+[(3+2)\times2+5]=27$.
Teilaufgaben
| Testfallnummer | $n$ | $m$ | $p_j$ | Eigenschaft 1 | Eigenschaft 2 |
|---|---|---|---|---|---|
| 1 | $\le2$ | $\le10$ | $\le10^3$ | Nein | Nein |
| 2 | $\le3$ | $\le10$ | $\le10^3$ | Nein | Nein |
| 3 | $\le4$ | $\le10$ | $\le10^3$ | Nein | Nein |
| 4 | $\le10^3$ | $\le10$ | $\le2$ | Nein | Nein |
| 5 | $\le10^3$ | $\le10$ | $\le3$ | Nein | Nein |
| 6 | $\le10^3$ | $\le10$ | $\le4$ | Nein | Nein |
| 7 | $\le4$ | $\le1$ | $\le4$ | Nein | Nein |
| 8 | $\le6$ | $\le2$ | $\le6$ | Nein | Nein |
| 9 | $\le8$ | $\le1$ | $\le8$ | Nein | Nein |
| 10 | $\le10$ | $\le2$ | $\le10$ | Nein | Nein |
| 11 | $\le20$ | $\le3$ | $\le20$ | Nein | Nein |
| 12 | $\le10^2$ | $\le10$ | $\le10^2$ | Ja | Nein |
| 13 | $\le10^2$ | $\le10$ | $\le10^2$ | Nein | Ja |
| 14 | $\le10^2$ | $\le10$ | $\le10^2$ | Nein | Nein |
| 15 | $\le10^2$ | $\le10$ | $\le10^2$ | Nein | Nein |
| 16 | $\le10^3$ | $\le10$ | $\le10^3$ | Ja | Ja |
| 17 | $\le10^3$ | $\le10$ | $\le10^3$ | Ja | Nein |
| 18 | $\le10^3$ | $\le10$ | $\le10^3$ | Nein | Ja |
| 19 | $\le10^3$ | $\le10$ | $\le10^3$ | Nein | Nein |
| 20 | $\le10^3$ | $\le10$ | $\le10^3$ | Nein | Nein |
| 21 | $\le10^5$ | $\le10$ | $\le10^5$ | Ja | Ja |
| 22 | $\le10^5$ | $\le10$ | $\le10^5$ | Ja | Nein |
| 23 | $\le10^5$ | $\le10$ | $\le10^5$ | Nein | Ja |
| 24 | $\le10^5$ | $\le10$ | $\le10^5$ | Nein | Nein |
| 25 | $\le10^5$ | $\le10$ | $\le10^5$ | Nein | Nein |
Eigenschaft 1: Alle $s_i$ sind $0$.
Eigenschaft 2: Alle $x_i$ sind $0$.
Für alle Testdaten ist garantiert, dass die $p_j$ der $k$ Fragen paarweise verschieden sind.
Für alle Testdaten gilt garantiert $0<a_i,c_i\le10^9$ und $0\le s_i,x_i\le10^9$.