시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 304 81 73 36.139%

문제

창영이와 현우는 새로운 게임을 하고 있다. 이 게임은 여러 라운드로 이루어져 있다. 매 라운드가 시작할 때, 현우는 창영이에게 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줄이다. 각 줄은 해당하는 라운드에서 창영이가 말해야하는 값 (모든 쌍의 합의 최댓값의 최솟값) 이다.

예제 입력 1

3
2 8
3 1
1 4

예제 출력 1

10
10
9
W3sicHJvYmxlbV9pZCI6IjI5MjMiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMyMmJcdWM3OTAgXHVhYzhjXHVjNzg0IiwiZGVzY3JpcHRpb24iOiI8cD5cclxuXHRcdWNjM2RcdWM2MDFcdWM3NzRcdWM2NDAgXHVkNjA0XHVjNmIwXHViMjk0IFx1YzBjOFx1Yjg1Y1x1YzZiNCBcdWFjOGNcdWM3ODRcdWM3NDQgXHVkNTU4XHVhY2UwIFx1Yzc4OFx1YjJlNC4gXHVjNzc0IFx1YWM4Y1x1Yzc4NFx1Yzc0MCBcdWM1ZWNcdWI3ZWMgXHViNzdjXHVjNmI0XHViNGRjXHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuIFx1YjllNCBcdWI3N2NcdWM2YjRcdWI0ZGNcdWFjMDAgXHVjMmRjXHVjNzkxXHVkNTYwIFx1YjU0YywgXHVkNjA0XHVjNmIwXHViMjk0IFx1Y2MzZFx1YzYwMVx1Yzc3NFx1YzVkMFx1YWM4YyAxMDBcdWJjZjRcdWIyZTQgXHVjNzkxXHVjNzQwIFx1YjQ1MCBcdWMyMmJcdWM3OTAgQVx1YzY0MCBCXHViOTdjIFx1YjlkMFx1ZDU3NFx1YzkwMFx1YjJlNC4gXHVhZGY4XHViN2VjXHVhY2UwIFx1YjA5YyBcdWI0YTQsIFx1Y2MzZFx1YzYwMVx1Yzc3NFx1YjI5NCBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHVjNzQwIFx1YmIzOFx1YzgxY1x1Yjk3YyBcdWQ0ODBcdWM1YjRcdWM1N2MgXHVkNTVjXHViMmU0LiZuYnNwOzxcL3A+XHJcblxyXG48cD5cclxuXHRcdWM5YzBcdWFlMDhcdWFlNGNcdWM5YzAgXHVkNjA0XHVjNmIwXHVhYzAwIFx1YjlkMFx1ZDU1YyBcdWJhYThcdWI0ZTAgQVx1YzY0MCBcdWJhYThcdWI0ZTAgQlx1Yjk3YyBcdWM5ZGRcdWM5ZDNcdWIyOTRcdWIyZTQuIFx1Yzc3NFx1YjU0YywgXHVhYzAxIFx1YzMwZFx1Yzc1OCBcdWQ1NjkgXHVjOTExXHVjNWQwXHVjMTFjIFx1YWMwMFx1YzdhNSBcdWQwNzAgXHVhYzEyXHVjNzQ0IFx1Yzc5MVx1YWM4YyBcdWI5Y2NcdWI0ZTRcdWM1YjRcdWI3N2MuPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1Yzk4OSwgXHVkNjA0XHVjN2FjIFx1Yjc3Y1x1YzZiNFx1YjRkY1x1YWMwMCBOIFx1Yjc3Y1x1YzZiNFx1YjRkY1x1Yzc3NFx1Yjc3Y1x1YWNlMCBcdWQ1NThcdWJhNzQsIFx1ZDYwNFx1YzZiMFx1YWMwMCBcdWNjM2RcdWM2MDFcdWM3NzRcdWM1ZDBcdWFjOGMgXHViOWQwXHVkNTVjIFx1YzIyYlx1Yzc5MFx1YjI5NCBhPHN1Yj4xPFwvc3ViPiwgYTxzdWI+MjxcL3N1Yj4sIC4uLiwgYTxzdWI+bjxcL3N1Yj4gXHVhY2ZjIGI8c3ViPjE8XC9zdWI+LCBiPHN1Yj4yPFwvc3ViPiwgLi4uLCBiPHN1Yj5uPFwvc3ViPlx1Yzc3NFx1Yjc3Y1x1YWNlMCBcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHVjNzc0XHViNTRjLCBcdWFjMDEgXHVjMjJiXHVjNzkwXHViOTdjIFx1ZDU1YyBcdWJjODhcdWM1MjkgXHVjMGFjXHVjNmE5XHVkNTU4XHVjNWVjIChhPHN1Yj5pPFwvc3ViPiwgYjxzdWI+ajxcL3N1Yj4pXHVjMzBkXHVjNzQ0IG5cdWFjMWMgXHViOWNjXHViNGU0IFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1Yzc3NFx1YjgwN1x1YWM4YyBcdWMzMGRcdWM3NDQgXHViYWE4XHViNDUwIFx1YjljY1x1YjRlNFx1YzVjOFx1Yzc0NCBcdWI1NGMsIGE8c3ViPmk8XC9zdWI+K2I8c3ViPmo8XC9zdWI+XHVjNzU4IFx1ZDU2OSBcdWM5MTEgXHVhYzAwXHVjN2E1IFx1ZDA3MCBcdWFjMTJcdWM3NDQgXHVhYzAwXHViMmE1XHVkNTVjIFx1Yzc5MVx1YWM4YyBcdWI5Y2NcdWI0ZTRcdWM1YjRcdWM1N2MgXHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHJcblx0XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWI3N2NcdWM2YjRcdWI0ZGNcdWM3NTggXHVjMjE4IE5cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbGU7IE4gJmxlOyAxMDAwMDApIFx1YjJlNFx1Yzc0YyBOXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWFjMDEgXHViNzdjXHVjNmI0XHViNGRjXHVjNWQwXHVjMTFjIFx1ZDYwNFx1YzZiMFx1YWMwMCBcdWI5ZDBcdWQ1NWMgXHVjMjJiXHVjNzkwIEFcdWM2NDAgQlx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsZTsgQSwgQiAmbGU7IDEwMCk8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cclxuXHRcdWNkOWNcdWI4MjVcdWM3NDAgTlx1YzkwNFx1Yzc3NFx1YjJlNC4gXHVhYzAxIFx1YzkwNFx1Yzc0MCBcdWQ1NzRcdWIyZjlcdWQ1NThcdWIyOTQgXHViNzdjXHVjNmI0XHViNGRjXHVjNWQwXHVjMTFjIFx1Y2MzZFx1YzYwMVx1Yzc3NFx1YWMwMCBcdWI5ZDBcdWQ1NzRcdWM1N2NcdWQ1NThcdWIyOTQgXHVhYzEyIChcdWJhYThcdWI0ZTAgXHVjMzBkXHVjNzU4IFx1ZDU2OVx1Yzc1OCBcdWNkNWNcdWIzMTNcdWFjMTJcdWM3NTggXHVjZDVjXHVjMTlmXHVhYzEyKSBcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMjkyMyIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6Ik1BTEkiLCJkZXNjcmlwdGlvbiI6IjxwPk1pcmtvIGFuZCBTbGF2a28gYXJlIHBsYXlpbmcgYSBuZXcgZ2FtZS4gQWdhaW4uIFNsYXZrbyBzdGFydHMgZWFjaCByb3VuZCBieSBnaXZpbmcgTWlya28gdHdvIG51bWJlcnMgQSBhbmQgQiwgYm90aCBzbWFsbGVyIHRoYW4gMTAwLiBNaXJrbyB0aGVuIGhhcyB0byBzbG92ZSB0aGUgZm9sbG93aW5nIHRhc2sgZm9yIFNsYXZrbzogaG93IHRvIHBhaXIgYWxsIGdpdmVuIEEgbnVtYmVycyB3aXRoIGFsbCBnaXZlbiBCIG51bWJlcyBzbyB0aGF0IHRoZSBtYXhpbWFsIHN1bSBvZiBzdWNoIHBhaXJzIGlzIGFzIHNtYWxsIGFzIHBvc3NpYmxlLjxcL3A+XHJcblxyXG48cD5JbiBvdGhlciB3b3JkcywgaWYgZHVyaW5nIHByZXZpb3VzIHJvdW5kcyBTbGF2a28gZ2F2ZSBudW1iZXJzIGE8c3ViPjE8XC9zdWI+LCBhPHN1Yj4yPFwvc3ViPiwgYTxzdWI+MzxcL3N1Yj4gLi4uLiBhPHN1Yj5uPFwvc3ViPiBhbmQgYjxzdWI+MTxcL3N1Yj4sIGI8c3ViPjI8XC9zdWI+LCBiPHN1Yj4zPFwvc3ViPiAuLi4gYjxzdWI+bjxcL3N1Yj4sIGRldGVybWluZSBuIHBhaXJpbmdzIChhPHN1Yj5pPFwvc3ViPiwgYjxzdWI+ajxcL3N1Yj4pIHN1Y2ggdGhhdCBlYWNoIG51bWJlciBpbiBBIHNlcXVlbmNlIGlzIHVzZWQgaW4gZXhhY3RsZXkgb25lIHBhaXJpbmcsIGFuZCBlYWNoIG51bWJlciBpbiBCIHNlcXVlbmN0IGlzIHVzZWQgaW4gZXhhY3RlbHkgb25lIHBhaXJpbmcgYW5kIHRoZSBtYXhpbXVtIG9mIGFsbCBzdW1zIGE8c3ViPmk8XC9zdWI+ICsgYjxzdWI+ajxcL3N1Yj4gaXMgbWluaW1hbC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIGEgc2luZ2xlIGludGVnZXIgTiAoMSAmbGU7IE4gJmxlOyAxMDAwMDApLCBudW1iZXIgb2Ygcm91bmRzLjxcL3A+XHJcblxyXG48cD5OZXh0IE4gbGluZXMgY29udGFpbiB0d28gaW50ZWdlcnMgQSBhbmQgQiAoMSAmbGU7IEEsIEIgJmxlOyAxMDApLCBudW1iZXJzIGdpdmVuIGJ5IFNsYXZrbyBpbiB0aGF0IHJvdW5kLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPk91dHB1dCBjb25zaXN0cyBvZiBOIGxpbmVzLCBvbmUgZm9yIGVhY2ggcm91bmQuIEVhY2ggbGluZSBzaG91bGQgY29udGFpbiB0aGUgc21hbGxlc3QgbWF4aW1hbCBzdW0gZm9yIHRoYXQgcm91bmQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d