Ngọt - Thấy Chưa (Official Music Video)

Thấy chưa thấy chưa em ?

Có thể bạn chưa biết (hoặc biết rồi cũng kệ) thì ở trong MV có hai phiên bản Thắng chính là một Thắng tóc ngắn và một Thắng tóc dài.

Hiện tại, bằng các thủ thuật nhân bản siêu tinh vi phiên bản Thắng tóc dài đã được nhân giống lên $n$ người và tất cả $n$ người đều muốn đi cắt tóc ở tiệm salon Mặn, tiệm salon Mặn có $\frac{n}{k}$ máy cắt hãng Chua quản lí đúng $n$ ghế cắt (máy cắt thứ $1$ quản lí các ghế $1,\ 2,\dots\ ,k$ và cứ liên tiếp vậy tới máy thứ $k$, dữ liệu đảm bảo $n\ \vdots\ k$), mỗi máy cắt sẽ có độ dài tóc tối đa được đặt trước, có nghĩa rằng, với mỗi máy cắt thì tổng số lượng tóc nó cắt không thể vượt qua độ dài tóc tối đa được đặt trước này. Mỗi phiên bản Thắng (tóc dài) thứ $i$ sẽ muốn cắt $a_i\ cm$ tóc, các máy cắt hãng Chua của tiệm salon do cùng được cài một hiện điều hành Cay nên chỉ có thể cài đặt được số $cm$ tóc tối đa mỗi mắt cắt được là như nhau, bạn - người của công ti Đắng - công ti sản xuất máy cắt Chua được cài hệ điều hành Cay sử dụng ở tiệm salon Mặn cắt tóc cho Thắng của ban nhạc Ngọt hãy tìm số $cm$ tóc tối đa mỗi máy cắt được sao cho phiên bản Thắng (tóc dài) nào cũng có thể được cắt số lượng tóc mong muốn nhé.

Input

• Dòng đầu tiên gồm hai số nguyên $n$ và $k$ - số lượng phiên bản Thắng (tóc dài) và số lượng máy cắt Chua. $(1\leq k\leq n\leq 10^5,\ n\ \vdots\ k)$
• Dòng thứ hai gồm dãy số nguyên $a$ gồm $n$ phần tử với phần tử $a_i$ chính là độ dài cần cắt của phiên bản Thắng (tóc dài) thứ $i$. $(a_i\leq 10^6)$

Output

• Gồm một số nguyên duy nhất là độ dài tối đa tối thiểu cần đặt cho mỗi máy cắt chua để mọi phiên bản Thắng (tóc dài) được cắt đúng số tóc mình mong muốn.

Subtasks

• Subtask $1$: Đảm bảo $n\leq 100$. ($98$ điểm)
• Subtask $2$: Không có ràng buộc gì thêm. ($2$ điểm)

Example

4 2
1 5 3 4

7