21766번 - 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}$

This subtask has an additional constraint: 

• $N \le 100$

This subtask has an additional constraint: 

• $N \le 10000$

This subtask has no additional constraints.