P1070晨汐散余香Ⅱ（scent）

【题目背景】

晨汐港的第一批香料已经完成交易，Gioush 大队也换得了一部分出海所需的补给。就在船队准备离港时，港口商会又送来一批数量更多、失香时间各不相同的香料，tfbz 决定在剩余的日子里继续交易，补足远航仍然欠缺的金币。

【题目描述】

晨汐港接下来共有若干个可供交易的日子。Gioush 大队带来了 $n$ 种香料，第 $i$ 种香料共有 $c_i$ 个单位，其中每个单位能够换得 $a_i$ 枚金币。第一次售出第 $i$ 种香料时，还会额外获得 $s_i$ 枚金币，这笔额外收益称为这种香料的初售赏金。无论之后又售出多少个单位，都不会再次获得同一种香料的初售赏金。

对于第 $i$ 种香料，若 $x_i>0$，则在交易开始前将它的 $c_i$ 个单位依次分成若干批。除最后一批外，每批都恰好包含 $x_i$ 个单位，最后一批包含的单位不超过 $x_i$ 个。第一批会在第 $1$ 天结束时失去香气，第二批会在第 $2$ 天结束时失去香气，其余各批依此类推。每个单位所属的批次在交易开始前便已经确定，不会因为其他单位被售出而改变。在某一天结束时失去香气的单位，仍然可以在这一天完成交易。若 $x_i=0$，则这种香料的所有单位都不会失去香气。

晨汐港每天至多允许 Gioush 大队交易 $m$ 个单位的香料。同一天内交易的香料种类可以相同，也可以不同。一份香料一旦被卖出便不能再次交易，在失去香气前没有卖出的香料也不能带来任何收益。

对于一次询问，tfbz 可以在第 $1$ 天至第 $p_j$ 天内安排交易。把选出的香料分别安排到一个不晚于其失香时间的交易日，并保证同一天至多交易 $m$ 个单位，称为一个交易方案。若同一种香料至少有一个单位被卖出，那么这种香料的初售赏金会在总收益中计算一次。

tfbz 一共准备了 $q$ 次询问。每次询问都相互独立，所有香料都会恢复到交易开始前的完整库存，失香时间也会重新从第 $1$ 天开始计算。特别地，当 $p_j=0$ 时，本次询问不会进行交易。

对于每次询问，请你求出所有合法的交易方案中，Gioush 大队最多能够获得多少枚金币。

【输入格式】

从文件 $\textbf{\textit{scent.in}}$ 中读入数据。

本题包含多组测试数据。

输入的第一行包含一个非负整数 $c$ 与一个正整数 $T$，分别表示测试点编号与测试数据的组数。$c=0$ 表示该测试点为样例。

对于每组测试数据：

第一行包含三个正整数 $n,m,q$，分别表示香料种类数、每天能够售出的单位数上限与询问数量。

接下来 $n$ 行，每行包含四个整数 $a_i,s_i,c_i,x_i$，依次表示第 $i$ 种香料的基础收益、初售赏金、初始库存与每天失去香气的单位数。

接下来 $q$ 行，每行包含一个非负整数 $p_j$，表示一次询问的交易天数。

【输出格式】

输出到文件 $\textbf{\textit{scent.out}}$ 中。

对于每组测试数据输出 $q$ 行，第 $j$ 行一个整数，表示第 $j$ 次询问中所有合法的交易方案能够获得的最大金币数。

【样例 1 输入】

10 222 3 233 3 3 342 5 8 3516371 2 384 6 3 090101112

【样例 1 输出】

11622730414518

【说明/提示】

【样例 1 解释】

在第一组测试数据中，当交易持续 $3$ 天时，可以在第 $1$ 天卖出第一种香料的全部三个单位，并在之后两天卖出第二种香料的五个单位，共获得 $3\times3+3+5\times2+5=27$ 枚金币。当交易只持续 $1$ 天时，最优收益为 $16$ 枚金币。

在第二组测试数据中，交易持续 $0,1,2$ 天时的最优收益依次为 $0,14,18$ 枚金币。可以证明，不存在收益更高的交易方案。

【样例 2】

见选手目录下的 $\textbf{\textit{scent/scent2.in}}$ 和 $\textbf{\textit{scent/scent2.ans}}$。

该组样例符合测试点 $1\sim 4$ 的数据范围。

【样例 3】

见选手目录下的 $\textbf{\textit{scent/scent3.in}}$ 和 $\textbf{\textit{scent/scent3.ans}}$。

该组样例符合测试点 $5\sim 8$ 的数据范围。

【样例 4】

见选手目录下的 $\textbf{\textit{scent/scent4.in}}$ 和 $\textbf{\textit{scent/scent4.ans}}$。

该组样例符合测试点 $9\sim 12$ 的数据范围。

【样例 5】

见选手目录下的 $\textbf{\textit{scent/scent5.in}}$ 和 $\textbf{\textit{scent/scent5.ans}}$。

该组样例符合测试点 $13\sim 15$ 的数据范围。

【样例 6】

见选手目录下的 $\textbf{\textit{scent/scent6.in}}$ 和 $\textbf{\textit{scent/scent6.ans}}$。

该组样例符合测试点 $16\sim 19$ 的数据范围。

【样例 7】

见选手目录下的 $\textbf{\textit{scent/scent7.in}}$ 和 $\textbf{\textit{scent/scent7.ans}}$。

该组样例符合测试点 $20\sim 25$ 的数据范围。

【数据范围】

对于 $100\%$ 的数据，保证 $1\leq T\leq10$，$1\leq n,q\leq10^5$，单个测试点内 $\sum n,\sum q\leq10^5$，$1\leq m\leq10$，$0\leq p_j\leq10^5$，$0<a_i,c_i\leq10^9$，$0\leq s_i,x_i\leq10^9$。同一组测试数据中的 $p_j$ 互不相同。

表中的 $\sum c_i$ 指一个测试点内所有测试数据的库存数量之和。

特殊性质：保证所有 $x_i=0$。