Phân bổ tài nguyên

Trong một vương quốc nọ, triều đình muốn phân bổ \(n\) đơn vị tài nguyên quý hiếm cho \(k\) vùng lãnh thổ. Các đơn vị tài nguyên này được xếp thành một hàng, đánh số từ \(1\) đến \(n\). Đơn vị thứ \(i\) có giá trị là \(v_i\). Triều đình quyết định phân bổ bằng cách chia hàng tài nguyên này thành \(k\) phần, mỗi phần là một đoạn các đơn vị tài nguyên đứng cạnh nhau. Mỗi phần sẽ được giao cho một vùng lãnh thổ. Tổng giá trị của một phần được tính bằng tổng giá trị của các đơn vị tài nguyên trong phần đó.

Để đảm bảo công bằng và hiệu quả, triều đình muốn tìm cách chia tài nguyên thành \(k\) phần sao cho hiệu số giữa giá trị lớn nhất và giá trị nhỏ nhất của các phần là nhỏ nhất có thể.

Yêu cầu: Cho trước \(n\) và \(k\) cùng với giá trị của \(n\) đơn vị tài nguyên. Hãy tìm cách chia chúng thành \(k\) phần liên tiếp sao cho hiệu số giữa giá trị của phần có tổng lớn nhất và phần có tổng nhỏ nhất là nhỏ nhất.

Input

• Dòng đầu tiên chứa hai số nguyên dương \(n\) và \(k\).
• Dòng thứ hai chứa \(n\) số nguyên dương \(v_1, v_2, \ldots, v_n\) (\(v_i \le 10^6\)).

Output

Một số nguyên duy nhất là hiệu số nhỏ nhất tìm được.

Example

6 3
7 4 6 1 2 10

2

Scoring

• Subtask 1 (25% số điểm): \(1 \leq k \leq n \le 20\).
• Subtask 2 (25% số điểm): \(1 \leq k \leq n \le 50\).
• Subtask 3 (25% số điểm): \(1 \leq k \leq n \le 100\).
• Subtask 4 (25% số điểm): \(1 \leq k \leq n \le 250\).