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à wi (i=1, 2,... N). 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 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.Tìm cách phân trang với hệ số phạt nhỏ nhất.
Input
- Dòng 1 chứa 2 số nguyên dương N, L (N<=6000,L<=1000)
- Dòng thứ i trong số N dòng tiếp theo chứa số nguyên dương wi (wi<=L), i=1, 2,.., N
Output
In ra hệ số phạt nhỏ nhất
Ví dụ
Input:
4 5
3
2
2
4
Output:
2
Solution: PTRANG
Code: PTRANG
