Problem H
Vacuum Tubes
Task
Given a set of tube lengths and the two distances $L_1$ and $L_2$, find four tubes with the total length being as long as possible under the constraint that the sum of the first two tube lengths is at most $L_1$ and the sum of the last two tube lengths is at most $L_2$.
Input
The first line of input contains three positive integers, $L_1$ and $L_2$, denoting the distances explained above in mm ($1 \leq L_1, L_2 \leq 10\, 000$) and $N$, the number of available tubes ($4 \leq N \leq 2\, 000$). The following $N$ lines each contain a single positive integer less than or equal to $10\, 000$, the length of a tube in mm.
Output
Output one line containing the maximum total length of air that can be avoided, i.e., the sum of the four tubes chosen. If there are no two pairs of tubes fitting into the setup, output the single word “Impossible” instead.
Sample Input 1 | Sample Output 1 |
---|---|
1000 2000 7 100 480 500 550 1000 1400 1500 |
2930 |
Sample Input 2 | Sample Output 2 |
---|---|
200 300 6 100 100 200 200 300 300 |
Impossible |