책상 위에 N 개의 사탕이 가로 일렬로 늘어서 있고 왼쪽에서 순서대로 1 에서 N 까지의 번호가 붙여져 있다. 사탕 i ( 1≤i≤N )의 맛은 A_i 이다 .

JOI는 N 개의 사탕 중 몇 가지를 선택하고 먹기로 결정했다.

다만, 사탕을 과식하지 않기 위해서, 어느 연속하는 K 개의 사탕에 대해서도, 그 중 최대 2 개 까지만 먹는다. 즉, 어떤 j ( 1≤j≤N - K + 1 )에 대해서도 사탕 j 에서 사탕 j + K - 1 까지의 연속적인 K 사탕 중 먹는 사탕의 개수는 2 개 이하여야 한다.

이 가운데, JOI는 먹는 사탕의 맛의 합계를 가능한 한 크게 하고 싶다.

N 개의 사탕의 맛과 K가 주어졌을 때, JOI가 먹는 사탕의 맛의 합계의 최대치를 구하는 프로그램을 작성하라.

#5857 upload 130 done 30 how_to_reg 28 call_split Subtask

사탕2 (Candies 2) timer 2s memory 1024MB

#5857
Subtask

사탕2 (Candies 2) 2s 1024MB