철인 N종 경기

문제 정보

    • 문제 ID
    • 시간 제한
    • 메모리 제한
    • 제출 횟수
    • 정답 횟수 (비율)
    • 출제자
    • 출처
    • 분류

문제

두 나라 A국과 B국은 항상 사이가 좋지 않은데, 국민들 간에 쌓인 감정을 털어버리기 위해 양국의 대표 선수들이 한 명씩 나와 친선 스포츠 경기를 하기로 했다. 채택된 종목은 철인 N종 경기이다. 철인 N종 경기의 코스는 여러 구간들로 구성되는데, 각 선수는 각 구간에서 정해진 종목을 이용해 결승점으로 이동해야 한다. 예를 들어, 어떤 철인 N종 경기의 코스는 수영 1500km, 마라톤 42.195km, 크로스컨트리 60km, 기어가기 1km 으로 구성될 수 있다.

당신은 국제 철인 N종 경기 협회장으로서, 이 경기에 사용될 종목들과 그 순서를 정하는 역할을 하게 되었다. 두 나라 국민 사이 감정의 앙금을 쌓이지 않게 하기 위해, 가능한 한 두 대표 선수가 비기도록 종목들을 고르고 싶다. 다행히, 당신은 협회장이기 때문에 두 선수가 각 종목에 걸릴 시간을 비교적 정확히 예상할 수 있다. 당신의 예상이 정확하다고 할 때, 두 선수가 비기도록 코스를 설계할 수 있을까? 또한, 비기는 코스 중 걸리는 시간이 가장 짧은 코스는 무엇일까?








종목명A국 선수의 예상 기록B국 선수의 예상 기록
63빌딩 계단 오르기17분15분
남산 스키타고 내려오기217분217분
슬리퍼 신고 42.195km 마라톤134분135분
1500m 앞구르기31분37분
2000m 깽깽이 뛰기10분11분

이와 같이 5개의 종목이 있다고 하자. 그러면, 남산 스키타고 내려오기로 코스를 정하면 양국 선수가 비긴다는 것을 쉽게 알 수 있다. 그러나 그보다 더 좋은 방법이 있다. 63빌딩 계단 오르기 이후 2000m 깽깽이 뛰기를 두번 하도록 코스를 정하면 양국 선수 모두 37분으로 비기기 때문이다.

이와 같은 최적의 코스를 찾는 프로그램을 작성하라.

단, 한 종목을 두 번 이상 코스에 추가할 수도 있다.

입력

입력의 첫 번째 줄에는 테스트 케이스의 수 C (1 <= C <= 50) 가 주어진다. 각 테스트 케이스의 첫 줄에는 채택 가능한 종목의 수 M (1 <= M <= 500) 이 주어지고, 그 후 M 줄에 각 두 개의 숫자로 해당 종목을 완주하는데 두 선수가 걸리는 시간이 정수로 주어진다. 걸리는 시간은 분 단위이며, 항상 1 과 200 사이의 정수이다.

출력

각 테스트 케이스마다 한 줄로, 최적 코스의 완주 시간을 출력한다. 만약 두 선수가 비기는 코스를 만들 수 없다면, 'IMPOSSIBLE' 을 출력한다. (따옴표 제외)

예제 입력

3
5
1 2
3 4
5 6
7 8
7 3
3
1 100
21 20
10 1 
3
10 81
63 71
16 51

예제 출력

11
111
IMPOSSIBLE

노트