Một dãy số gồm toàn các số nguyên 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 ta 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 và tổng của tất cả các số trong mỗi đoạn con đều không quá ~S~.

Cho dãy số nguyên dương ~a_1, a_2, \dots, a_N~. Ta gọi độ hoàn hảo của dãy số trên 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 chứa hai số nguyên dương ~N~ và ~S~ (~N \le 2 \times 10^5~, ~S \le 10^{15}~).
• Dòng thứ hai chứa ~N~ số nguyên dương ~a_1, a_2, \dots, a_N~ (~a_i \le \min(10^9, S)~ với mọi ~i=1 \dots N~).

Output

• Ghi ra một số nguyên dương duy nhất là kết quả của bài toán.

Sample Input 1

3 3
1 2 3

Sample Output 1

8