coffee21   4년 전

문제

오늘도 비가 오고 있습니다. Paweł과 Gaweł은 집에 머물 수밖에 없었습니다. 수업이 없기 때문에 그들은 게임을 만들기로 결정했습니다. Paweł은 기발한 아이디어를 가지고 있었습니다. 

그는 한 장의 종이에 n개의 칸을 그렸습니다. 각 칸에는 두 개의 숫자가 있습니다. 첫 번째는 칸 번호(1에서 n까지의 자연수, 각 칸은 서로 다른 숫자를 가짐)이고 두 번째는 칸의 값(-1,000에서 1,000 사이의 정수)입니다. 

플레이어는 1에서 6까지의 숫자가 적힌 정육면체 주사위를 던지고, 주사위에서 나온 수만큼 말을 움직입니다. 말은 칸 번호 1에서 시작하여 칸 번호 n에 도착하면 게임이 종료됩니다. 플레이어가 얻는 점수는 말이 지나온 칸 값의 합입니다. 

몇 게임을 플레이한 후 Paweł과 Gaweł은 여러 가지 다른 결과를 얻었지만 그 중 어떤 것이 가능한 한 가장 큰 점수가 되는 것인지는 알 수 없었습니다. 그래서 그들은 유능한 프로그래머인 당신에게 주어진 보드에 대해 가능한 최대 점수를 계산할 프로그램을 작성하도록 요청했습니다.

입력

입력의 첫 번째 줄에는 보드의 칸 수를 나타내는 하나의 정수 n(1 ≤ n ≤ 10^6)이 주어집니다. 두 번째 줄에는 n개의 정수 w1, w2, ..., wi(-1,000 ≤ wi ≤ 1,000)가 포함됩니다. 여기서 wi는 i번째 칸의 값을 나타냅니다.

출력

출력의 첫 번째 줄에는 주어진 보드에서 가능한 최대 점수를 출력합니다.

예제 입력1

4

1 2 -1 1

예제 출력1

4

댓글을 작성하려면 로그인해야 합니다.