|시간 제한||메모리 제한||제출||정답||맞힌 사람||정답 비율|
|1 초||256 MB||26||12||11||45.833%|
In the X-ray lab at KTH some experiments require evacuated tubes between source and sample and between sample and detector so that the X-rays are not absorbed by the air. Since the positions of object and detector vary between different experiments, several tubes of different lengths are available. The tubes should be fixed together in pairs, since they have a vacuum window only in one end. Two such tube pairs should be chosen, one to place between the source and the object and one to place between the object and the detector. This, however, gives a large set of possible lengths and makes it difficult to figure out which tubes to use for an experiment. The length of the tubes used should be as long as possible to minimize air absorption, but there is a limited amount of space between source and object L1 and between object and detector L2. What is the maximum length of air that can be replaced by vacuum tubes in this way?
Given a set of tube lengths and the two distances L1 and L2, 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 L1 and the sum of the last two tube lengths is at most L2.
The first line of input contains three positive integers, L1 and L2, denoting the distances explained above in mm (1 ≤ L1, L2 ≤ 10 000) and N, the number of available tubes (4 ≤ N ≤ 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 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.
1000 2000 7 100 480 500 550 1000 1400 1500
200 300 6 100 100 200 200 300 300
Contest > KTH Challenge > KTH Challenge 2013 C번