산산조각 난 정수

앨리스와 밥은 아주 큰 정수를 새로 사서 파티에서 자랑한 뒤 집으로 돌아가고 있었다. 정수가 워낙 커서 둘이 함께 들어야 했는데, 돌아가는 길에 둘 다 발을 헛디뎠다. 정수는 보도 위로 떨어져 $n$개의 양의 정수 조각으로 산산조각 났다.

비싼 정수를 사느라 이미 살림이 빠듯했던 두 사람은 이 일을 계기로 헤어지기로 했다. 남은 조각은 게임으로 나눈다. 조각이 하나도 남지 않을 때까지 번갈아 가며 조각을 하나씩 가져가고, 앨리스가 먼저 가져간다.

두 사람은 자기가 가져간 조각의 합을 최대로 만들려 하고, 둘 다 최적으로 행동한다. 앨리스와 밥이 최종적으로 가지는 합을 각각 구하시오.

입력은 두 줄로 이루어진다.

첫째 줄에 조각의 개수 $n$이 주어진다. ($1 \le n \le 15$)

둘째 줄에 조각의 값 $a_0, a_1, \dots, a_{n-1}$이 공백으로 구분되어 주어진다. ($1 \le a_i \le 100$)

한 줄에 앨리스가 가진 조각의 합과 밥이 가진 조각의 합을 공백으로 구분해 출력한다.