관광 일정

관광지 $N$곳을 방문하는 여행을 계획하고 있습니다. 관광지에는 1번부터 $N$번까지 번호가 붙어 있으며, 이 순서대로 방문해야 합니다. 하루에 방문할 수 있는 관광지는 최대 $K$곳이고, 가능한 한 적은 일수로 여행을 끝내려고 합니다.

관광지 $i$에는 점수 $a_i$가 주어집니다. 일정이 주어지면 하루의 점수는 그날 방문한 관광지 중 가장 큰 점수입니다. 일정의 총점은 각 날의 점수를 모두 더한 값입니다. 최소 일수를 사용하는 일정 중에서 총점의 최댓값을 구하세요.

첫째 줄에 두 정수 $N$과 $K$가 공백으로 구분되어 주어집니다 ($1 \le K \le N \le 10^6$).

둘째 줄에는 정수 $a_i$가 공백으로 구분되어 $N$개 주어집니다 ($1 \le a_i \le 10^9$).

채점 항목 15개 중 3개는 $2K \ge N$인 경우입니다. 추가로 3개는 $K \le 100$이고 $N \le 10^5$인 경우입니다.

총점의 최댓값을 정수 하나로 출력하세요.