Luyện tập của Polycarp

Polycarp có một danh sách gồm $n$ bài tập với độ khó lần lượt là $a_1,a_2,\dots ,a_n$. Anh dự định luyện tập trong đúng $k$ ngày. Mỗi ngày anh phải giải ít nhất một bài, giải các bài theo đúng thứ tự trong danh sách, không được bỏ qua bài nào và không giải lại bài đã giải. Như vậy, mỗi ngày Polycarp giải một đoạn liên tiếp các bài, và sau $k$ ngày anh giải hết toàn bộ $n$ bài.

Lợi ích của ngày thứ $j$ là độ khó lớn nhất trong số các bài giải ngày hôm đó: nếu ngày đó anh giải các bài từ vị trí $l$ đến $r$ thì lợi ích là ${max}_{l\le i\le r}{a}_i$. Tổng lợi ích là tổng lợi ích của cả $k$ ngày.

Hãy phân chia toàn bộ $n$ bài thành $k$ ngày sao cho tổng lợi ích là lớn nhất.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên $n$ và $k$ ($1\le k\le n\le 2000$) là số bài tập và số ngày.
• Dòng thứ hai chứa $n$ số nguyên $a_1,a_2,\dots ,a_n$ ($1\le a_i\le 2000$) là độ khó các bài tập theo thứ tự.

Dữ liệu ra

• Dòng đầu in ra tổng lợi ích lớn nhất.
• Dòng thứ hai in ra đúng $k$ số nguyên dương $t_1,t_2,\dots ,t_k$ (với $t_1+t_2+\cdots +t_k=n$), trong đó $t_j$ là số bài Polycarp giải trong ngày thứ $j$ để đạt được tổng lợi ích lớn nhất đó.

Nếu có nhiều cách phân chia cho cùng tổng lợi ích lớn nhất, in ra một cách bất kỳ.

Ràng buộc

• $1\le k\le n\le 2000$
• $1\le a_i\le 2000$

Ví dụ