Để trang trí lễ hội sản xuất thủ công mỹ nghệ, Ban tổ chức Lễ hội đặt xưởng gia công làm những khung sắt để trang trí. Nhằm đẩy nhanh tiến độ hoàn thành công việc, xưởng gia công đã phân chia công việc thành ~N~ công việc, công việc thứ ~i~ hoàn thành trong thời gian ~t_i~ (~1 \le i \le N~; ~1 \le t_i \le 10^{12}~, ~t_i~ là số nguyên). Các công việc được thực hiện trên ~M~ máy (các máy có công suất như nhau và đều có thể thực hiện được mọi công việc trong số ~N~ công việc), mỗi công việc được làm liên tục cho đến khi xong.

Tổ chức ~M~ máy để thực hiện ~N~ công việc sao cho thời gian hoàn thành của tất cả các công việc là ngắn nhất.

Input

• Dòng 1: chứa hai số nguyên ~N, M~ (~0 < N, M \le 100~).
• Dòng 2: ghi ~N~ số nguyên ~t_1, t_2, \dots, t_N~.

Output

• Ghi ra một số duy nhất là thời gian ngắn nhất để hoàn thành công việc.

Sample Input 1

6 3
2 5 8 1 5 1

Sample Output 1

8