Mock CCC '20 Contest 2 S5 - Sticks

View as PDF

Submit solution

Points: 20 (partial)
Time limit: 0.5s
Memory limit: 128M

Authors:
Problem type

You have A sticks each of length a metres and B sticks each of length b metres which you are trying to place into one of M tubes. Tube i has a length of l_i metres. Each tube can fit some number of sticks such that the sum of the length of the sticks does not exceed l_i. Each stick can also only go in at most one tube. What is the maximum number of sticks that can be put into the tubes?

Input Specification

The first line will contain two integers, a, A (1 \le a \le 10^9, 0 \le A).
The second line will contain two integers, b, B (1 \le b \le 10^9, 0 \le B).
We will guarantee a \le b and 0 \le A+B \le 10^5.

The third line will contain the integer M (1 \le M \le 10^5).
The fourth line will contain M integers, l_i (1 \le l_i \le 10^9).

Output Specification

Output the maximum number of sticks that can be put into the tubes.

Subtasks

For 2/15 of the points, M, A+B \le 10, a, b, l_i \le 1000.

For an additional 7/15 of the points, M, A+B, a, b, l_i \le 1000.

Sample Input

3 2
4 2
2
6 5

Sample Output

3

Comments

There are no comments at the moment.