小 N は野菜倉庫の管理者で、野菜の販売計画を立てる仕事をしています。
倉庫には全部で $n$ 種類の野菜が保管されています。小 N はそれぞれの野菜の特性に応じて、さまざまな要因を総合的に考慮し、収益を最大にする適切な販売計画を立てる必要があります。
野菜販売の収益を計算する際、種類 $i$ の野菜を 1 単位売るごとに、収益 $a_i$ が得られます。
特に、多様な種類の販売を政策で奨励しているため、種類 $i$ の野菜を初めて売ったときには、さらに追加の収益 $s_i$ が得られます。
営業開始時における種類 $i$ の野菜の在庫は $c_i$ 単位です。
しかし、野菜の鮮度が保たれる時間には厳しい制限があり、腐ってしまうと販売できません。賢い小 N は、すでに各単位の野菜が腐る時刻を計算しました。種類 $i$ の野菜には鮮度の値 $x_i$ があり、毎日の終わりに $x_i$ 単位の野菜が腐り、すべての野菜が腐るまでこれが続きます。（注意：各単位の野菜が腐る時刻は固定されており、販売によって変わることはありません。）
形式的には、条件 $d\times x_i\le c_i$ を満たすすべての正整数 $d$ に対して、$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$ の場合は、この種類の野菜が腐らないことを意味する点に注意してください。
また、1 日に販売する野菜の総量にも制限があり、最大で $m$ 単位までです。
今、小 N にはあなたに計算を手伝ってほしい質問が $k$ 個あります。各質問は次の形式です。既知の $p_j$ に対して、$p_j$ 日間販売するとき、得られる収益の最大値はいくらですか？
入力
ファイル vegetables.in からデータを読み込みます。
最初の行には三つの正整数 $n,m,k$ が与えられます。それぞれ、野菜の種類数、1 日に販売できる野菜の総量の上限、小 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 種類目の野菜は、1 単位売るごとに収益 $3$ が得られ、初めてこの種類を売るときには追加で収益 $3$ が得られます。この野菜は全部で 3 単位あり、すべて 1 日目の終わりに腐ります。
2 種類目の野菜は、1 単位売るごとに収益 $2$ が得られ、初めてこの種類を売るときには追加で収益 $5$ が得られます。この野菜は全部で 8 単位あり、そのうち 3 単位が 1 日目の終わりに、3 単位が 2 日目の終わりに、2 単位が 3 日目の終わりに腐ります。
1 日間だけ販売する場合は、1 種類目の野菜を 2 単位、2 種類目の野菜を 1 単位販売すべきです。
この場合、1 種類目の野菜の販売収益は $2\times 3+3$、2 種類目の野菜の販売収益は $1\times 2+5$ であり、収益の合計は $(2\times 3+3)+(1\times 2+5)=16$ です。
3 日間だけ販売する場合は、1 日目に 1 種類目の野菜を 3 単位、2 日目に 2 種類目の野菜を 3 単位（このときは 2 日目の終わりに腐る 3 単位を選んで売ります）、3 日目に 2 種類目の野菜を 2 単位販売すべきです。
この場合、1 種類目の野菜の販売収益は $3\times 3+3$、2 種類目の野菜の販売収益は $(3+2)\times 2+5$ であり、収益の合計は $(3\times 3+3)+[(3+2)\times 2+5]=27$ です。
小課題
| テストケース番号 | $n$ | $m$ | $p_j$ | 特性 1 | 特性 2 |
|---|---|---|---|---|---|
| $1$ | $\le 2$ | $\le 10$ | $\le 10^3$ | なし | なし |
| $2$ | $\le 3$ | $\le 10$ | $\le 10^3$ | なし | なし |
| $3$ | $\le 4$ | $\le 10$ | $\le 10^3$ | なし | なし |
| $4$ | $\le 10^3$ | $\le 10$ | $\le 2$ | なし | なし |
| $5$ | $\le 10^3$ | $\le 10$ | $\le 3$ | なし | なし |
| $6$ | $\le 10^3$ | $\le 10$ | $\le 4$ | なし | なし |
| $7$ | $\le 4$ | $\le 1$ | $\le 4$ | なし | なし |
| $8$ | $\le 6$ | $\le 2$ | $\le 6$ | なし | なし |
| $9$ | $\le 8$ | $\le 1$ | $\le 8$ | なし | なし |
| $10$ | $\le 10$ | $\le 2$ | $\le 10$ | なし | なし |
| $11$ | $\le 20$ | $\le 3$ | $\le 20$ | なし | なし |
| $12$ | $\le 10^2$ | $\le 10$ | $\le 10^2$ | あり | なし |
| $13$ | $\le 10^2$ | $\le 10$ | $\le 10^2$ | なし | あり |
| $14$ | $\le 10^2$ | $\le 10$ | $\le 10^2$ | なし | なし |
| $15$ | $\le 10^2$ | $\le 10$ | $\le 10^2$ | なし | なし |
| $16$ | $\le 10^3$ | $\le 10$ | $\le 10^3$ | あり | あり |
| $17$ | $\le 10^3$ | $\le 10$ | $\le 10^3$ | あり | なし |
| $18$ | $\le 10^3$ | $\le 10$ | $\le 10^3$ | なし | あり |
| $19$ | $\le 10^3$ | $\le 10$ | $\le 10^3$ | なし | なし |
| $20$ | $\le 10^3$ | $\le 10$ | $\le 10^3$ | なし | なし |
| $21$ | $\le 10^5$ | $\le 10$ | $\le 10^5$ | あり | あり |
| $22$ | $\le 10^5$ | $\le 10$ | $\le 10^5$ | あり | なし |
| $23$ | $\le 10^5$ | $\le 10$ | $\le 10^5$ | なし | あり |
| $24$ | $\le 10^5$ | $\le 10$ | $\le 10^5$ | なし | なし |
| $25$ | $\le 10^5$ | $\le 10$ | $\le 10^5$ | なし | なし |
特性 1：すべての $s_i$ が $0$ です。
特性 2：すべての $x_i$ が $0$ です。
すべてのテストデータで、$k$ 個の質問における $p_j$ は互いに異なることが保証されます。
すべてのテストデータで、$0<a_i,c_i\le 10^9,0\le s_i,x_i\le 10^9$ が保証されます。