체스 연합회는 일년에 한 번씩 열리는 체스 대회를 준비하고 있다. 이 대회는 백팀 15 명 흑팀 15 명으로 총 30 명의 선수가 필요하다.

이 연합회는 회원 중 최고의 팀으로 팀을 구성하기를 원한다.

백으로 게임을 할 경우의 회원의 능력치는 1 에서 100 가지의 수로 주어진다. 흑도 마찬가지이다. 팀의 능력은 흰색팀의 능력의 합과 검은색 팀의 능력의 합으로 표현된다.

요약하면 , 30 명을 선택 -- 15 명은 흰색 15 명은 검은색으로 합이 최대가 되게 뽑는 문제

입력

파일의 끝은 EOF 이다.

출력

입출력 예

입력

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

출력

2506

출처:The UofA Local 1999.10.16