아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

진공 튜브

시간 제한1초메모리 제한256 MB

요약
각각 L1과 L2를 초과하지 않으면서 서로 겹치지 않는 튜브 두 쌍을 골라 전체 길이를 최대로 합니다.
난이도

보통10점 중 6점

유형
정렬, 투 포인터, 완전 탐색
정답자
아직 제출이 없습니다

문제

X선 실험실에서는 X선이 공기에 흡수되지 않도록 선원과 시료 사이, 그리고 시료와 검출기 사이를 진공 튜브로 채운다. 실험마다 시료와 검출기의 위치가 달라지므로 길이가 서로 다른 튜브를 여러 개 준비해 두었다. 튜브는 한쪽 끝에만 진공 창이 있어서 두 개를 맞붙여 한 쌍으로 쓴다. 한 쌍은 선원과 시료 사이에 넣고, 다른 한 쌍은 시료와 검출기 사이에 넣는다. 공기를 최대한 밀어내려면 튜브가 길수록 좋지만, 선원과 시료 사이의 공간은 L1L_1 mm, 시료와 검출기 사이의 공간은 L2L_2 mm로 정해져 있다.

튜브 길이 목록과 두 거리 L1L_1, L2L_2가 주어진다. 앞의 두 튜브의 길이 합이 L1L_1 이하이고 뒤의 두 튜브의 길이 합이 L2L_2 이하가 되도록 튜브 네 개를 고르고, 네 튜브의 길이 합을 최대로 하라. 튜브 하나는 최대 한 번만 쓸 수 있다.

입력

첫째 줄에 정수 L1L_1, L2L_2, NN이 공백으로 구분되어 주어진다. L1L_1과 L2L_2는 위에서 설명한 두 공간의 길이이고 단위는 mm이다 (1≤L1,L2≤100001 \le L_1, L_2 \le 10000). NN은 준비된 튜브의 개수다 (4≤N≤20004 \le N \le 2000).

다음 NN개 줄에는 각각 튜브 하나의 길이가 mm 단위 정수로 주어진다. 길이는 1 이상 10000 이하다.

출력

고른 튜브 네 개의 길이 합의 최댓값을 한 줄에 출력한다. 두 공간에 각각 들어가는, 서로 겹치지 않는 두 쌍을 만들 수 없으면 대신 Impossible을 출력한다.

예제2

  1. 예제 1

    입력
    1000 2000 7
    100
    480
    500
    550
    1000
    1400
    1500
    
    예상 출력
    2930
    
  2. 예제 2

    입력
    200 300 6
    100
    100
    200
    200
    300
    300
    
    예상 출력
    Impossible