#P144. [CTFPC-1] Expressway

[CTFPC-1] Expressway

题目背景

2se 23 年国庆的时候在高速上堵了半天,今年春节他不想再这样了……

题目描述

高速真堵啊!

我们假设高速拥堵是不动态的,那么我们可以将一次行程分为 nn 个不同的行程段,通过每个行程段要 AiA_i 分钟,那么请选择一个最小的 kk,使得从 kk 段进入高速,到达段 nn 不会超过时间 tt

或者说,把问题简化一下,就是给你 nn 个数,求一个最小的 k (1kn)k\ (1\le k\le n),使得:

i=knAit\sum_{i=k}^nA_i\le t

同时,我们保证 kk 一定存在。

输入格式

第一行两个整数 n (1n105)n\ (1\le n\le 10^5)t(1t1018)t(1\le t\le 10^{18})

第二行 nn 个整数,第 ii 个整数为 Ai (1Ai1018)A_i\ (1\le A_i\le 10^{18})

输出格式

共一行,为 kk

样例

10 5
1 1 1 1 1 1 1 1 1 1
6