Văn bản là một dãy gồm N từ đánh số từ \(1\) đến \(N\). Từ thứ \(i\) có độ dài là \(w_i\). Phân trang là một cách xếp lần lượt các từ của văn bản vào dãy các dòng, mỗi dòng có độ dài tối đa là \(L\), sao cho tổng độ dài của các từ trên cùng một dòng không vượt quá \(L\).

Ta gọi hệ số phạt của mỗi dòng trong cách phân trang là hiệu số \(L - S\), trong đó \(S\) là tổng độ dài của các từ xếp trên dòng đó. Hệ số phạt của cách phân trang là giá trị lớn nhất trong số các hệ số phạt của các dòng.

Bạn hãy lập chương trình nhận đầu vào là danh sách các từ, tìm cách phân trang với hệ số phạt nhỏ nhất.

Dữ liệu vào

• Dòng \(1\) chứa \(2\) số nguyên dương \(N, L\) \((1 \le N \le 6000, 1 \le L \le 1000)\)
• Dòng tiếp theo chứa \(N\) số nguyên dương \(w_1, w_2, ..., w_N\) \((1 \le w_i \le L)\)

Dữ liệu ra

• In ra hệ số phạt nhỏ nhất

Input 1

4 5
3 2 2 4

Output 1

2

Giải thích:

Trong ví dụ trên ta có thể phân thành \(3\) dòng:

• Dòng \(1\): gồm một từ \((3)\) hệ số phạt dòng này là \(5 - 3 = 2\)
• Dòng \(2\): gồm hai từ \((2, 2)\) hệ số phạt là \(5 - 4 = 1\)
• Dòng \(3\): gồm một từ \((4)\) hệ số phạt là \(5 - 4 = 1\)
• Đáp án: \(max(2, 1, 1) = 2\)