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

문제

꿍 협회는 매년 세계체스대회에 나갈 팀을 만들고 있다. 팀은 흑으로 플레이하는 15명과 백으로 플레이하는 15명, 총 30명으로 이루어진다. 꿍 협회는 가능한 최고의 팀을 만들려고 하는데 각 플레이어의 흑,백 능력치는 각각 1부터 100까지의 정수로 주어진다. 대회가 진행되는 동안 플레이어는 흑, 백 중 한 가지만으로 참여를 해야하며 팀의 전체 능력치는 흑 플레이어의 능력치를 합한것과 백 플레이어의 능력치를 합한것을 모두 더한 값이다. 어떻게 하면 꿍 협회는 가능한 높은 능력치의 팀을 만들수 있을까.

입력

입력은 각 플레이어들의 능력치로 이루어진다. 각 줄은 공백으로 구분되는 두 개의 정수로 주어진다. 첫 번째 숫자는 해당 플레이어가 백으로 플레이를 할 때 능력치고 두 번째 숫자는 흑으로 플레이를 할 때의 능력치다. 최소한 30줄 이상이며 1000줄은 넘지 않는다.

출력

꿍 협회가 만들 수 있는 팀 중 가장 큰 능력치를 갖는 팀의 능력치를 출력한다.

예제 입력 1

87 84
66 78
86 94
93 87
72 100
78 63
60 91
77 64
77 91
87 73
69 62
80 68
81 83
74 63
86 68
53 80
59 73
68 70
57 94
93 62
74 80
70 72
88 85
75 99
71 66
77 64
81 92
74 57
71 63
82 97
76 56

예제 출력 1

2506
W3sicHJvYmxlbV9pZCI6IjE2MzMiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWNkNWNcdWFjZTBcdWM3NTggXHVkMzAwIFx1YjljY1x1YjRlNFx1YWUzMCIsImRlc2NyaXB0aW9uIjoiPHA+XHVhZmNkIFx1ZDYxMVx1ZDY4Y1x1YjI5NCBcdWI5ZTRcdWIxNDQgXHVjMTM4XHVhY2M0XHVjY2I0XHVjMmE0XHViMzAwXHVkNjhjXHVjNWQwIFx1YjA5OFx1YWMwOCBcdWQzMDBcdWM3NDQgXHViOWNjXHViNGU0XHVhY2UwIFx1Yzc4OFx1YjJlNC4gXHVkMzAwXHVjNzQwIFx1ZDc1MVx1YzczY1x1Yjg1YyBcdWQ1MGNcdWI4MDhcdWM3NzRcdWQ1NThcdWIyOTQgMTVcdWJhODVcdWFjZmMgXHViYzMxXHVjNzNjXHViODVjIFx1ZDUwY1x1YjgwOFx1Yzc3NFx1ZDU1OFx1YjI5NCAxNVx1YmE4NSwgXHVjZDFkIDMwXHViYTg1XHVjNzNjXHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzljNFx1YjJlNC4gXHVhZmNkIFx1ZDYxMVx1ZDY4Y1x1YjI5NCBcdWFjMDBcdWIyYTVcdWQ1NWMgXHVjZDVjXHVhY2UwXHVjNzU4IFx1ZDMwMFx1Yzc0NCBcdWI5Y2NcdWI0ZTRcdWI4MjRcdWFjZTAgXHVkNTU4XHViMjk0XHViMzcwIFx1YWMwMSBcdWQ1MGNcdWI4MDhcdWM3NzRcdWM1YjRcdWM3NTggXHVkNzUxLFx1YmMzMSBcdWIyYTVcdWI4MjVcdWNlNThcdWIyOTQgXHVhYzAxXHVhYzAxIDFcdWJkODBcdWQxMzAgMTAwXHVhZTRjXHVjOWMwXHVjNzU4IFx1YzgxNVx1YzIxOFx1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YjMwMFx1ZDY4Y1x1YWMwMCBcdWM5YzRcdWQ1ODlcdWI0MThcdWIyOTQgXHViM2Q5XHVjNTQ4IFx1ZDUwY1x1YjgwOFx1Yzc3NFx1YzViNFx1YjI5NCZuYnNwO1x1ZDc1MSwgXHViYzMxIFx1YzkxMSBcdWQ1NWMgXHVhYzAwXHVjOWMwXHViOWNjXHVjNzNjXHViODVjIFx1Y2MzOFx1YzVlY1x1Yjk3YyBcdWQ1NzRcdWM1N2NcdWQ1NThcdWJhNzAgXHVkMzAwXHVjNzU4IFx1YzgwNFx1Y2NiNCBcdWIyYTVcdWI4MjVcdWNlNThcdWIyOTQgXHVkNzUxIFx1ZDUwY1x1YjgwOFx1Yzc3NFx1YzViNFx1Yzc1OCBcdWIyYTVcdWI4MjVcdWNlNThcdWI5N2MgXHVkNTY5XHVkNTVjXHVhYzgzXHVhY2ZjIFx1YmMzMSBcdWQ1MGNcdWI4MDhcdWM3NzRcdWM1YjRcdWM3NTggXHViMmE1XHViODI1XHVjZTU4XHViOTdjIFx1ZDU2OVx1ZDU1Y1x1YWM4M1x1Yzc0NCBcdWJhYThcdWI0NTAgXHViMzU0XHVkNTVjIFx1YWMxMlx1Yzc3NFx1YjJlNC4gXHVjNWI0XHViNWJiXHVhYzhjIFx1ZDU1OFx1YmE3NCBcdWFmY2QgXHVkNjExXHVkNjhjXHViMjk0IFx1YWMwMFx1YjJhNVx1ZDU1YyBcdWIxOTJcdWM3NDAgXHViMmE1XHViODI1XHVjZTU4XHVjNzU4IFx1ZDMwMFx1Yzc0NCBcdWI5Y2NcdWI0ZTRcdWMyMTggXHVjNzg4XHVjNzQ0XHVhZTRjLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjNzg1XHViODI1XHVjNzQwIFx1YWMwMSBcdWQ1MGNcdWI4MDhcdWM3NzRcdWM1YjRcdWI0ZTRcdWM3NTggXHViMmE1XHViODI1XHVjZTU4XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzljNFx1YjJlNC4gXHVhYzAxIFx1YzkwNFx1Yzc0MCBcdWFjZjVcdWJjMzFcdWM3M2NcdWI4NWMgXHVhZDZjXHViZDg0XHViNDE4XHViMjk0IFx1YjQ1MCBcdWFjMWNcdWM3NTggXHVjODE1XHVjMjE4XHViODVjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVjY2FiIFx1YmM4OFx1YzlmOCBcdWMyMmJcdWM3OTBcdWIyOTQgXHVkNTc0XHViMmY5IFx1ZDUwY1x1YjgwOFx1Yzc3NFx1YzViNFx1YWMwMCBcdWJjMzFcdWM3M2NcdWI4NWMgXHVkNTBjXHViODA4XHVjNzc0XHViOTdjIFx1ZDU2MCBcdWI1NGMgXHViMmE1XHViODI1XHVjZTU4XHVhY2UwIFx1YjQ1MCBcdWJjODhcdWM5ZjggXHVjMjJiXHVjNzkwXHViMjk0IFx1ZDc1MVx1YzczY1x1Yjg1YyBcdWQ1MGNcdWI4MDhcdWM3NzRcdWI5N2MgXHVkNTYwIFx1YjU0Y1x1Yzc1OCBcdWIyYTVcdWI4MjVcdWNlNThcdWIyZTQuIFx1Y2Q1Y1x1YzE4Y1x1ZDU1YyAzMFx1YzkwNCBcdWM3NzRcdWMwYzFcdWM3NzRcdWJhNzAgMTAwMFx1YzkwNFx1Yzc0MCBcdWIxMThcdWM5YzAgXHVjNTRhXHViMjk0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWZjZCBcdWQ2MTFcdWQ2OGNcdWFjMDAgXHViOWNjXHViNGU0IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVkMzAwIFx1YzkxMSBcdWFjMDBcdWM3YTUgXHVkMDcwIFx1YjJhNVx1YjgyNVx1Y2U1OFx1Yjk3YyBcdWFjMTZcdWIyOTQgXHVkMzAwXHVjNzU4IFx1YjJhNVx1YjgyNVx1Y2U1OFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiMTYzMyIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkNoZXNzIiwiZGVzY3JpcHRpb24iOiI8cD5UaGUgQXNzb2NpYXRpb24gb2YgQ2hlc3MgTW9uc3RlcnMgKEFDTSkgaXMgcGxhbm5pbmcgdGhlaXIgYW5udWFsIHRlYW0gbWF0Y2ggdXAgYWdhaW5zdCB0aGUgcmVzdCBvZiB0aGUgd29ybGQuIFRoZSBtYXRjaCB3aWxsIGJlIG9uIDMwIGJvYXJkcywgd2l0aCAxNSBwbGF5ZXJzIHBsYXlpbmcgd2hpdGUgYW5kIDE1IHBsYXllcnMgcGxheWluZyBibGFjay4gQUNNIGhhcyBtYW55IHBsYXllcnMgdG8gY2hvb3NlIGZyb20sIGFuZCB0aGV5IHRyeSB0byBwaWNrIHRoZSBiZXN0IHRlYW0gdGhleSBjYW4uIFRoZSBhYmlsaXR5IG9mIGVhY2ggcGxheWVyIGZvciBwbGF5aW5nIHdoaXRlIGlzIG1lYXN1cmVkIG9uIGEgc2NhbGUgZnJvbSAxIHRvIDEwMCBhbmQgdGhlIHNhbWUgZm9yIHBsYXlpbmcgYmxhY2suIER1cmluZyB0aGUgbWF0Y2ggYSBwbGF5ZXIgY2FuIHBsYXkgd2hpdGUgb3IgYmxhY2sgYnV0IG5vdCBib3RoLiBUaGUgdmFsdWUgb2YgYSB0ZWFtIGlzIHRoZSB0b3RhbCBvZiBwbGF5ZXJzJiMzOTsgYWJpbGl0aWVzIHRvIHBsYXkgd2hpdGUgZm9yIHBsYXllcnMgZGVzaWduYXRlZCB0byBwbGF5IHdoaXRlIGFuZCBwbGF5ZXJzJiMzOTsgYWJpbGl0aWVzIHRvIHBsYXkgYmxhY2sgZm9yIHBsYXllcnMgZGVzaWduYXRlZCB0byBwbGF5IGJsYWNrLiBBQ00gd2FudHMgdG8gcGljayB1cCBhIHRlYW0gd2l0aCB0aGUgaGlnaGVzdCB0b3RhbCB2YWx1ZS48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPklucHV0IGNvbnNpc3RzIG9mIGEgc2VxdWVuY2Ugb2YgbGluZXMgZ2l2aW5nIHBsYXllcnMmIzM5OyBhYmlsaXRpZXMuIEVhY2ggbGluZSBnaXZlcyB0aGUgYWJpbGl0aWVzIG9mIGEgc2luZ2xlIHBsYXllciBieSB0d28gaW50ZWdlciBudW1iZXJzIHNlcGFyYXRlZCBieSBhIHNpbmdsZSBzcGFjZS4gVGhlIGZpcnN0IG51bWJlciBpcyB0aGUgcGxheWVyJiMzOTtzIGFiaWxpdHkgdG8gcGxheSB3aGl0ZSBhbmQgdGhlIHNlY29uZCBpcyB0aGUgcGxheWVyJiMzOTtzIGFiaWxpdHkgdG8gcGxheSBibGFjay4gVGhlcmUgd2lsbCBiZSBubyBsZXNzIHRoYW4gMzAgYW5kIG5vIG1vcmUgdGhhbiAxMDAwIGxpbmVzIG9uIGlucHV0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPk91dHB1dCBhIHNpbmdsZSBsaW5lIGNvbnRhaW5pbmcgYW4gaW50ZWdlciBudW1iZXIgZ2l2aW5nIHRoZSB2YWx1ZSBvZiB0aGUgYmVzdCBjaGVzcyB0ZWFtIHRoYXQgQUNNIGNhbiBhc3NlbWJsZS48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d