Statement
djangg7과 ibasic은 광산에서 보석을 캐는 광부이다. 광산은 지하 층부터 지하 층까지 있다. 이때 은 짝수이다.
광산의 각 층에는 개의 보석이 있다. 지하 층의 번째 보석의 가치는 이다.
두 사람은 작업의 효율을 위해 지하 층부터 지하 층까지 순서대로 방문한다. 지하 층에서는 djangg7이 보석을 캐며, 이후로는 직전 층에서 보석을 캐지 않은 광부가 보석을 캔다.
빠르고 정확한 작업을 위해 한 층에서는 보석을 정확히 하나 캐야 한다. 그런데 지하 층에서 번째 보석을 캐면 지하 층의 번째 보석의 보석이 훼손되며, 훼손된 보석의 가치는 이 된다. 지하 층에서 보석을 캘 때는 지하 층이 없으므로 아무런 보석도 훼손되지 않는다.
너무 심심했던 djangg7과 ibasic은 각자 채굴한 보석의 가치 합을 비교하여 가치 합이 더 높은 광부가 승리하는 게임을 하기로 했다. 두 광부가 캔 보석의 가치 합이 같은 경우 ibasic이 이긴다.
격차를 최대한 벌리는 것이 좋다고 생각한 두 광부는 모든 보석을 캔 뒤 자신이 캔 보석의 가치 합에서 상대가 캔 보석의 가치 합을 뺀 값을 최대화하는 전략을 사용하기로 했다. 이때 누가 승리하는 지와 두 광부가 캔 보석의 가치 합의 차이를 구하시오.
Input
첫 번째 줄에 광산의 층 수 , 각 층에 있는 보석의 개수 가 공백으로 구분되어 주어진다. 은 짝수
두 번째 줄부터 개의 줄에 걸쳐 각 줄에 각 층에 있는 보석의 가치를 나타내는 개의 정수가 공백으로 구분되어 주어진다. 번째 줄에는 지하 층에 있는 보석의 가치 가 공백으로 구분되어 주어진다.
Output
첫 번째 줄에 게임의 승자와 두 광부가 캔 보석의 가치 합의 차을 공백으로 구분하여 출력한다.