Xếp chữ vào trang giấy

Một bài báo gồm \(N\) từ, đánh số từ \(1\) đến \(N\), từ thứ \(i\) chiếm \(w_i\) ô ký tự. Người ta phải xếp lần lượt các từ (theo đúng thứ tự \(1, 2, \dots, N\)) vào các dòng liên tiếp, mỗi dòng chứa một đoạn liên tiếp các từ và không có dòng nào rỗng. Tổng độ dài các từ trên một dòng không được vượt quá sức chứa \(L\) của dòng.

Với một dòng có tổng độ dài các từ là \(S\), số ô trống còn thừa là \(L - S\). Độ xấu của một cách chia trang là số ô trống thừa lớn nhất trong tất cả các dòng.

Hãy tìm cách chia trang sao cho độ xấu là nhỏ nhất và in ra độ xấu đó.

Input

• Dòng đầu chứa hai số nguyên dương \(N\) và \(L\).
• Dòng thứ hai chứa \(N\) số nguyên dương \(w_1, \dots, w_N\).

Output

• In ra một số nguyên: độ xấu nhỏ nhất có thể đạt được.

Constraints

• \(1 \le N \le 6000\)
• \(1 \le L \le 1000\)
• \(1 \le w_i \le L\)

Sample Input

5 7
4 1 3 3 2

Sample Output

3

Explanation

Chia thành ba dòng: \((4)\), \((1, 3)\), \((3, 2)\) với số ô thừa lần lượt là \(3, 3, 2\). Độ xấu là \(\max(3,3,2)=3\). Không có cách chia nào cho kết quả nhỏ hơn.