#P50438. 「NOI2017」蔬菜

「NOI2017」蔬菜

题目描述

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

输入格式

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

输出格式

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

样例

2 3 2
3 3 3 3
2 5 8 3
1
3
16
27

数据范围与提示

测试点编号 nn mm pjp_j 特性 11 特性 22
11 2\le 2 10\le 10 103\le 10^3
22 3\le 3
33 4\le 4
44 103\le 10^3 2\le 2
55 3\le 3
66 4\le 4
77 4\le 4 1\le 1
88 6\le 6 2\le 2 6\le 6
99 8\le 8 1\le 1 8\le 8
1010 10\le 10 2\le 2 10\le 10
1111 20\le 20 3\le 3 20\le 20
1212 102\le 10^2 10\le 10 102\le 10^2
1313
1414
1515
1616 103\le 10^3 103\le 10^3
1717
1818
1919
2020
2121 105\le 10^5 105\le 10^5
2222
2323
2424
2525

特性 11:所有的 sis_i 均为 00

特性 22:所有的 xix_i 均为 00

对于所有的测试数据,均保证 kk 组询问中的 pjp_j 互不相同。

对于所有的测试数据,均保证 0<ai,ci109,0si,xi1090<a_i,c_i\le 10^9,0\le s_i,x_i\le 10^9