小 N 是蔬菜倉庫的管理員，負責設計蔬菜的銷售方案。
在蔬菜倉庫中，共存放有 $n$ 種蔬菜，小 N 需要根據不同蔬菜的特性，綜合考慮各方面因素，設計合理的銷售方案，以獲得最多的收益。
在計算銷售蔬菜的收益時，每銷售一個單位第 $i$ 種蔬菜，就可以獲得 $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$ 時，意味著這種蔬菜不會變質。
同時，每天銷售的蔬菜總量也是有限的，最多不能超過 $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 種蔬菜時，每銷售一單位可以獲得的收益為 $2$，第一次銷售這種蔬菜時，額外可以獲得的收益為 $5$。這種蔬菜共有 8 個單位，其中，有 3 單位在第一天結束時變質，3 單位在第二天結束時變質，2 單位在第三天結束時變質。
在只銷售 1 天時，應當銷售 2 單位的第一種蔬菜和 1 單位的第二種蔬菜。
在這種情況下：銷售第一種蔬菜的收益為 $2\times 3+3$；銷售第二種蔬菜的收益為 $1\times 2+5$；總共獲得的收益為 $(2\times 3+3)+(1\times 2+5)=16$。
在只銷售 3 天時，第一天應當銷售 3 單位的第一種蔬菜，第二天應當銷售 3 單位的第二種蔬菜（此時選擇在第二天結束時會變質的 3 個單位出售），第三天銷售 2 單位的第二種蔬菜。
在這種情況下：銷售第一種蔬菜的收益為 $3\times 3+3$；銷售第二種蔬菜的收益為 $(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$。