Phòng thí nghiệm Trí tuệ nhân tạo có ~N~ tác vụ tính toán cần xử lý có khối lượng công việc lần lượt là ~T_1,T_2,…,T_N~. Các tác vụ này phải được chia vào tối đa ~K~ máy chủ theo nguyên tắc phân đoạn liên tiếp (máy chủ 1 xử lý một số tác vụ đầu tiên liên tiếp, máy chủ 2 xử lý các tác vụ liên tiếp tiếp theo,...; một tác vụ không được chia nhỏ cho 2 máy chủ).

Tất cả các máy chủ đều có cùng tốc độ xử lý là ~S~ (khối lượng công việc xử lý được trong 1 giây). Thời gian để một máy chủ hoàn thành phần việc được giao là (Tổng khối lượng công việc của máy đó)/(S) giây. Các máy chủ chạy song song nên toàn bộ hệ thống hoàn thành khi tất cả các máy chủ đều chạy xong.

Yêu cầu: Để toàn bộ hệ thống hoàn thành công việc trong thời gian không quá ~1~ giây trên mỗi máy chủ được phân công (tức là không có máy chủ nào phải nhận tổng khối lượng công việc vượt quá ~S~), hãy tìm tốc độ xử lý tối thiểu ~S~ (với ~S~ là số nguyên dương) cần thiết lập cho dàn máy chủ.

Đầu vào

Dữ liệu từ tập tin OLP2026_04.INP gồm 2 dòng:

• Dòng 1 chứa hai số nguyên dương ~N,K~ (~1≤K≤N≤200 000~).
• Dòng 2 chứa ~N~ số nguyên dương ~T_1,T_2,…,T_N~ (~1≤T_i≤10^9~).

Đầu ra

Kết quả ghi vào tệp OLP2026_04.OUT gồm một số nguyên duy nhất là giá trị ~S~ nhỏ nhất tìm được.

Ví dụ

Input

5 3
4 2 7 3 5

Output

8

Subtask

• Subtask 1 (20%): N ≤ 20.
• Subtask 2 (30%): N ≤ 2 000.
• Subtask 3 (50%): N ≤ 200 000.