시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 128 MB 299 79 59 31.720%

문제

데브베이커리에서는 기념일을 맞아 직원들에게 행운쿠키를 선물하기로 하였다. 회사의 간식을 담당하는 철수는 나누어줄 행운 쿠키를 준비하는 역할을 맡게 되었다. 행운쿠키를 만들기 위해서는 N개의 행운반죽을 2개의 오븐을 이용해 구워야 한다. 각각의 행운반죽은 2개의 오븐 중 1개의 오븐에서만 구워져야 하며, 어떤 오븐에서 굽는지에 따라 구워지는데 걸리는 시간이 다르다. 각각의 오븐은 독립적으로 반죽을 구울 수 있으며, 오븐에 반죽을 넣거나 빼는데 걸리는 시간은 없다고 가정하자.

철수는 행운반죽을 모두 구워야 퇴근을 할 수 있다고 한다. 철수가 최대한 빨리 퇴근을 할 수 있도록 행운반죽을 모두 굽는데 걸리는 최소 시간을 구해주자. 

입력

첫번째 줄에 테스트 케이스의 수 T 가 주어진다.

각 케이스의 첫번째 줄에 철수가 가지고 있는 행운반죽의 개수 N(1 ≤ N ≤ 1,000)이 주어진다.

그 다음 N개의 줄에 각 행운반죽이 오븐 1에서 구워지는데 걸리는 시간 ai, 오븐 2에서 구워지는데 걸리는 시간 bi가 주어진다. (1 ≤ ai, bi ≤ 100)

출력

각 테스트 케이스마다 한 줄씩 철수가 행운반죽을 모두 굽는데 걸리는 최소 시간을 출력한다.

예제 입력

2
3
10 5
8 5
8 5
4
15 20
30 21
5 3
10 10

예제 출력

10
25

힌트