题目描述

共有偶数件作业，需要两两配成若干组并行处理。一件难度为 $y$ 的作业与另一件难度为 $z$ 的作业组成一组时，耗时为 $y+z$；总完成时间是所有组耗时的最大值。输入按难度汇总为 $N$ 类，第 $i$ 类有 $x_i$ 件、难度 $y_i$。求最短总完成时间。

输入格式

第一行整数 $N$，接下来 $N$ 行为 $x_i,y_i$。

输出格式

输出最短总完成时间。

输入

4
695 508954041
370 767974739
267 25405041
28 639412023

输出

1276928780

输入

16
604 855542425
925 129745571
745 683446736
449 177452984
583 272701105
17 223277461
332 997238415
862 218822398
894 197419624
883 249333840
509 422336195
600 939920468
35 316611517
750 733539080
686 789941450
418 976402245

输出

1126983986

输入

22
202 168103040
915 472632552
57 951092824
550 924220651
309 534910068
648 844372329
800 930473660
634 377842550
413 47639538
202 559621151
492 880262441
597 910100389
389 904850583
422 158760371
690 142613881
943 69836224
777 632008112
796 176196358
940 369781381
47 137883222
634 910693890
729 537427170

输出

1250043822

数据范围

$1\le N\le10^5$，总件数为不超过 $10^9$ 的偶数，$1\le y_i\le10^9$。