시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB150043433033.000%

문제

창영이와 현우는 새로운 게임을 하고 있다. 이 게임은 여러 라운드로 이루어져 있다. 매 라운드가 시작할 때, 현우는 창영이에게 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

예제 입력 2

3
1 1
2 2
3 3

예제 출력 2

2
3
4
W3sicHJvYmxlbV9pZCI6IjI5MjMiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMyMmJcdWM3OTAgXHVhYzhjXHVjNzg0IiwiZGVzY3JpcHRpb24iOiI8cD5cdWNjM2RcdWM2MDFcdWM3NzRcdWM2NDAgXHVkNjA0XHVjNmIwXHViMjk0IFx1YzBjOFx1Yjg1Y1x1YzZiNCBcdWFjOGNcdWM3ODRcdWM3NDQgXHVkNTU4XHVhY2UwIFx1Yzc4OFx1YjJlNC4gXHVjNzc0IFx1YWM4Y1x1Yzc4NFx1Yzc0MCBcdWM1ZWNcdWI3ZWMgXHViNzdjXHVjNmI0XHViNGRjXHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuIFx1YjllNCBcdWI3N2NcdWM2YjRcdWI0ZGNcdWFjMDAgXHVjMmRjXHVjNzkxXHVkNTYwIFx1YjU0YywgXHVkNjA0XHVjNmIwXHViMjk0IFx1Y2MzZFx1YzYwMVx1Yzc3NFx1YzVkMFx1YWM4YyAxMDBcdWJjZjRcdWIyZTQgXHVjNzkxXHVjNzQwIFx1YjQ1MCBcdWMyMmJcdWM3OTAgQVx1YzY0MCBCXHViOTdjIFx1YjlkMFx1ZDU3NFx1YzkwMFx1YjJlNC4gXHVhZGY4XHViN2VjXHVhY2UwIFx1YjA5YyBcdWI0YTQsIFx1Y2MzZFx1YzYwMVx1Yzc3NFx1YjI5NCBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHVjNzQwIFx1YmIzOFx1YzgxY1x1Yjk3YyBcdWQ0ODBcdWM1YjRcdWM1N2MgXHVkNTVjXHViMmU0LiA8XC9wPlxyXG5cclxuPHA+XHVjOWMwXHVhZTA4XHVhZTRjXHVjOWMwIFx1ZDYwNFx1YzZiMFx1YWMwMCBcdWI5ZDBcdWQ1NWMgXHViYWE4XHViNGUwIEFcdWM2NDAgXHViYWE4XHViNGUwIEJcdWI5N2MgXHVjOWRkXHVjOWQzXHViMjk0XHViMmU0LiBcdWM3NzRcdWI1NGMsIFx1YWMwMSBcdWMzMGRcdWM3NTggXHVkNTY5IFx1YzkxMVx1YzVkMFx1YzExYyBcdWFjMDBcdWM3YTUgXHVkMDcwIFx1YWMxMlx1Yzc0NCBcdWM3OTFcdWFjOGMgXHViOWNjXHViNGU0XHVjNWI0XHViNzdjLjxcL3A+XHJcblxyXG48cD5cdWM5ODksIFx1ZDYwNFx1YzdhYyBcdWI3N2NcdWM2YjRcdWI0ZGNcdWFjMDAgTiBcdWI3N2NcdWM2YjRcdWI0ZGNcdWM3NzRcdWI3N2NcdWFjZTAgXHVkNTU4XHViYTc0LCBcdWQ2MDRcdWM2YjBcdWFjMDAgXHVjYzNkXHVjNjAxXHVjNzc0XHVjNWQwXHVhYzhjIFx1YjlkMFx1ZDU1YyBcdWMyMmJcdWM3OTBcdWIyOTQgYTxzdWI+MTxcL3N1Yj4sIGE8c3ViPjI8XC9zdWI+LCAuLi4sIGE8c3ViPm48XC9zdWI+IFx1YWNmYyBiPHN1Yj4xPFwvc3ViPiwgYjxzdWI+MjxcL3N1Yj4sIC4uLiwgYjxzdWI+bjxcL3N1Yj5cdWM3NzRcdWI3N2NcdWFjZTAgXHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1Yzc3NFx1YjU0YywgXHVhYzAxIFx1YzIyYlx1Yzc5MFx1Yjk3YyBcdWQ1NWMgXHViYzg4XHVjNTI5IFx1YzBhY1x1YzZhOVx1ZDU1OFx1YzVlYyAoYTxzdWI+aTxcL3N1Yj4sIGI8c3ViPmo8XC9zdWI+KVx1YzMwZFx1Yzc0NCBuXHVhYzFjIFx1YjljY1x1YjRlNCBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWM3NzRcdWI4MDdcdWFjOGMgXHVjMzBkXHVjNzQ0IFx1YmFhOFx1YjQ1MCBcdWI5Y2NcdWI0ZTRcdWM1YzhcdWM3NDQgXHViNTRjLCBhPHN1Yj5pPFwvc3ViPitiPHN1Yj5qPFwvc3ViPlx1Yzc1OCBcdWQ1NjkgXHVjOTExIFx1YWMwMFx1YzdhNSBcdWQwNzAgXHVhYzEyXHVjNzQ0IFx1YWMwMFx1YjJhNVx1ZDU1YyBcdWM3OTFcdWFjOGMgXHViOWNjXHViNGU0XHVjNWI0XHVjNTdjIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHViNzdjXHVjNmI0XHViNGRjXHVjNzU4IFx1YzIxOCBOXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEgJmxlOyBOICZsZTsgMTAwMDAwKSBcdWIyZTRcdWM3NGMgTlx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVhYzAxIFx1Yjc3Y1x1YzZiNFx1YjRkY1x1YzVkMFx1YzExYyBcdWQ2MDRcdWM2YjBcdWFjMDAgXHViOWQwXHVkNTVjIFx1YzIyYlx1Yzc5MCBBXHVjNjQwIEJcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbGU7IEEsIEIgJmx0OyAxMDApPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjZDljXHViODI1XHVjNzQwIE5cdWM5MDRcdWM3NzRcdWIyZTQuIFx1YWMwMSBcdWM5MDRcdWM3NDAgXHVkNTc0XHViMmY5XHVkNTU4XHViMjk0IFx1Yjc3Y1x1YzZiNFx1YjRkY1x1YzVkMFx1YzExYyBcdWNjM2RcdWM2MDFcdWM3NzRcdWFjMDAgXHViOWQwXHVkNTc0XHVjNTdjXHVkNTU4XHViMjk0IFx1YWMxMiAoXHViYWE4XHViNGUwIFx1YzMwZFx1Yzc1OCBcdWQ1NjlcdWM3NTggXHVjZDVjXHViMzEzXHVhYzEyXHVjNzU4IFx1Y2Q1Y1x1YzE5Zlx1YWMxMikgXHVjNzc0XHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6IjI5MjMiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJNQUxJIiwiZGVzY3JpcHRpb24iOiI8cD5NaXJrbyBhbmQgU2xhdmtvIGFyZSBwbGF5aW5nIGEgbmV3IGdhbWUuIEFnYWluLiBTbGF2a28gc3RhcnRzIGVhY2ggcm91bmQgYnkgZ2l2aW5nIE1pcmtvIHR3byBudW1iZXJzIEEgYW5kIEIsIGJvdGggc21hbGxlciB0aGFuIDEwMC4gTWlya28gdGhlbiBoYXMgdG8gc2xvdmUgdGhlIGZvbGxvd2luZyB0YXNrIGZvciBTbGF2a286IGhvdyB0byBwYWlyIGFsbCBnaXZlbiBBIG51bWJlcnMgd2l0aCBhbGwgZ2l2ZW4gQiBudW1iZXMgc28gdGhhdCB0aGUgbWF4aW1hbCBzdW0gb2Ygc3VjaCBwYWlycyBpcyBhcyBzbWFsbCBhcyBwb3NzaWJsZS48XC9wPlxyXG5cclxuPHA+SW4gb3RoZXIgd29yZHMsIGlmIGR1cmluZyBwcmV2aW91cyByb3VuZHMgU2xhdmtvIGdhdmUgbnVtYmVycyBhPHN1Yj4xPFwvc3ViPiwgYTxzdWI+MjxcL3N1Yj4sIGE8c3ViPjM8XC9zdWI+IC4uLi4gYTxzdWI+bjxcL3N1Yj4gYW5kIGI8c3ViPjE8XC9zdWI+LCBiPHN1Yj4yPFwvc3ViPiwgYjxzdWI+MzxcL3N1Yj4gLi4uIGI8c3ViPm48XC9zdWI+LCBkZXRlcm1pbmUgbiBwYWlyaW5ncyAoYTxzdWI+aTxcL3N1Yj4sIGI8c3ViPmo8XC9zdWI+KSBzdWNoIHRoYXQgZWFjaCBudW1iZXIgaW4gQSBzZXF1ZW5jZSBpcyB1c2VkIGluIGV4YWN0bGV5IG9uZSBwYWlyaW5nLCBhbmQgZWFjaCBudW1iZXIgaW4gQiBzZXF1ZW5jdCBpcyB1c2VkIGluIGV4YWN0ZWx5IG9uZSBwYWlyaW5nIGFuZCB0aGUgbWF4aW11bSBvZiBhbGwgc3VtcyBhPHN1Yj5pPFwvc3ViPiArIGI8c3ViPmo8XC9zdWI+IGlzIG1pbmltYWwuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiBpbnB1dCBjb250YWlucyBhIHNpbmdsZSBpbnRlZ2VyIE4gKDEgJmxlOyBOICZsZTsgMTAwMDAwKSwgbnVtYmVyIG9mIHJvdW5kcy48XC9wPlxyXG5cclxuPHA+TmV4dCBOIGxpbmVzIGNvbnRhaW4gdHdvIGludGVnZXJzIEEgYW5kIEIgKDEgJmxlOyBBLCBCICZsdDsgMTAwKSwgbnVtYmVycyBnaXZlbiBieSBTbGF2a28gaW4gdGhhdCByb3VuZC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5PdXRwdXQgY29uc2lzdHMgb2YgTiBsaW5lcywgb25lIGZvciBlYWNoIHJvdW5kLiBFYWNoIGxpbmUgc2hvdWxkIGNvbnRhaW4gdGhlIHNtYWxsZXN0IG1heGltYWwgc3VtIGZvciB0aGF0IHJvdW5kLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=

출처

Contest > Croatian Open Competition in Informatics > COCI 2009/2010 > Contest #1 4번