题目描述

给定n个正整数组成的数列a1，a2，⋯，an和一个整数m。求出这个数列中的一个子区间[i, j]，也就是在这个数列中连续的数字ai，ai+1，⋯，aj-1，aj，使得这个子区间的和在不超过m的情况下最大。如果有多个区间符合要求，请输出i最小的那一个。

输入格式

第一行，两个整数n，m(1≤n≤4*10^6, 1≤m≤10^9)；

第二行，n个整数a1，a2，⋯，an(1≤ai≤10^6)。

一行，三个整数，表示符合题意的区间的左端点、右端点和累加和。

5 10
2 3 4 5 6

1 3 9

时间1000ms，内存256MiB