F. GukiZ Height
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

GukiZ loves hiking in the mountains. He starts his hike at the height 0 and he has some goal to reach, initially equal to h.

The mountains are described by a sequence of integers A0, A1, ..., An - 1. In the first day GukiZ will change his height by A0, in the second day by A1, and so on. Mountains are a regular structure so the pattern repeats after the first n days. In general, in the i-th day GukiZ will change his height by A(i - 1)%n.

Additionally, GukiZ will become more and more tired and in the i-th day his goal will decrease by i. For example, after first three days his goal will be equal to h - 1 - 2 - 3 = h - 6.

Note that A may contain negative elements, what represents going down from some hill. Moreover, GukiZ's height may become negative, and so does his goal!

You can assume that both GukiZ's height and goal change at the same moment (immediately and simultaneously) in the middle of a day.

Once GukiZ is at the height not less than his goal, he ends his hike. Could you calculate the number of days in his hike?

Input

The first line of the input contains two integers n and h (1 ≤ n ≤ 105, 1 ≤ h ≤ 109) — the length of the array A and the initial goal, respectively.

The second line contains n integers A0, A1, ..., An - 1 ( - 109 ≤ Ai ≤ 109).

Output

In a single line print the number of days in the GukiZ's hike.

It can be proved that for any valid input the answer exists.

Examples
Input
3 45
7 -4 5
Output
7
Input
1 1
0
Output
1
Note

GukiZ starts at height 0 with goal 45. We can describe his hike as follows:

  1. After the first day he is at height 7 and his goal is 44.
  2. Height 3, goal 42.
  3. Height 8, goal 39.
  4. Height 15, goal 35.
  5. Height 11, goal 30.
  6. Height 16, goal 24.
  7. Height 23, goal 17.

After the 7-th day Gukiz's height is not less than his goal so he ends his hike.