Mock CCC '20 Contest 2 S5 - Sticks

View as PDF

Submit solution

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

Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

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 sum of the length of the sticks do 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.


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
6 5

Sample Output



There are no comments at the moment.