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\)

Constraints

• \(1 \leq n \leq 2 \cdot 10^5\)
• \(1 \leq x_i \leq 2 \cdot 10^9\)
• \(1 \leq k \leq 2 \cdot 10^{18}\)

Output

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

Example

8 5
2 2 2 1 3 1 2 1

3