시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 228 62 55 39.007%

문제

창영이와 현우는 새로운 게임을 하고 있다. 이 게임은 여러 라운드로 이루어져 있다. 매 라운드가 시작할 때, 현우는 창영이에게 100보다 작은 두 숫자 A와 B를 말해준다. 그러고 난 뒤, 창영이는 다음과 같은 문제를 풀어야 한다. 

지금까지 현우가 말한 모든 A와 모든 B를 짝짓는다. 이 때, 각 쌍의 합 중에서 가장 큰 값을 작게 만들어라.

즉, 현재 라운드가 N 라운드이라고 하면, 현우가 창영이에게 말한 숫자는 a1, a2, ..., an 과 b1, b2, ..., bn이라고 할 수 있다. 이 때, 각 숫자를 한 번씩 사용하여 (ai, bj)쌍을 n개 만들 수 있다. 이렇게 쌍을 모두 만들었을 때, ai+bj의 합 중 가장 큰 값을 가능한 작게 만들어야 한다.

입력

첫째 줄에 라운드의 수 N이 주어진다. (1 ≤ N ≤ 100000) 다음 N개의 줄에는 각 라운드에서 현우가 말한 숫자 A와 B가 주어진다. (1 ≤ A, B ≤ 100)

출력

출력은 N줄이다. 각 줄은 해당하는 라운드에서 창영이가 말해야하는 값 (모든 쌍의 합의 최대값의 최소값) 이다.

예제 입력

3
2 8
3 1
1 4

예제 출력

10
10
9

힌트