Maximum Steel Transport

A steel factory has a train with two compartments used to transport scrap steel. The first compartment has a maximum capacity of \(A\) and the second has a maximum capacity of \(B\). There are \(N\) pieces of scrap steel, where the \(i\)-th piece weighs \(w_i\). Each piece is indivisible and must be loaded entirely into either compartment. To maximize transport efficiency, determine the maximum total weight of steel that can be transported in one go without exceeding the capacities of the two compartments.

The input guarantees that all weights are positive integers. Formally, you are given capacities \(A, B\) and a list of weights \(w_1, w_2, \ldots, w_N\). Find a subset of these pieces together with a partition into two groups such that the sum of weights in the first group is at most \(A\) and in the second group is at most \(B\), and the total transported weight is maximized.

Note: A solution using dynamic programming is suggested, where a boolean DP state is maintained for each possible combination of loaded weights in the two compartments.

inputFormat

The first line contains three integers \(A\), \(B\), and \(N\) representing the capacities of compartment 1, compartment 2, and the number of steel pieces respectively.

The second line contains \(N\) integers \(w_1, w_2, \ldots, w_N\), where \(w_i\) is the weight of the \(i\)-th piece.

outputFormat

Print a single integer representing the maximum total weight that can be transported.

sample

10 10 3
5 5 10

20