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 ai 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 a1, a2, a3, ..., an (1 ≤ ai ≤ 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.
import java.io.File;import java.io.FileInputStream;import java.io.FileNotFoundException;
import java.io.IOException;import java.io.PrintStream;import java.io.PrintWriter;
import java.security.AccessControlException;import java.util.Arrays;import java.util.Collection;
import java.util.Comparator;import java.util.List;import java.util.Map;import java.util.Objects;
import java.util.Scanner;import java.util.TreeMap;import java.util.function.Function;
import java.util.stream.Collectors;import java.util.stream.IntStream;import java.util.stream.LongStream;
import java.util.stream.Stream;public class _p000839A {static public void main(final String[] args) 
throws IOException{p000839A._main(args);}
static private class p000839A extends Solver{public p000839A(){nameIn="in/900/p000839A.in"
;singleTest=true;}@Override public void solve()throws IOException{int n=sc.nextInt
();int k=sc.nextInt();if(sc.hasNextLine()){sc.nextLine();}int br=0;int ar=0;int 
res=0;for(int _if0=0;_if0<n;_if0++){int a=sc.nextInt();if(br<k){ar+=a;int d=Math
.min(k-br,Math.min(ar,8));br+=d;ar-=d;res++;}}if(sc.hasNextLine()){sc.nextLine()
;}pw.println(br==k?res:-1);}static public void _main(String[]args)throws IOException
{new p000839A().run();}}static private class Pair<K,V>{private K k;private V v;public
 Pair(final K t,final V u){this.k=t;this.v=u;}public K getKey(){return k;}public
 V getValue(){return v;}}static private abstract class Solver{protected String nameIn
=null;protected String nameOut=null;protected boolean singleTest=false;protected
 boolean preprocessDebug=false;protected boolean doNotPreprocess=false;protected
 PrintStream debugPrintStream=null;protected Scanner sc=null;protected PrintWriter
 pw=null;final static String SPACE=" ";final static String SPACES="\\s+";private
 void process()throws IOException{if(!singleTest){int t=lineToIntArray()[0];while
(t-->0){solve();}}else{solve();}}abstract protected void solve()throws IOException
;protected String[]lineToArray()throws IOException{return sc.nextLine().trim().split
(SPACES);}protected int[]lineToIntArray()throws IOException{return Arrays.stream
(lineToArray()).mapToInt(Integer::valueOf).toArray();}protected long[]lineToLongArray
()throws IOException{return Arrays.stream(lineToArray()).mapToLong(Long::valueOf
).toArray();}protected void run()throws IOException{boolean done=false;try{if(nameIn
!=null && new File(nameIn).exists()){try(FileInputStream fis=new FileInputStream
(nameIn);PrintWriter pw0=select_output();){done=true;sc=new Scanner(fis);pw=pw0;
process();}}}catch(IOException ex){}catch(AccessControlException ex){}if(!done){
try(PrintWriter pw0=select_output();){sc=new Scanner(System.in);pw=pw0;process()
;}}}private PrintWriter select_output()throws FileNotFoundException{if(nameOut!=
null){return new PrintWriter(nameOut);}return new PrintWriter(System.out);}public
 static Map<Integer,List<Integer>>mapi(final int[]a){return IntStream.range(0,a.
length).collect(()->new TreeMap<Integer,List<Integer>>(),(res,i)->{if(!res.containsKey
(a[i])){res.put(a[i],Stream.of(i).collect(Collectors.toList()));}else{res.get(a[
i]).add(i);}},Map::putAll);}public static Map<Long,List<Integer>>mapi(final long
[]a){return IntStream.range(0,a.length).collect(()->new TreeMap<Long,List<Integer
>>(),(res,i)->{if(!res.containsKey(a[i])){res.put(a[i],Stream.of(i).collect(Collectors
.toList()));}else{res.get(a[i]).add(i);}},Map::putAll);}public static<T>Map<T,List
<Integer>>mapi(final T[]a){return IntStream.range(0,a.length).collect(()->new TreeMap
<T,List<Integer>>(),(res,i)->{if(!res.containsKey(a[i])){res.put(a[i],Stream.of(
i).collect(Collectors.toList()));}else{res.get(a[i]).add(i);}},Map::putAll);}public
 static<T>Map<T,List<Integer>>mapi(final T[]a,Comparator<T>cmp){return IntStream
.range(0,a.length).collect(()->new TreeMap<T,List<Integer>>(cmp),(res,i)->{if(!res
.containsKey(a[i])){res.put(a[i],Stream.of(i).collect(Collectors.toList()));}else
{res.get(a[i]).add(i);}},Map::putAll);}public static Map<Integer,List<Integer>>mapi
(final IntStream a){int[]i=new int[]{0};return a.collect(()->new TreeMap<Integer
,List<Integer>>(),(res,v)->{if(!res.containsKey(v)){res.put(v,Stream.of(i[0]).collect
(Collectors.toList()));}else{res.get(v).add(i[0]);}i[0]++;},Map::putAll);}public
 static Map<Long,List<Integer>>mapi(final LongStream a){int[]i=new int[]{0};return
 a.collect(()->new TreeMap<Long,List<Integer>>(),(res,v)->{if(!res.containsKey(v
)){res.put(v,Stream.of(i[0]).collect(Collectors.toList()));}else{res.get(v).add(
i[0]);}i[0]++;},Map::putAll);}public static<T>Map<T,List<Integer>>mapi(final Stream
<T>a,Comparator<T>cmp){int[]i=new int[]{0};return a.collect(()->new TreeMap<T,List
<Integer>>(cmp),(res,v)->{if(!res.containsKey(v)){res.put(v,Stream.of(i[0]).collect
(Collectors.toList()));}else{res.get(v).add(i[0]);}},Map::putAll);}public static
<T>Map<T,List<Integer>>mapi(final Stream<T>a){int[]i=new int[]{0};return a.collect
(()->new TreeMap<T,List<Integer>>(),(res,v)->{if(!res.containsKey(v)){res.put(v,
Stream.of(i[0]).collect(Collectors.toList()));}else{res.get(v).add(i[0]);}},Map::
putAll);}public static List<int[]>listi(final int[]a){return IntStream.range(0,a
.length).mapToObj(i->new int[]{a[i],i}).collect(Collectors.toList());}public static
 List<long[]>listi(final long[]a){return IntStream.range(0,a.length).mapToObj(i->
new long[]{a[i],i}).collect(Collectors.toList());}public static<T>List<Pair<T,Integer
>>listi(final T[]a){return IntStream.range(0,a.length).mapToObj(i->new Pair<T,Integer
>(a[i],i)).collect(Collectors.toList());}public static List<int[]>listi(final IntStream
 a){int[]i=new int[]{0};return a.mapToObj(v->new int[]{v,i[0]++}).collect(Collectors
.toList());}public static List<long[]>listi(final LongStream a){int[]i=new int[]
{0};return a.mapToObj(v->new long[]{v,i[0]++}).collect(Collectors.toList());}public
 static<T>List<Pair<T,Integer>>listi(final Stream<T>a){int[]i=new int[]{0};return
 a.map(v->new Pair<T,Integer>(v,i[0]++)).collect(Collectors.toList());}public static
 String join(final int[]a){return Arrays.stream(a).mapToObj(Integer::toString).collect
(Collectors.joining(SPACE));}public static String join(final long[]a){return Arrays
.stream(a).mapToObj(Long::toString).collect(Collectors.joining(SPACE));}public static
<T>String join(final T[]a){return Arrays.stream(a).map(v->Objects.toString(v)).collect
(Collectors.joining(SPACE));}public static<T>String join(final T[]a,final Function
<T,String>toString){return Arrays.stream(a).map(v->toString.apply(v)).collect(Collectors
.joining(SPACE));}public static<T>String join(final Collection<T>a){return a.stream
().map(v->Objects.toString(v)).collect(Collectors.joining(SPACE));}public static
<T>String join(final Collection<T>a,final Function<T,String>toString){return a.stream
().map(v->toString.apply(v)).collect(Collectors.joining(SPACE));}public static<T
>String join(final Stream<T>a){return a.map(v->Objects.toString(v)).collect(Collectors
.joining(SPACE));}public static<T>String join(final Stream<T>a,final Function<T,
String>toString){return a.map(v->toString.apply(v)).collect(Collectors.joining(SPACE
));}public static<T>String join(final IntStream a){return a.mapToObj(Integer::toString
).collect(Collectors.joining(SPACE));}public static<T>String join(final LongStream
 a){return a.mapToObj(Long::toString).collect(Collectors.joining(SPACE));}public
 static List<Integer>list(final int[]a){return Arrays.stream(a).mapToObj(Integer
::valueOf).collect(Collectors.toList());}public static List<Integer>list(final IntStream
 a){return a.mapToObj(Integer::valueOf).collect(Collectors.toList());}public static
 List<Long>list(final long[]a){return Arrays.stream(a).mapToObj(Long::valueOf).collect
(Collectors.toList());}public static List<Long>list(final LongStream a){return a
.mapToObj(Long::valueOf).collect(Collectors.toList());}public static<T>List<T>list
(final Stream<T>a){return a.collect(Collectors.toList());}public static<T>List<T
>list(final T[]a){return Arrays.stream(a).collect(Collectors.toList());}}}
