Cho dãy số nguyên không âm ~a_1~, ~a_2, ..., a_n~ và số nguyên dương ~k \le n~.

Hãy tìm cách chia dãy số thành ~k~ đoạn con liên tiếp sao cho chênh lệch giữa tổng giữa đoạn có tổng lớn nhất và đoạn có tổng nhỏ nhất là bé nhất.

INPUT

Dòng đầu chứa số nguyên dương ~n, k~ (~k \le n \le 250~, ~k \le 50~).

Dòng thứ hai chứa ~n~ số nguyên không âm ~a_i~ (~0 \le a_i \le 10^6~).

OUTPUT

Dòng duy nhất chứa kết quả bài toán.

SAMPLE INPUT

6 3
7 4 6 1 2 10

SAMPLE OUTPUT

2

Chia ~[7, 4]~, ~[6, 1, 2]~, ~[10]~.