Độ hoàn hảo

Một dãy số gồm toàn các số nguyên dương không lớn hơn \(S\) có độ đẹp được định nghĩa là một số nguyên dương \(X\) nhỏ nhất sao cho:

• Có thể chia dãy số ban đầu thành \(X\) đoạn con liên tiếp, mỗi số trong dãy thuộc một và chỉ một đoạn con.
• Tổng của tất cả các số trong mỗi đoạn con đều không quá \(S\).

Cho dãy \(A\) gồm \(N\) số nguyên dương \(a_1, a_2, \ldots, a_N\) (\(a_i \leq 10^9\) và \(a_i \leq S\) với \(\forall i=1..N\)). Ta gọi độ hoàn hảo của dãy số \(A\) là tổng độ đẹp của mọi dãy con liên tiếp của nó.

Yêu cầu: Tính độ hoàn hảo của dãy số đã cho.

Input

• Dòng đầu tiên chứa hai số nguyên dương \(N\) và \(S\) (\(N \leq 10^5, S \leq 10^{15}\))
• Dòng thứ hai chứa \(N\) số nguyên dương \(a_1, a_2, \ldots, a_N\) (\(0 < a_i \leq 10^9\), \(a_i \leq S\) với \(\forall j=1..N\))

Output

Số nguyên duy nhất là kết quả của bài toán.

Example

3 3
1 2 3

8

Scoring

• Có \(50\%\) số test ứng với \(50\%\) số điểm thỏa mãn: \(0 < N \leq 10^2\).
• Có \(20\%\) số test ứng với \(20\%\) số điểm thỏa mãn: \(10^2 < N \leq 10^3\).
• \(30\%\) số test còn lại ứng với \(30\%\) số điểm của bài không có ràng buộc gì thêm.