국수 팀 대회
면접 대비시간 제한2초메모리 제한512 MB
각 팀원의 끓이는 시간과 양념하는 시간이 주어질 때, 모든 국수가 완성되는 시간이 최소가 되도록 순서를 정한다.
문제
국수 요리 대회가 열린다! 각 팀은 N (1 <= N <= 12) 명으로 구성된다. 팀의 각 구성원은 자신의 국수를 요리해야 하지만, 팀에는 국수를 요리할 냄비가 하나뿐이다. 가장 먼저 국수를 완성한 팀이 우승한다.
국수를 요리하는 데는 두 단계가 있다:
- 1단계: 끓는 물에서 국수를 3분간 익히고, 건져서 그릇에 담는다.
- 2단계: 양념을 넣고 비비면 완성!
냄비가 하나뿐이므로, 팀에서 한 번에 한 사람만 1단계를 할 수 있다.
예를 들어, 팀에 두 사람이 있다고 하자:
- Andoko. 1단계에 2분, 2단계에 3분이 걸린다.
- Kurniady. 1단계에 3분, 2단계에 4분이 걸린다.
Andoko가 먼저 냄비를 사용해 1단계를 하면 (Kurniady는 2분을 기다린다), 팀이 국수를 완성하는 데 9분이 걸린다. Kurniady가 먼저 사용하면 (Andoko가 3분을 기다린다), 팀이 국수를 완성하는 데 8분이 걸린다. 따라서 Kurniady를 먼저 하게 하는 것이 더 좋은 결과(더 빠른 완성 시간)를 낳는다.
각 구성원이 1단계와 2단계를 완료하는 데 걸리는 시간이 주어질 때, 팀이 모든 국수를 완성하는 데 필요한 최소 시간을 구하라.
입력
입력의 첫 줄에는 정수 T (1 <= T <= 200000)가 주어지며, 그 뒤에 T 개의 테스트 케이스가 따른다.
각 테스트 케이스는 한 팀의 사람 수를 나타내는 정수 N으로 시작한다. 다음 N개의 줄에는 각각 두 정수 T1과 T2 (0 <= T1, T2 <= 1000)가 주어지며, 이는 각 구성원이 1단계와 2단계를 하는 데 필요한 시간이다.
출력
각 테스트 케이스마다 모든 국수를 완성하는 데 필요한 최소 시간을 한 줄에 출력한다.