행운쿠키 제작소

데브베이커리는 기념일을 맞아 직원에게 행운쿠키를 나눠주기로 했다. 간식을 맡은 철수가 쿠키를 굽는 일을 하게 되었다.

철수는 행운반죽 $N$개를 오븐 2대로 모두 구워야 한다. 반죽 하나는 두 오븐 중 한 대에서만 굽고, 어느 오븐에 넣느냐에 따라 굽는 시간이 다르다. 두 오븐은 서로 독립적으로 동시에 돌아가지만, 한 오븐은 한 번에 반죽 하나만 굽는다. 그래서 한 오븐이 일을 마치는 시각은 그 오븐에 배정한 반죽의 굽는 시간을 모두 더한 값이고, 전체 작업이 끝나는 시각은 두 오븐 중 늦게 끝나는 쪽의 시각이다. 반죽을 넣거나 빼는 시간은 0이다.

철수는 반죽을 모두 구워야 퇴근한다. 반죽을 전부 굽는 데 걸리는 최소 시간을 구하라.

첫 줄에 테스트 케이스의 수 $T$ ($1 \le T \le 20$)가 주어진다.

각 테스트 케이스의 첫 줄에 행운반죽의 개수 $N$ ($1 \le N \le 1000$)이 주어진다. 이어지는 $N$개의 줄에는 각 반죽을 오븐 1에서 굽는 데 걸리는 시간 $a_i$와 오븐 2에서 굽는 데 걸리는 시간 $b_i$가 공백 하나로 구분되어 주어진다 ($1 \le a_i, b_i \le 100$).

각 테스트 케이스마다 반죽을 모두 굽는 데 걸리는 최소 시간을 한 줄에 하나씩 출력한다.