给你一个由 $N$ 个正整数组成的数组 $A_0, A_1, A_2, \dots, A_{N-1}$。此外，还给你一个正整数 $K$。你的任务是找到最大的正整数 $M$，使得满足以下条件：

• 存在一个整数 $0 \le i \le N - 3M$，满足以下三个条件：

  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$

输入格式

第一行包含两个整数 $N$ 和 $K$。第二行包含 $N$ 个整数，表示按顺序给出的数组 $A$。

输出格式

输出一个正整数，表示最大的可能 $M$。如果不存在这样的 $M$，则输出 $0$。

数据范围

• $1 \le N \le 5 \times 10^5$
• $1 \le K \le 10^9$
• $1 \le A_i \le 10^9$

子任务

子任务 1 (10 分)

该子任务满足以下附加限制：

• $N \le 100$

子任务 2 (20 分)

该子任务满足以下附加限制：

• $N \le 10000$

子任务 3 (70 分)

该子任务没有附加限制。

样例

输入样例 1

10 10
3 7 4 3 1 3 5 2 5 1

输出样例 1

2