시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 270 73 65 36.517%

문제

창영이와 현우는 새로운 게임을 하고 있다. 이 게임은 여러 라운드로 이루어져 있다. 매 라운드가 시작할 때, 현우는 창영이에게 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+XHJcblxyXG48cD5cclxuXHRcdWM5YzBcdWFlMDhcdWFlNGNcdWM5YzAgXHVkNjA0XHVjNmIwXHVhYzAwIFx1YjlkMFx1ZDU1YyBcdWJhYThcdWI0ZTAgQVx1YzY0MCBcdWJhYThcdWI0ZTAgQlx1Yjk3YyBcdWM5ZGRcdWM5ZDNcdWIyOTRcdWIyZTQuIFx1Yzc3NCBcdWI1NGMsIFx1YWMwMSBcdWMzMGRcdWM3NTggXHVkNTY5IFx1YzkxMVx1YzVkMFx1YzExYyBcdWFjMDBcdWM3YTUgXHVkMDcwIFx1YWMxMlx1Yzc0NCBcdWM3OTFcdWFjOGMgXHViOWNjXHViNGU0XHVjNWI0XHViNzdjLjxcL3A+XHJcblxyXG48cD5cclxuXHRcdWM5ODksIFx1ZDYwNFx1YzdhYyBcdWI3N2NcdWM2YjRcdWI0ZGNcdWFjMDAgTiBcdWI3N2NcdWM2YjRcdWI0ZGNcdWM3NzRcdWI3N2NcdWFjZTAgXHVkNTU4XHViYTc0LCBcdWQ2MDRcdWM2YjBcdWFjMDAgXHVjYzNkXHVjNjAxXHVjNzc0XHVjNWQwXHVhYzhjIFx1YjlkMFx1ZDU1YyBcdWMyMmJcdWM3OTBcdWIyOTQgYTxzdWI+MTxcL3N1Yj4sIGE8c3ViPjI8XC9zdWI+LCAuLi4sIGE8c3ViPm48XC9zdWI+IFx1YWNmYyBiPHN1Yj4xPFwvc3ViPiwgYjxzdWI+MjxcL3N1Yj4sIC4uLiwgYjxzdWI+bjxcL3N1Yj5cdWM3NzRcdWI3N2NcdWFjZTAgXHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1Yzc3NCBcdWI1NGMsIFx1YWMwMSBcdWMyMmJcdWM3OTBcdWI5N2MgXHVkNTVjIFx1YmM4OFx1YzUyOSBcdWMwYWNcdWM2YTlcdWQ1NThcdWM1ZWMgKGE8c3ViPmk8XC9zdWI+LCBiPHN1Yj5qPFwvc3ViPilcdWMzMGRcdWM3NDQgblx1YWMxYyBcdWI5Y2NcdWI0ZTQgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHVjNzc0XHViODA3XHVhYzhjIFx1YzMwZFx1Yzc0NCBcdWJhYThcdWI0NTAgXHViOWNjXHViNGU0XHVjNWM4XHVjNzQ0IFx1YjU0YywgYTxzdWI+aTxcL3N1Yj4rYjxzdWI+ajxcL3N1Yj5cdWM3NTggXHVkNTY5IFx1YzkxMSBcdWFjMDBcdWM3YTUgXHVkMDcwIFx1YWMxMlx1Yzc0NCBcdWFjMDBcdWIyYTVcdWQ1NWMgXHVjNzkxXHVhYzhjIFx1YjljY1x1YjRlNFx1YzViNFx1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cclxuXHRcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1Yjc3Y1x1YzZiNFx1YjRkY1x1Yzc1OCBcdWMyMTggTlx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsZTsgTiAmbGU7IDEwMDAwMCkgXHViMmU0XHVjNzRjIE5cdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwXHViMjk0IFx1YWMwMSBcdWI3N2NcdWM2YjRcdWI0ZGNcdWM1ZDBcdWMxMWMgXHVkNjA0XHVjNmIwXHVhYzAwIFx1YjlkMFx1ZDU1YyBcdWMyMmJcdWM3OTAgQVx1YzY0MCBCXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEgJmxlOyBBLCBCICZsZTsgMTAwKTxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlxyXG5cdFx1Y2Q5Y1x1YjgyNVx1Yzc0MCBOXHVjOTA0XHVjNzc0XHViMmU0LiBcdWFjMDEgXHVjOTA0XHVjNzQwIFx1ZDU3NFx1YjJmOVx1ZDU1OFx1YjI5NCBcdWI3N2NcdWM2YjRcdWI0ZGNcdWM1ZDBcdWMxMWMgXHVjYzNkXHVjNjAxXHVjNzc0XHVhYzAwIFx1YjlkMFx1ZDU3NFx1YzU3Y1x1ZDU1OFx1YjI5NCBcdWFjMTIgKFx1YmFhOFx1YjRlMCBcdWMzMGRcdWM3NTggXHVkNTY5XHVjNzU4IFx1Y2Q1Y1x1YjMwMFx1YWMxMlx1Yzc1OCBcdWNkNWNcdWMxOGNcdWFjMTIpIFx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIyOTIzIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiTUFMSSIsImRlc2NyaXB0aW9uIjoiPHA+TWlya28gYW5kIFNsYXZrbyBhcmUgcGxheWluZyBhIG5ldyBnYW1lLiBBZ2Fpbi4gU2xhdmtvIHN0YXJ0cyBlYWNoIHJvdW5kIGJ5IGdpdmluZyBNaXJrbyB0d28gbnVtYmVycyBBIGFuZCBCLCBib3RoIHNtYWxsZXIgdGhhbiAxMDAuIE1pcmtvIHRoZW4gaGFzIHRvIHNsb3ZlIHRoZSBmb2xsb3dpbmcgdGFzayBmb3IgU2xhdmtvOiBob3cgdG8gcGFpciBhbGwgZ2l2ZW4gQSBudW1iZXJzIHdpdGggYWxsIGdpdmVuIEIgbnVtYmVzIHNvIHRoYXQgdGhlIG1heGltYWwgc3VtIG9mIHN1Y2ggcGFpcnMgaXMgYXMgc21hbGwgYXMgcG9zc2libGUuPFwvcD5cclxuXHJcbjxwPkluIG90aGVyIHdvcmRzLCBpZiBkdXJpbmcgcHJldmlvdXMgcm91bmRzIFNsYXZrbyBnYXZlIG51bWJlcnMgYTxzdWI+MTxcL3N1Yj4sIGE8c3ViPjI8XC9zdWI+LCBhPHN1Yj4zPFwvc3ViPiAuLi4uIGE8c3ViPm48XC9zdWI+IGFuZCBiPHN1Yj4xPFwvc3ViPiwgYjxzdWI+MjxcL3N1Yj4sIGI8c3ViPjM8XC9zdWI+IC4uLiBiPHN1Yj5uPFwvc3ViPiwgZGV0ZXJtaW5lIG4gcGFpcmluZ3MgKGE8c3ViPmk8XC9zdWI+LCBiPHN1Yj5qPFwvc3ViPikgc3VjaCB0aGF0IGVhY2ggbnVtYmVyIGluIEEgc2VxdWVuY2UgaXMgdXNlZCBpbiBleGFjdGxleSBvbmUgcGFpcmluZywgYW5kIGVhY2ggbnVtYmVyIGluIEIgc2VxdWVuY3QgaXMgdXNlZCBpbiBleGFjdGVseSBvbmUgcGFpcmluZyBhbmQgdGhlIG1heGltdW0gb2YgYWxsIHN1bXMgYTxzdWI+aTxcL3N1Yj4gKyBiPHN1Yj5qPFwvc3ViPiBpcyBtaW5pbWFsLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgaW5wdXQgY29udGFpbnMgYSBzaW5nbGUgaW50ZWdlciBOICgxICZsZTsgTiAmbGU7IDEwMDAwMCksIG51bWJlciBvZiByb3VuZHMuPFwvcD5cclxuXHJcbjxwPk5leHQgTiBsaW5lcyBjb250YWluIHR3byBpbnRlZ2VycyBBIGFuZCBCICgxICZsZTsgQSwgQiAmbGU7IDEwMCksIG51bWJlcnMgZ2l2ZW4gYnkgU2xhdmtvIGluIHRoYXQgcm91bmQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+T3V0cHV0IGNvbnNpc3RzIG9mIE4gbGluZXMsIG9uZSBmb3IgZWFjaCByb3VuZC4gRWFjaCBsaW5lIHNob3VsZCBjb250YWluIHRoZSBzbWFsbGVzdCBtYXhpbWFsIHN1bSBmb3IgdGhhdCByb3VuZC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=