cíu bài chia táo

dề bài

Mẹ mới mua $n$ quả táo cho Vũ và Long. Vì là anh nên Vũ sẽ nhường cho Long phần nhiều hơn. Tuy nhiên, Vũ sẽ lợi dụng cơ hội này để ra cho Long một bài toán về chia táo để thử thách Long:

Vũ xếp $n$ quả táo thành 1 hàng, khối lượng các quả theo thứ tự trên hàng được thể hiện bằng mảng a:a1,a2,...,ana:a1​,a2​,...,an​. Long sẽ phải chia những quả táo này thành những nhóm nhỏ, sao cho mỗi nhóm sẽ gồm các quả liền kề nhau trong hàng và có tổng khối lượng của nhóm không được quá $m$. Với mỗi nhóm, quả có khối lượng lớn nhất sẽ thuộc về Vũ và Long sẽ được những quả còn lại.

Long ham ăn và luôn muốn ăn nhiều nhất có thể, bạn hãy giúp Long tìm ra cách chia như trên mà khối lượng táo Long có thể ăn là lớn nhất.

Input

• Dòng đầu tiên gồm 2 số nguyên $n$ và $m$.
• Dòng thứ 2 gồm $n$ số nguyên dương thể hiện a:a1,a2,...,ana:a1​,a2​,...,an​.

Output

• Hãy in ra khối lượng táo lớn nhất mà Long có thể ăn.

Scoring

• Subtask $1$ ($30\%$ số điểm): n≤103,m≤1018n≤103,m≤1018.
• Subtask $2$ ($20\%$ số điểm): n≤105,m≤200n≤105,m≤200.
• Subtask $3$ ($50\%$ số điểm): n≤105,m≤1018n≤105,m≤1018.
• Mọi test đều có ai≤min(m,106),∀iai​≤min(m,106),∀i