Background

To account for the efficiency of the Python language, the time limit for this problem is relatively large. It is recommended to use PyPy3 to submit this problem.

Problem Description

A steel factory has a train used to transport scrap steel. It has two carriages: carriage 1 has a maximum load of $A$, and carriage 2 has a maximum load of $B$. There are $N$ pieces of scrap steel to be transported, and the weight of the $i$-th piece is $w_i$. To maximize transportation efficiency, the conductor wants to transport as much total weight as possible in a single trip. Please help the conductor compute the maximum total weight of scrap steel that can be carried in one trip.

Each piece of steel is independent and indivisible, and can only be placed into one of the carriages. When loading the steel, you only need to consider the weight constraints.

Input Format

The first line contains three integers $N, A, B$, separated by a single space, representing the number of steel pieces and the maximum loads of the two carriages.

The second line contains $N$ integers, representing $w_1, w_2, \cdots, w_n$, with a single space between adjacent integers.

Output Format

Output one integer representing the answer.

3 10 8
8 9 1

18

Hint

For $30\%$ of the test cases, $1 \le N \le 10$.

For all test cases, $1 \le N \le 200$, and $1 \le w_i, A, B \le 1000$.

Sample Explanation

Carriage 1 loads the 2nd and 3rd pieces of steel, and carriage 2 loads the 1st piece of steel.

Translated by ChatGPT 5