Lịch sử của ngành hàng hải và vận tải biển luôn gắn liền với những bài toán tối ưu hóa logistics đầy thách thức. Từ thế kỷ XIX, khi con đường tơ lụa trên biển bùng nổ cùng sự ra đời của các tàu hơi nước, việc quản lý tải trọng tàu chở hàng đã trở thành yếu tố sống còn quyết định sự thành bại của các tập đoàn vận tải toàn cầu.

Tại các cảng biển hiện đại, hàng hóa được di chuyển liên tục trên hệ thống băng chuyền tự động theo một thứ tự cố định nghiêm ngặt. Để đảm bảo chuỗi cung ứng không bị đứt gãy, toàn bộ lô hàng trên băng chuyền phải được vận chuyển hoàn tất từ cảng xuất phát đến cảng đích trong đúng số ngày ~D~ quy định. Mỗi ngày, tàu chỉ có thể chở một khối lượng hàng hóa không vượt quá sức chứa tối đa ~C~ của nó và hàng trên băng chuyền phải được xếp lên tàu lần lượt từ trái sang phải mà không được phép thay đổi vị trí hay chia nhỏ từng kiện.

• Thứ tự cố định: Các kiện hàng trên băng chuyền phải được chất lên tàu theo đúng thứ tự xuất hiện ban đầu.
• Tải trọng tối đa: Tổng khối lượng hàng hóa chất lên tàu trong một ngày không được vượt quá sức chứa tối đa của tàu.
• Giới hạn thời gian: Toàn bộ quá trình vận chuyển bắt buộc phải hoàn thành trong đúng hoặc ít hơn ~D~ ngày.

Trong bài tập này, bạn được cấp một mảng ~W~ gồm ~N~ phần tử đại diện cho khối lượng của từng kiện hàng và số nguyên ~D~. Hãy viết chương trình xác định tải trọng tối thiểu của tàu!

Input

• Dòng ~1~: Chứa hai số nguyên ~N~ và ~D~ - số lượng kiện hàng và số ngày tối đa.
• Dòng ~2~: Chứa ~N~ số nguyên ~W_1, W_2, \dots, W_N~ - khối lượng của từng kiện hàng trên băng chuyền.
• Lưu ý: ~1 \le D \le N \le 10^5~, ~1 \le W_i \le 10^9~.

Output

• In ra một dòng duy nhất chứa một số nguyên: Sức chứa (tải trọng) tối thiểu của tàu để vận chuyển xong toàn bộ hàng hóa trong đúng hoặc ít hơn ~D~ ngày.

Example Input 1

10 5
1 2 3 4 5 6 7 8 9 10

Example Output 1

15

Example Input 2

6 3
3 2 2 4 1 4

Example Output 2

6

Example Input 3

5 4
1 2 3 1 1

Example Output 3

3