N개의 구멍이 있고 그 위에 공이 나오는 통로가 있다.당신은 이 통로에 직선 모양의 경사를 설치할 것이다. 경사는 두 개 이상의 통로를 덮어야 한다. 공이 나온 후에는 곧바로 떨어지거나 경사에 구른 후 떨어지는데, 최종적으로 N개 중 하나의 구멍에 들어가게 된다.
각 구멍마다 정수의 점수가 매겨져 있는데, 최종 점수는 N개의 공이 들어간 구멍의 점수의 합이 된다. 당신은 경사를 잘 설치해서 점수가 최대한 높게 나오게 하려고 한다. 그런데, 경사를 왼쪽으로 기울일 경우와 오른쪽으로 기울일 경우에 얻을 수 있는 최고 점수가 다를 수 있다.
6개의 구멍이 있어 각 구멍의 점수가 순서대로 6, 10, -7, 2, 5, -12인 경우, 경사를 왼쪽으로 기울여 설치할 경우 아래 왼쪽 그림과 같이 설치하면 56점을 얻을 수 있으며, 경사를 오른쪽으로 기울여 설치할 경우 아래 오른쪽 그림과 같이 설치하면 19점을 얻을 수 있다.
각 구멍의 점수가 주어질 때, 경사를 오른쪽으로 기울여서 설치할 때와 왼쪽으로 기울여서 설치할 때 얻을 수 있는 최대 점수를 구하는 프로그램을 작성하여라.
입력 6 6 10 -7 2 5 -12 출력 19 56
번역: functionx 출처 : Balkan Olympiad in Informatics 2012, Day 2 Task 3 http://boi2012.dms.rs/index.php?action=show&data=tasks