연세워터파크

(연세대학교 도서관, 2016년 7월)

연세대학교는 매년 여름 깜짝 워터파크를 연다. 어디에 생길지는 아무도 모르고, 보통 도서관이나 서문 쪽에 열린다는 사실만 알려져 있다.

개장을 막기는 어렵다고 판단한 학교는 차라리 학생들이 워터파크를 더 즐기도록 정수 $K_i$가 적힌 징검다리 $N$개를 놓아 두었다. 수업이 끝나고 친구들과 집에 가던 준호는 이 징검다리로 여럿이 함께 즐길 게임을 하나 생각해냈다.

• 각 사람은 시작점으로 쓸 징검다리를 아무거나 하나 고른다.
• 시작점에서 출발한 뒤 계속 점프해 징검다리를 몇 개든 마음대로 밟고, 나오고 싶을 때 나온다. 시작점에서 바로 나오는 것도 가능하다.
• 시작점을 포함해 밟은 모든 징검다리에 적힌 정수의 합이 가장 큰 사람이 이긴다.

이 규칙으로 게임을 하던 준호는 제자리 점프로 10억 점을 만드는 친구를 본 뒤 규칙을 더 보탰다.

• 징검다리 $N$개에 순서대로 $1$번부터 $N$번까지 번호를 붙인다. $U$번 징검다리에서 $V$번 징검다리로 점프하려면 $U$와 $V$의 차이가 미리 정해진 값 $D$ 이하여야 한다.
• 어떤 징검다리도 두 번 이상 밟을 수는 없다.

이제 바뀐 규칙으로 다시 게임을 한다. 준호가 얻을 수 있는 최대 점수는 몇 점인가?

첫 줄에 징검다리의 수 $N$과 문제에서 설명한 $D$가 주어진다. ($2 \le N \le 10^5$, $1 \le D \le N-1$)

이어 정수 $N$개가 $1$번 징검다리부터 $N$번 징검다리까지 순서대로 주어진다. $i$번 징검다리에 적힌 수가 $K_i$이다. ($-10^9 \le K_i \le 10^9$)

가능한 최대 점수를 출력한다.