태곳적부터, A나라와 B나라는 서로 전쟁을 해 왔다. 이제 두 나라는 휴전 협정에 서명했으며, 이를 기념하기 위해 2인용 자전거 타기 경주에 참여하기로 했다. A, B 나라에서 각각 N명씩 출전하며, 각 나라에서 1명씩 두 나라가 서로 짝을 이룬 한 팀이 2인용 자건거를 타는 방식으로, N개의 팀이 경기를 치르게 된다. 1명의 출전자는 자신의 평소에 타던 1인용 자건거 속도를 갖고 있으며, '2인용 자건거 속도 C'는 팀원 2명 중 1인용 자전거 속도가 더 큰 사람의 속도로 결정된다. 즉, 한 팀을 이룬 두 명의 1인용 자건거 속도가 각각 a, b 라고 하면, 2인용 자건거의 속도 C는 MAX(a, b) 이다. 그리고 '전체 속도 D'는 N개 팀의 '2인용 자건거 속도 C'의 합이다. 이때, 다음 2가지 질문 중 한 질문의 답을 구하는 프로그램을 작성하시오.
|
첫번째 줄에 질문 유형 번호 1, 또는 2가 주어진다.
두번째 줄에 각 나라의 출전자 인원 N (\(1 \leq N \leq 100\))이 주어진다.
세번째 줄에 A 나라 출전자 N명의 속도가 공백 1개를 사이에 두고 주어진다. 각 사람의 속도는 1 ~ 1,000,000 사이의 정수다.
네번째 줄에 B 나라 출전자 N명의 속도가 공백 1개를 사이에 두고 주어진다. 각 사람의 속도는 1 ~ 1,000,000 사이의 정수다.
15개의 채점 데이터 중에서 8개는 질문 1이, 7개는 질문 2가 제시된다.
입력에서 제시한 질문에 대한 답, 즉, 전체 속도 D의 최대값, 또는 최솟값을 출력한다.
(예시1) MAX(5, 6) + MAX(1, 2) + MAX(4, 4) = 12
(예시2) MAX(5, 2) + MAX(1, 6) + MAX(4, 4) = 15
(예시3) MAX(202, 1) + MAX(177, 540) + MAX(189, 17) + MAX(589, 78) + MAX(102, 496) = 2016