[NOI2017] 蔬菜

题目描述

小 N 是蔬菜仓库的管理员,负责设计蔬菜的销售方案。 在蔬菜仓库中,共存放有 $n$ 种蔬菜,小 N 需要根据不同蔬菜的特性,综合考虑各方面因素,设计合理的销售方案,以获得最多的收益。 在计算销售蔬菜的收益时,每销售一个单位第 $i$ 种蔬菜,就可以获得 $a_i$ 的收益。 特别地,由于政策鼓励商家进行多样化销售,第一次销售第 $i$ 种蔬菜时,还会额外得到 $s_i$ 的额外收益。 在经营开始时,第 $i$ 种蔬菜的库存为 $c_i$ 个单位。 然而,蔬菜的保鲜时间非常有限,一旦变质就不能进行销售,不过聪明的小 N 已 经计算出了每个单位蔬菜变质的时间:对于第 $i$ 种蔬菜,存在保鲜值 $x_i$,每天结束时会 有 $x_i$ 个单位的蔬菜变质,直到所有蔬菜都变质。(注意:每一单位蔬菜的变质时间是固定的,不随销售发生变化) 形式化地:对于所有的满足条件 $d\times x_i \leq c_i$ 的正整数 $d$ ,有 $x_i$ 个单位的蔬菜将在 第 $d$ 天结束时变质。 特别地,若 $(d - 1)\times x_i \leq c_i < d\times x_i$ ,则有 $c_i - (d - 1)\times x_i$ 单位的蔬菜将在第 $d$ 天结束时变质。 注意,当 $x_i = 0$ 时,意味着这种蔬菜不会变质。 同时,每天销售的蔬菜,总量也是有限的,最多不能超过 $m$ 个单位。 现在,小 N 有 $k$ 个问题,想请你帮忙算一算。每个问题的形式都是:对于已知的 $p_j$,如果需要销售 $p_j$ 天,最多能获得多少收益?

输入输出格式

输入格式


第一行包含三个正整数 $n,m,k$,分别表示蔬菜的种类数目、每天能售出蔬菜总量上限、小 N 提出的问题的个数。 接下来 $n$ 行,每行输入四个非负整数,描述一种蔬菜的特点,依次为 $a_i,s_i,c_i,x_i$ , 意义如上文所述。 接下来 $k$ 行,每行输入一个非负整数 $p_j$ ,意义如上文所述。

输出格式


输出 $k$ 行,每行包含一个整数,第 $i$ 行的数表示第 $i$ 个问题的答案。

输入输出样例

输入样例 #1

2 3 2
3 3 3 3
2 5 8 3
1
3

输出样例 #1

16
27

说明

### 样例解释 共有两种蔬菜: 销售第 $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$。