무게가 서로 다른 \(N\)개의 화물을 두 화물선에 나누어 싣고자 한다.

각 화물은 첫 번째 화물선에 싣거나, 두 번째 화물선에 싣거나, 사용하지 않을 수 있다. 하나의 화물을 두 화물선에 나누어 실을 수는 없다.

두 화물선에 실린 화물의 총무게가 정확히 같아야 하며, 각 화물선에는 화물이 하나 이상 실려 있어야 한다. 이 조건을 만족하면서 한 화물선에 실린 화물의 총무게를 최대화하는 프로그램을 작성하시오.

모든 화물을 사용할 필요는 없다.

입력

첫째 줄에 화물의 수 \(N\)이 주어진다.

둘째 줄에 각 화물의 무게 \(W_i\)가 공백으로 구분되어 주어진다.

출력

두 화물선이 공통으로 가지는 총무게의 최댓값을 출력한다.

조건을 만족하는 두 화물선을 만들 수 없다면 -1을 출력한다.

제한 사항

• \(1 \le N \le 50\)
• \(1 \le W_i \le 450,000\)
• 모든 화물의 무게 합은 \(450,000\) 이하이다.

예제 입력 1

3
2 3 5

예제 출력 1

5

예제 설명 1

첫 번째 화물선에 무게가 2, 3인 화물을 싣고 두 번째 화물선에 무게가 5인 화물을 실으면 두 화물선의 총무게가 모두 5가 된다.

예제 입력 2

3
10 9 2

예제 출력 2

-1