题目描述

有一个数组 a[1...n] ，你把数组复制 ${10}^{100}$ 次，然后把他们从左往右串在一起排成一行，就可以得到一个巨长的数组。求最小的下标 k , 使得 a[1]+a[2]+....+a[k] >= X。

输入格式

第一行，两个整数：n 和 X 。( 1 <= n <= 100000 , 1 <= X <= ${10}^{18}$ )

第二行，n 个整数，第 i 个整数是 a[i] ( 1 <= a[i] <= ${10}^9$ )

输出格式

一个整数。

样例

3 26
3 5 2

8

样例解释

把数组 a 复制 ${10}^{100}$ 次后，得到 { 3,5,2,3,5,2,3,5,2,3,5,2,..... } , 可以发现前 8 个数的和刚好超过 26 。