Vegetables - MarisaOJ: Marisa Online Judge

You are managing a store selling vegetables and have to plan the sales. There are

n

$n$ types of vegetables, and each unit of vegetable type

i

$i$ sold will earn

a_{i}

$a_i$ . Furthermore, to enhance diversity, the first time selling vegetable type

i

$i$ will receive an additional

s_{i}

$s_i$ . On the first day, vegetable type

i

$i$ has

c_{i}

$c_i$ units. However, the freshness of vegetable type

i

$i$ is

x_{i}

$x_i$ , meaning at the end of each day,

x_{i}

$x_i$ units will wither. Moreover, each day, you cannot sell more than

m

$m$ units of vegetables. The director asks you

k

$k$ questions. For the

j

$j$ -th question, a non-negative integer

p_{j}

$p_j$ is asked, inquiring about the maximum profit if you have to sell for

p_{j}

$p_j$ days. ### Input - The first line consists of three integers

n, m, k

$n, m, k$ . - The next

n

$n$ lines, the

i

$i$ -th line contains four integers

a_{i}, s_{i}, c_{i}, x_{i}

$a_i, s_i, c_i, x_i$ . - The next

k

$k$ lines, the

j

$j$ -th line contains a non-negative integer

p_{j}

$p_j$ . ### Output - Output

k

$k$ lines, the

i

$i$ -th line is the answer to the

i

$i$ -th question. ### Example Input:

2323333258313

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

Output:

1627

$16 27$

Explanation: - For the case of

1

$1$ day: Buy

1

$1$ unit of vegetable type

2

$2$ and

2

$2$ units of vegetable type

1

$1$ . - For the case of

3

$3$ days: + On the first day, buy

3

$3$ units of vegetable type

1

$1$ , earning

12

$12$ . At the end of the day, there are still

5

$5$ units of vegetable type

2

$2$ . + On the second day, buy

3

$3$ units of vegetable type

2

$2$ , earning

11

$11$ . There should be

3

$3$ units of vegetable type

2

$2$ withering at the end of the day, but we sold them, leaving

2

$2$ units of vegetable type

2

$2$ . + On the third day, sell the remaining

2

$2$ units of vegetable type

2

$2$ , earning

4

$4$ , making the total

12 + 11 + 4 = 27

$12 + 11 + 4 = 27$ . ### Constraints - Condition

1

$1$ : All

s_{i}

$s_i$ values are

0

$0$ . - Condition

2

$2$ : All

x_{i}

$x_i$ values are

0

$0$ . - Ensure distinct values for each

p_{j}

$p_j$ . -

0 \leq a_{i}, c_{i}, s_{i}, x_{i} \leq 10^{9}

$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$	$\le 4$
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					No
16	$\leq 10^3$		$\leq 10^3$	Yes	Yes
17				Yes	No
18				No	Yes
19					No
20					No
21	$\leq 10^5$		$\leq 10^5$	Yes	Yes
22				Yes	No
23				No	Yes
24					No
25					No

(China) National Olympiad in Informatics 2017
	Earthworms queue
	Game
	Integer
	Vegetables
	Pool

Topic

Greedy

Rating

2400

Solution (0)

Solution