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 nn 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: a_1,a_2,...,a_n\). 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 nn số nguyên dương thể hiện \(a: a_1,a_2,...,a_n\).

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 \leq 103,m \leq 10^{18}\).
• Subtask \(2\) (\(20\%\) số điểm): \(n \leq 105,m \leq 200\).
• Subtask \(3\) (\(50\%\) số điểm): \(n \leq 10^5,m \leq 10^{18}\).
• Mọi test đều có \(ai \leq min(m,10^6),∀ i\)

Example

8 11
1 1 1 5 1 5 1 2 

9