Bran and his older sister Arya are from the same house. Bran like candies so much, so Arya is going to give him some Candies.

At first, Arya and Bran have 0 Candies. There are n days, at the i-th day, Arya finds a_{i} candies in a box, that is given by the Many-Faced God. Every day she can give Bran at most 8 of her candies. If she don't give him the candies at the same day, they are saved for her and she can give them to him later.

Your task is to find the minimum number of days Arya needs to give Bran k candies before the end of the n-th day. Formally, you need to output the minimum day index to the end of which k candies will be given out (the days are indexed from 1 to n).

Print -1 if she can't give him k candies during n given days.


-----Input-----

The first line contains two integers n and k (1 ≤ n ≤ 100, 1 ≤ k ≤ 10000).

The second line contains n integers a_1, a_2, a_3, ..., a_{n} (1 ≤ a_{i} ≤ 100).


-----Output-----

If it is impossible for Arya to give Bran k candies within n days, print -1.

Otherwise print a single integer — the minimum number of days Arya needs to give Bran k candies before the end of the n-th day.


-----Examples-----
Input
2 3
1 2

Output
2
Input
3 17
10 10 10

Output
3
Input
1 9
10

Output
-1


-----Note-----

In the first sample, Arya can give Bran 3 candies in 2 days.

In the second sample, Arya can give Bran 17 candies in 3 days, because she can give him at most 8 candies per day.

In the third sample, Arya can't give Bran 9 candies, because she can give him at most 8 candies per day and she must give him the candies within 1 day.

Difficulty: interview

Starter code:

Solutions:
#!/bin/python

n, k = list(map(int, input().split()))
p = list(map(int, input().split()))

a, b = 0, 0
for i in range(n):
    a += p[i]
    x = min(8, a)
    b += x
    a -= x
    if b >= k:
        print(i+1)
        break
else:
    print(-1)


def list_input():
    return list(map(int,input().split()))
def map_input():
    return list(map(int,input().split()))
def map_string():
    return input().split()
    
n,k = map_input()
a = list_input()
cur = 0
cnt = 1
for i in a:
  cur += i
  if cur >= 8:
    cur -= 8
    k -= 8
  else:
    k -= cur
    cur = 0
  if k <= 0:
    break
  cnt += 1
if k <= 0:
  print(cnt)
else:
  print(-1)
  


N,K = list(map(int,input().split()))
a = [int(i) for i in input().split()]

store = 0
s = 0
for day in range(N):
    store+=a[day]
    x = min(8,store)
    s +=x
    store -=x
    if s>=K:
        break

if s>=K:
    print(day+1)
else:
    print(-1)


n,k=map(int,input().split())
l=list(map(int,input().split()))
cur=0
for i in range(n):
    cur+=l[i]
    k-=min(cur,8)
    cur-=min(cur,8)
    if k<=0:
        print(i+1)
        break
else:
    print(-1)

n, k = map(int, input().split())

l = list(map(int, input().split()))

cnt = 0
ans = 0

for a in l:
	ans += 1
	cnt += a;
	gt = min(8, min(cnt, k))
	k -= gt
	cnt -= gt
	if k == 0:
		print(ans)
		return

print(-1)

from sys import stdin, stdout

n, k = list(map(int, stdin.readline().split()))
values = list(map(int, stdin.readline().split()))
cnt = 0
sweet = 0

for i in range(n):
    cnt += values[i]
    
    v = min(min(cnt, 8), k - sweet)
    sweet += v 
    cnt -= v
    
    if sweet == k:
        stdout.write(str(i + 1))
        break
else:
    stdout.write('-1')


n,k = list(map(int, input().split()))
A = list(map(int, input().split()))

arya = 0
bran = 0

for i,a in enumerate(A):
    arya += a 
    bran += min(arya, 8)
    arya -= min(arya, 8)
    if bran >= k:
        print(i+1)
        return

print(-1)


n,k=list(map(int,input().split()))
l=list(map(int,input().split()))
days=0
stock=0
while(k>0 and days<n):
	stock+=l[days]
	k-=min(stock,8)
	stock-=min(stock,8)
	days+=1
if(k>0):
	print(-1)
else:
	print(days)




def main():
    n, k = (int(x) for x in input().split())
    xs = [int(x) for x in input().split()]

    counter = 0
    arya = 0
    bran = 0

    for i, x in enumerate(xs):
        arya += x

        give = min(arya, 8)
        arya -= give
        bran += give

        if bran >= k:
            break

    if bran >= k:
        print(i+1)
    else:
        print(-1)


def __starting_point():
    main()



__starting_point()

n, m = list(map(int, input().split()))
z = list(map(int, input().split()))
ans = 0
ctr = 0
left = 0
while ctr < m:
    if ans >= n:
        print(-1)
        return
    else:
        z[ans] += left
        ctr += min(8, z[ans])
        left = z[ans] - min(8, z[ans])
    ans += 1
print(ans)


n, k = list(map(int, input().split()))
a = list(map(int, input().split()))

tot = 0
remain = 0
i = 0
while i < n:
    if a[i] + remain <= 8:
        tot += a[i] + remain
        remain = 0
    else:
        tot += 8
        remain += a[i] - 8
    if tot >= k:
        print(i+1)
        break
    i += 1
if i == n:
    print(-1)


n, k = list(map(int, input().split()))
a = list(map(int, input().split()))

ans = -1
ca = 0
cb = 0
for i in range(n):
    ca += a[i]
    c = min(ca, 8)
    ca -= c
    cb += c
    if k <= cb:
        ans = i + 1
        break

print(ans)


def main():
	n, k = list(map(int, input().split()))
	candies = list(map(int, input().split()))

	rest = 0
	given = 0
	for i in range(n):
		rest += candies[i]
		if rest >= 8:
			given += 8
			rest -= 8
		else:
			given += rest
			rest = 0

		if given >= k:
			print(i + 1)
			break

		if i == n - 1:
			print(-1)

def __starting_point():
	main()
__starting_point()

q,w=list(map(int,input().split()))
a=list(map(int,input().split()))
if (w>8*q)|(w>sum(a)):
    print(-1)
else:
    s=0
    i=0
    while (w>0)&(i<q):
        s+=a[i]
        w-=min(8,s)
        s-=min(8,s)
        i+=1
    if w<=0:
        print(i)
    else:
        print(-1)


from sys import stdin
i = [[int(y) for y in x.rstrip().split()] for x in stdin.readlines()]
k = i[0][1]
days = i[1]
remaining = 0
for i,x in enumerate(days):
    k-= min(8,x+remaining)
    remaining = x+remaining - min(8,x+remaining)
    if k<=0:
        print(i+1)
        break
else:
    print (-1)

#py3com
#pycom
#ciphereck
#t=int(input())
#n=list(map(int,input().split()))
#a,b=map(int,input().split())
#print(n)
#print(a)
# n.sort()
#print(*ans) to print list with spaces without brackets
n,k=list(map(int,input().split()))
a=list(map(int,input().split()))
d=0
c=0
t=0
while t<k:
  if d==n:
    d+=1
    break
  c+=a[d]
  g=min(8,c)
  t+=g
  d+=1
  c=c-g
if d==n+1:
  print(-1)
else:
  print(d)


import sys

def r():
    return list(map(int, input().split()))

n, k = list(map(int, input().split()))
a = r()

sum = 0
cnt = 0
for i in range(n):
    sum += a[i]
    cnt += min(8, sum)
    sum = max(0, sum-8)
    if (cnt >= k):
        print(i+1)
        return

print(-1)


def main():
    N, K = list(map(int, input().split()))
    nums = list(map(int, input().split()))

    aran = 0
    bran = 0
    for n in range(N):
        aran += nums[n]
        x = min(aran, 8)
        aran -= x
        bran += x
        if bran >= K:
            print(n+1)
            return

    print(-1)
    return
        

def __starting_point():
    # nonlocal stime
    # stime = time.clock()
    main()


__starting_point()

n, k = input().split()
n, k = int(n), int(k)
array = list(map(int, input().split()))

total = 0
saved = 0
found = False

for day in range(n):
    saved += array[day]
    
    given = min(saved, 8)
    total += given
    saved -= given

    if total >= k:
        found = True
        print(day+1)
        break
    
if not found:
    print(-1)


n, k = map(int, input().split())
a = list(map(int, input().split()))

s = 0
res = 0
ans = -1
for i in range(n):
    s += a[i]
    res += min(s, 8)
    s -= min(s, 8)
    if res >= k:
        ans = i + 1
        break

print(ans)

split = lambda: list(map(int, input().split()))
a, b = split()
candies = split()
p = q = 0
for x in range(a):
    p += candies[x]
    s = min(8, p)
    p -= s
    q += s
    if q >= b:
        print(x + 1)
        break
else:
    print(-1)

#!/usr/bin/env python3
# -*- coding: utf-8 -*-

import sys
import re
import math
import collections
import itertools
import functools

DEBUG = True
DEBUG = False

def dbg(*args):
    if DEBUG:
        print("DBG: ", file=sys.stderr, end="")
        print(*args, file=sys.stderr)



def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))

    candy_a = 0;
    candy_b = 0;
    for day in range(N):
        candy_a += A[day]
        if candy_a > 8:
            candy_b += 8
            candy_a -= 8
        else:
            candy_b += candy_a
            candy_a  = 0

        if candy_b >= K:
            print(day+1)
            return

    print(-1)

def __starting_point(): main()

__starting_point()

n, k = list(map(int, input().split()))
cnt, day = 0, 0
a = list(map(int, input().split()))
while k > 0:
    try:
        cnt += a[day]
    except IndexError:
        print(-1)
        return
    x = min(8, cnt)
    cnt -= x
    k -= x
    day += 1
print(day)



import sys, os

n, k = map(int, input().split())
data =list(map(int, input().split()))
res = 0
resu = 0
for i in range(n):
    res += data[i]
    r = min(res, 8)
    res -= r
    resu += r
    if resu >= k:
        print(i + 1)
        return
        sys.exit
        os.abort()
print(-1)

n, k = list(map(int, input().split()))
a = list(map(int, input().split()))
a1, a2 = 0, 0
ans = False

for i in range(n):
    a1 += a[i]
    a2 += min(8, a1)
    a1 -= min(8, a1)
    if a2 >= k:
        ans = i + 1
        break

if ans:
    print(ans)
else:
    print(-1)