Công ty HP vừa thiết kế một loại robot thông minh mới. Để đánh giá khả năng tự vận hành của robot, người ta tạo ra một bức tường từ ݊ cột các khối lập phương, các cột đặt cạnh nhau, bề dày bức tường là 1, độ cao cột thứ \(i\) là ܽ\(a_i\) (do ܽ\(a_i\) khối lập phương tạo lên). Có ݉\(m\) robot tham gia thử nghiệm. Trước tiên người ta chia ݊\(n\) cột thành ݉\(m\) đoạn bằng ݉\(m − 1\) điểm cắt ݇\(k_1, ݇k_2, . . , ݇k_{m-1} (݇k_0 = 0 < k_1 < ... < ݇k_{m-1} < k_m = n)\). Robot thứ ݅ được giao nhiệm vụ xếp lại đoạn từ cột ݇\(k_{i-1} + 1\) đến cột ݇\(k_i\) sao cho các cột trong đoạn có độ cao bằng nhau. Robot chỉ có thể thực hiện một trong hai loại thao tác, mỗi thao tác mất 1 đơn vị thời gian.

• Thao tác 1: Lấy khối trên cùng của một cột trong đoạn được giao để bỏ đi;
• Thao tác 2: Lấy một khối mới, đặt khối đó lên trên cùng của một cột trong đoạn được giao.

Thời gian kết thúc thử nghiệm là thời gian mà robot cuối cùng hoàn thành xong nhiệm vụ.

Yêu cầu: Cho \(a_1, a_2, ..., a_n\) và ݉\(m\). Hãy tìm \(m− 1\) điểm cắt để chia cột thành ݉\(m\) đoạn sao cho thời gian thử nghiệm là nhanh nhất, biết các robot đều thực hiện các thao tác tối ưu.

Input

Vào từ thiết bị nhập chuẩn:

• Dòng đầu chứa hai số nguyên \(n, m\);
• Dòng thứ hai gồm ݊\(n\) số nguyên không âm \(a_1, a_2, ..., a_n (a_i \le 10^6)\)

Output

• Ghi ra thiết bị ra chuẩn một dòng chứa một số nguyên là thời gian ít nhất để thử nghiệm.

Scoring

• Subtask \(1\) (\(25\%\) số điểm): \(m = 1; n \le 10\);
• Subtask \(2\) (\(25\%\) số điểm): \(m = 2; n \le 1000\);
• Subtask \(3\) (\(25\%\) số điểm): ݉\(m \le n; n \le 100\);
• Subtask \(4\) (\(25\%\) số điểm): ݉\(m\le n; n \le 1000\).

Example

6 2
1 1 2 3 4 3

1