Công ty tin học XYZ quyết định thuê K xe chở hàng có tải trọng như nhau để vận chuyển các container hàng. Có n kiện hàng được bốc dỡ lần lượt theo thứ tự từ 1 đến n, kiện hàng thứ i có trọng lượng ai. Hỏi rằng công ty cần thuê loại xe có tải trọng nhỏ nhất là bao nhiêu để cho thể vận chuyển hết số hàng?.

Input:

Dòng đầu tiên ghi hai số nguyên n k(1≤n,k≤10^5) Các dòng tiếp theo lần lượt ghi các số nguyên dương a1, a2, ..., an (ai≤~10^9~) Hai số liên tiếp trên cùng một dòng ghi cách nhau ít nhất một dấu cách.

Output:

Một số nguyên duy nhất là tải trọng tối thiểu của k xe tải.

Input

5 2

3 2 4 5 1

Output

9