Three Slices

You are given an array $A\_{0}$, $A\_{1}$, $A\_{2}$, $...$ , $A\_{N-1}$ of $N$ positive integers. Also, you are given an positive integer $K$. Your task is to find the largest positive integer $M$ such that the following condition is satisfied:

• There exists an integer $0 \le i \le N-3M$ such that

  1. $\sum\_{j=i}^{i+M-1}A\_{j} \le K$
  2. $\sum\_{j=i+M}^{i+2M-1}A\_{j} \le K$
  3. $\sum\_{j=i+2M}^{i+3M-1}A\_{j} \le K$

The first line contains two integers, $N$ and $K$. The second line contains $N$ integers, the array $A$ given in order.

Output a single positive integer denoting the largest possible $M$. If there is no such $M$, output $0$.

• $1 \le N \le 5 \times 10^{5}$
• $1 \le K \le 10^{9}$
• $1 \le A\_{i} \le 10^{9}$