Maximizing Vegetable Sales Profit

You are given a vegetable warehouse containing n types of vegetables. For each vegetable of type i (1 ≤ i ≤ n):

• Selling each unit yields a profit of \(a_i\).
• If you sell at least one unit of type \(i\), you get an extra bonus \(s_i\) (only once).
• You have an initial stock of \(c_i\) units.
• Each vegetable type has a spoilage parameter \(x_i\). At the end of day \(d\), exactly \(x_i\) units spoil for every positive integer \(d\) for which \(d \times x_i \le c_i\), and if \((d-1)\times x_i \le c_i < d\times x_i\), then the remaining \(c_i - (d-1)x_i\) units spoil at the end of day \(d\). When \(x_i = 0\), the vegetable does not spoil.

Each day you can sell at most m units (across all vegetables). Before the day ends, you may sell any number of units; unsold units scheduled to spoil at the end of the day will be lost permanently. Note that selling a unit prevents it from perishing.

You are given k queries. For each query with a given \(p_j\) (number of sale days), determine the maximum total profit you can achieve by scheduling your sales over \(p_j\) days optimally.

Important: For each vegetable i, if \(x_i > 0\) then even with optimal sales scheduling, you cannot sell more than \(p_j \times x_i\) units (or the available \(c_i\), whichever is smaller). If \(x_i = 0\), you may sell up to \(c_i\) units. Moreover, if you sell at least one unit of vegetable type i, you receive an extra bonus \(s_i\) in addition to the per‐unit profits \(a_i\).

You need to plan the sales across all vegetables such that the sum of sold units does not exceed the overall sale capacity, which is \(p_j \times m\) over \(p_j\) days. Each vegetable type is independent in that you choose a sale quantity between 0 and its maximum sellable units (taking spoilage into account), and profit from that type is \(a_i \times (\text{sold units})\) plus an extra \(s_i\) if at least one unit is sold. Your goal is to maximize the total profit.

Input and output formats are described below.

inputFormat

The first line contains three integers: n, m, and k — the number of vegetable types, the maximum number of units that can be sold per day, and the number of queries, respectively.

Then follow n lines, each containing four integers: \(a_i\), \(s_i\), \(c_i\), and \(x_i\) for \(i = 1, 2, \dots, n\).

Then follow k lines, each containing one integer \(p_j\) representing the number of sale days for that query.

\(1 \le i \le n,\) and all numbers are non-negative integers. For \(x_i=0\) the vegetable does not spoil.

outputFormat

For each query, print a single line containing one integer — the maximum total profit that can be obtained over the given number of days.

sample

2 5 3
2 5 10 3
3 4 5 0
1
2
3

23
34
42