Deskripsi Masalah

Di atas meja terdapat $N$ buah permen yang berjajar dalam satu baris horizontal, diberi nomor secara berurutan dari $1$ sampai $N$ dari kiri ke kanan. Kelezatan permen $i$ ($1 \le i \le N$) adalah $A_i$.

JOI-kun memutuskan untuk memilih beberapa dari $N$ permen tersebut dan memakannya.

Namun, agar tidak makan terlalu banyak permen, untuk setiap $K$ permen yang berurutan, ia makan paling banyak $2$ buah di antaranya. Dengan kata lain, untuk setiap $j$ ($1 \le j \le N - K + 1$), di antara $K$ permen berurutan mulai dari permen $j$ hingga permen $j + K - 1$, banyaknya permen yang dimakan haruslah paling banyak $2$ buah.

Dengan syarat tersebut, JOI-kun ingin memaksimalkan total kelezatan permen yang ia makan.

Diberikan kelezatan dari $N$ permen serta nilai $K$, buatlah program untuk mencari nilai maksimum dari total kelezatan permen yang dimakan JOI-kun.

Batasan

• $2 \le K \le N \le 3\,000$.
• $1 \le A_i \le 10^9$ ($1 \le i \le N$).
• Semua nilai masukan adalah bilangan bulat.

Subsoal

1. ($4$ poin) $N \le 20$.
2. ($19$ poin) $K \le 10$.
3. ($47$ poin) $N \le 300$.
4. ($30$ poin) Tidak ada batasan tambahan.

Masukan

Masukan diberikan dari masukan standar dalam format berikut:

N K
A_1 A_2 ... A_N

Keluaran

Pada keluaran standar, keluarkan dalam $1$ baris nilai maksimum dari total kelezatan permen yang dimakan JOI-kun.

Contoh Masukan dan Keluaran

Contoh Masukan 1

5 4
1 3 2 4 3

Contoh Keluaran 1

8

Ketika JOI-kun memakan permen $1$, permen $4$, dan permen $5$, total kelezatannya adalah $8$.

Di antara cara memakan permen sedemikian sehingga untuk setiap $4$ permen berurutan banyaknya permen yang dimakan paling banyak $2$ buah, tidak ada cara yang menghasilkan total kelezatan $9$ atau lebih, sehingga keluarkan $8$.

Contoh masukan ini memenuhi batasan semua subsoal.

Contoh Masukan 2

6 3
3 7 1 5 6 4

Contoh Keluaran 2

21

Ketika JOI-kun memakan permen $1$, permen $2$, permen $4$, dan permen $5$, total kelezatannya adalah $21$.

Di antara cara memakan permen sedemikian sehingga untuk setiap $3$ permen berurutan banyaknya permen yang dimakan paling banyak $2$ buah, tidak ada cara yang menghasilkan total kelezatan $22$ atau lebih, sehingga keluarkan $21$.

Contoh masukan ini memenuhi batasan semua subsoal.

Contoh Masukan 3

5 2
3 3 2 2 1

Contoh Keluaran 3

11

Contoh masukan ini memenuhi batasan semua subsoal.

Contoh Masukan 4

12 5
864814169 716638377 926889183 891468826 217138351 891972397 504371916 678159995 435478604 181254225 760822841 688502728

Contoh Keluaran 4

4427122428

Contoh masukan ini memenuhi batasan semua subsoal.