Task C2641 - Bargain

Bargain

C2641 Time Limit: 1.000 s Memory Limit: 256 MB

Submit Submissions

Problem

Alice is going to a supermarket to buy snacks. She has $W$ dollars and plans to buy $N$ types of snacks, the $i^{th}$ type of snack costs $A_i$ per pack.

She can buy multiple packs of snacks of the same type, but she must buy at least $1$ pack per type as her friends have different preferences.

Besides, the supermarket has two promotions:

During February and December, the price of all snacks reduces by 5 dollars. It’s guaranteed that the price of the snacks will always be positive.
Alice can choose at most $P$ packs of snacks that she has bought, and take them away for free. Note that if $P = 0$, the promotion is inactive.

Alice wants to buy as many packs of snacks as possible. Your task is to determine the maximum total number of packs of snacks that she can buy within the budget.

Don’t forget to make good use of the promotions! You may refer to the examples for further understanding.

Input

The first line contains three integers $N$, $W$ and $P$.

The second line contains $N$ integers $A_1 \dots A_N$, denoting the prices of the snacks.

The third line contains a string $S$, denoting the month of the year.

Output

If it‘s impossible to buy at least $1$ pack of each type of snack, output -1.

Otherwise, output a single integer, denoting the maximum total number of packs of snacks that Alice can buy within the budget.

Hints

Remember to use long long int instead of int as $W, P$ might be as large as $10^{18}$.

Subtasks

For all test cases, $1 \le N \le 10^6, 0 \le W, P \le 10^{18}, 10 \le A_i \le 10^9$ for $1 \le i \le N$ and $S$ is one of the months of the year.

Subtask	Score	Additional Constraints
$1$	$20$	$N = 1$ $P = 0$ $S \neq$ `February` and `December`
$2$	$11$	$N = 1$ $P = 0$
$3$	$16$	$N = 1$
$4$	$25$	$P = 0$
$5$	$28$	No Additional Constraints

Sample Test Cases

Input	Output
5 58 2 16 14 14 998 999 January	6
There are $5$ types of snacks. We can buy $1$ pack per type and buy $1$ more pack of the second type, a total of $6$ packs. The total cost is $16+14 \times 2+14+998+999=2055$ dollars. It's now over the budget. But don't forget $P=2$, so we choose the last two packs and take them away for free. The total cost now reduces to $2055-998-999=58$ dollars, which is just within the budget. It can be shown that $6$ packs is the maximum answer.

Input

Output

5 58 2
16 14 14 998 999
January

There are $5$ types of snacks. We can buy $1$ pack per type and buy $1$ more pack of the second type, a total of $6$ packs.

The total cost is $16+14 \times 2+14+998+999=2055$ dollars. It's now over the budget.

But don't forget $P=2$, so we choose the last two packs and take them away for free. The total cost now reduces to $2055-998-999=58$ dollars, which is just within the budget.

It can be shown that $6$ packs is the maximum answer.

Click to copy.

Scoring: Per Subtask
Authored by s22f26
Appeared in 2026 Mini Comp 4