Vegetables - MarisaOJ: Marisa Online Judge
You are managing a store selling vegetables and have to plan the sales. There are $n$ types of vegetables, and each unit of vegetable type $i$ sold will earn $a_i$. Furthermore, to enhance diversity, the first time selling vegetable type $i$ will receive an additional $s_i$.
On the first day, vegetable type $i$ has $c_i$ units. However, the freshness of vegetable type $i$ is $x_i$, meaning at the end of each day, $x_i$ units will wither. Moreover, each day, you cannot sell more than $m$ units of vegetables.
The director asks you $k$ questions. For the $j$-th question, a non-negative integer $p_j$ is asked, inquiring about the maximum profit if you have to sell for $p_j$ days.
### Input
- The first line consists of three integers $n, m, k$.
- The next $n$ lines, the $i$-th line contains four integers $a_i, s_i, c_i, x_i$.
- The next $k$ lines, the $j$-th line contains a non-negative integer $p_j$.
### Output
- Output $k$ lines, the $i$-th line is the answer to the $i$-th question.
### Example
Input:
```
2 3 2
3 3 3 3
2 5 8 3
1
3
```
Output:
```
16
27
```
Explanation:
- For the case of $1$ day: Buy $1$ unit of vegetable type $2$ and $2$ units of vegetable type $1$.
- For the case of $3$ days:
+ On the first day, buy $3$ units of vegetable type $1$, earning $12$. At the end of the day, there are still $5$ units of vegetable type $2$.
+ On the second day, buy $3$ units of vegetable type $2$, earning $11$. There should be $3$ units of vegetable type $2$ withering at the end of the day, but we sold them, leaving $2$ units of vegetable type $2$.
+ On the third day, sell the remaining $2$ units of vegetable type $2$, earning $4$, making the total $12 + 11 + 4 = 27$.
### Constraints
- Condition $1$: All $s_i$ values are $0$.
- Condition $2$: All $x_i$ values are $0$.
- Ensure distinct values for each $p_j$.
- $0 \le a_i, c_i, s_i, x_i \le 10^9$.
Test |
$n$ |
$m$ |
$p_j$ |
Condition $1$ |
Condition $2$ |
1 |
$\le 2$ |
$\leq 10$ |
$\leq 10^3$ |
No |
2 |
$\le 3$ |
3 |
$\le 4$ |
4 |
$\le 10^3$ |
$\le 2$ |
5 |
$\le 3$ |
6 |
$\le 4$ |
7 |
$\leq 4$ |
$\leq 1$ |
8 |
$\leq 6$ |
$\leq 2$ |
$\leq 6$ |
9 |
$\leq 8$ |
$\leq 1$ |
$\leq 8$ |
10 |
$\leq 10$ |
$\leq 2$ |
$\leq 10$ |
11 |
$\leq 20$ |
$\leq 3$ |
$\leq 20$ |
12 |
$\leq 10^2$ |
$\leq 10$ |
$\leq 10^2$ |
Yes |
No |
13 |
No |
Yes |
14 |
No |
15 |
16 |
$\leq 10^3$ |
$\leq 10^3$ |
Yes |
Yes |
17 |
No |
18 |
No |
Yes |
19 |
No |
20 |
21 |
$\leq 10^5$ |
$\leq 10^5$ |
Yes |
Yes |
22 |
No |
23 |
No |
Yes |
24 |
No |
25 |
Topic
Greedy
Rating
2400
Solution (0)
Solution