Bạn được cho một mảng tuần hoàn gồm \(n\) giá trị. Mỗi phần tử có 2 hàng xóm, các phần tử ở vị trí \(n\) và \(1\) cũng được coi là hàng xóm.

Nhiệm vụ của bạn là chia mảng thành các mảng con sao cho tổng các số trong mỗi mảng con không lớn hơn \(k\). Hỏi số lượng mảng con tối thiểu là bao nhiêu?

Input

• Dòng đầu tiên chứa số nguyên \(n\) và \(k\).
• Dòng tiếp theo chứa n số nguyên \(x_1, x_2, ..., x_n\). Các phần tử trong mảng không lớn hơn \(k\).

Output

• In ra một số: số mảng con tối thiểu.

Constraints

• \(1 \le n \le 2 \times 10^5\).
• \(1 \le x_i \le 2 \times 10^9\).
• \(1 \le k \le 2 \times 10^{18}\).

Example

Sample input

8 5  
2 2 2 1 3 1 2 1

Sample output

3

Note

• Giải thích: chúng ta có thể tạo ra \(3\) mảng con: \([2,2,1]\), \([3,1]\) và \([2,1,2]\) (nhớ rằng mảng là tuần hoàn).