저가 항공

바이타자르(Bajtazar)는 오래 기다려 온 휴가를 떠나려 합니다. 비토츠키 바다(Morze Bitockie)의 황금빛 모래사장에서 햇볕을 쬐며 지낼 생각입니다. 바이타자르는 자신의 바이오리듬, 일기 예보, 그리고 비토차(Bitocja)의 문화 행사 등을 고려하여, 휴가 $n$일 각각에 대해 그날을 얼마나 즐겁게 보낼 수 있는지를 나타내는 정수 값인 '휴양 지수'를 매겼습니다. 각 지수는 정수이며 음수일 수도 있는데, 음수는 그날 바이타자르가 바다에 가느니 차라리 집에서 텃밭의 잡초를 뽑는 편이 낫다는 뜻입니다.

다행히 바이타자르가 휴가 전체를 바다에서 보내야 하는 것은 아닙니다. 그가 즐겨 이용하는 저가 항공사가 특별 할인 행사를 열어, 바이타자르는 매우 저렴한 가격에 최대 $k$장의 항공권을 살 수 있습니다(항공권 한 장은 비토츠키 바다까지 갔다가 돌아오는 왕복 여행 한 번에 해당합니다).

바다에서 보내는 날들의 휴양 지수 합이 최대가 되도록 휴가 계획을 세워 주세요. 단, 휴가 동안 바다로 떠나는 횟수는 최대 $k$번입니다. 비행기는 밤에만 운항한다고 가정하므로, 한 번의 여행은 연속된 며칠 동안 바다에 머무는 것에 해당합니다. 즉, 바다에서 보내는 날들은 서로 겹치지 않는 최대 $k$개의 연속 구간을 이루며, 한 번도 떠나지 않는 것(합이 $0$)도 가능합니다.

첫째 줄에 두 정수 $n$과 $k$가 주어집니다 ($1 \le k \le n \le 1{,}000{,}000$). 둘째 줄에는 휴가의 연속된 각 날의 휴양 지수를 나타내는 $n$개의 정수가 주어지며, 각 값의 절댓값은 $10^9$ 이하입니다.

최적의 휴가 계획에서 얻을 수 있는 휴양 지수의 합을 나타내는 정수 하나를 한 줄에 출력합니다.