### 问题描述 康康有 $n$ 种蔬菜，在计算销售蔬菜的收益时，每销售一个单位第 $i$ 种蔬菜，就可以获得 $a_i$ 的收益。 特别地，由于政策鼓励商家进行多样化销售，第一次销售第 $i$ 种蔬菜时，还会额外得到 $s_i$ 的额外收益。 在经营开始时，第 $i$ 种蔬菜的库存为 $c_i$ 个单位。然而，蔬菜的保鲜时间非常有限，一旦变质就不能进行销售，不过康康已经计算出了每个单位蔬菜变质的时间：对于第 $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$ 个单位。 现在康康有 $k$ 个问题，每个问题的形式都是：已知 $p_j$，如果需要销售 $p_j$ 天，最多能获得多少收益。 ### 输入格式 第一行包含三个正整数 $n, m, k$。 接下来 $n$ 行，每行输入四个非负整数，描述一种蔬菜的特点，依次为 $a_i, s_i, c_i, x_i$。 接下来 $k$ 行，每行输入一个非负整数 $p_j$。 ### 输出格式 输出 $k$ 行，每行包含一个整数，第 $i$ 行的数表示第 $i$ 个问题的答案。 ### 样例输入 ``` 2 3 2 3 3 3 3 2 5 8 3 1 3 ``` ### 样例输出 ``` 16 27 ``` ### 评测数据规模 $1 \leq n \leq 1000$，$1 \leq m \leq 10$，$1 \leq k \leq 10^5$，$1 \leq p_j \leq 10^5$，$1 \leq a_i, c_i, s_i, x_i \leq 10^9$。