Cho mảng \(A\) có \(n\) số nguyên và \(k\), chia mảng \(A\) thành \(k\) phần (không rỗng) sao cho tổng lớn nhất của \(k\) phần là nhỏ nhất.

Dữ liệu vào

• Dòng 1: \(n\) và \(k\)
• Dòng 2: \(n\) số nguyên của mảng \(A\)

Dữ liệu ra

• Đáp án bài toán

Ràng buộc

• \(1 \le n \le 3000\)
• \(0 \le a[i] \le 10^6\)
• \(1 \le k \le min(50,n)\)

Input 1

5 2
7 2 5 10 8

Output 1

18

Giải thích

Chia mảng thành 2 phần [7,2,5] và [10,8] => tổng lớn nhất là 18