Vacuum Tubes
Time limit1sMemory limit256 MB
Choose two disjoint tube pairs that fit within lengths L1 and L2 so the combined length is as large as possible.
- Level
Medium6 of 10
- Topics
- Sorting, Two pointers, Brute force
- Solved
- No attempts yet
Problem
An X-ray lab keeps evacuated tubes between the source and the sample, and between the sample and the detector, so that the air does not absorb the X-rays. The sample and the detector sit at different places in different experiments, so tubes of several lengths are kept ready. A tube has a vacuum window at one end only, so two tubes are fixed together into a pair. One pair goes between the source and the sample, the other pair goes between the sample and the detector. Longer tubes leave less air, but the space between the source and the sample is mm and the space between the sample and the detector is mm.
You are given the tube lengths and the two distances and . Choose four tubes so that the sum of the first two lengths is at most , the sum of the last two lengths is at most , and the total length of the four tubes is as large as possible. Each tube can be used at most once.
Input
The first line contains three integers , and separated by spaces. and are the two distances described above, in mm (). is the number of available tubes ().
Each of the next lines contains the length of one tube in mm, an integer between 1 and 10000.
Output
Print the largest possible total length of the four chosen tubes on one line. If no two disjoint pairs fit into the two spaces, print Impossible instead.