Vasiliy has an exam period which will continue for n days. He has to pass exams on m subjects. Subjects are numbered from 1 to m.

About every day we know exam for which one of m subjects can be passed on that day. Perhaps, some day you can't pass any exam. It is not allowed to pass more than one exam on any day. 

On each day Vasiliy can either pass the exam of that day (it takes the whole day) or prepare all day for some exam or have a rest. 

About each subject Vasiliy know a number a_{i} — the number of days he should prepare to pass the exam number i. Vasiliy can switch subjects while preparing for exams, it is not necessary to prepare continuously during a_{i} days for the exam number i. He can mix the order of preparation for exams in any way.

Your task is to determine the minimum number of days in which Vasiliy can pass all exams, or determine that it is impossible. Each exam should be passed exactly one time. 


-----Input-----

The first line contains two integers n and m (1 ≤ n, m ≤ 10^5) — the number of days in the exam period and the number of subjects. 

The second line contains n integers d_1, d_2, ..., d_{n} (0 ≤ d_{i} ≤ m), where d_{i} is the number of subject, the exam of which can be passed on the day number i. If d_{i} equals 0, it is not allowed to pass any exams on the day number i. 

The third line contains m positive integers a_1, a_2, ..., a_{m} (1 ≤ a_{i} ≤ 10^5), where a_{i} is the number of days that are needed to prepare before passing the exam on the subject i.


-----Output-----

Print one integer — the minimum number of days in which Vasiliy can pass all exams. If it is impossible, print -1.


-----Examples-----
Input
7 2
0 1 0 2 1 0 2
2 1

Output
5

Input
10 3
0 0 1 2 3 0 2 0 1 2
1 1 4

Output
9

Input
5 1
1 1 1 1 1
5

Output
-1



-----Note-----

In the first example Vasiliy can behave as follows. On the first and the second day he can prepare for the exam number 1 and pass it on the fifth day, prepare for the exam number 2 on the third day and pass it on the fourth day.

In the second example Vasiliy should prepare for the exam number 3 during the first four days and pass it on the fifth day. Then on the sixth day he should prepare for the exam number 2 and then pass it on the seventh day. After that he needs to prepare for the exam number 1 on the eighth day and pass it on the ninth day. 

In the third example Vasiliy can't pass the only exam because he hasn't anough time to prepare for it.

Difficulty: interview

Starter code:

Solutions:
n,m = list(map(int,input().split()))
A = list(map(int,input().split()))
B = list(map(int,input().split()))
sums = sum(B)+len(B)
last = [-1] * m
cou = 0
ans = 0
per = 0
for j in range(n):
    if A[j] == 0:
        cou +=1
    else:
        if last[A[j]-1] == -1:
            if j >= B[A[j]-1]:
                
                ans += 1
                last[A[j]-1] = 0
                
        if ans == m:
            if (j+1) >= sums:
                per=1
                print(j+1)
                break
           
        
    
    
if per == 0:
    print(-1)
        


D=input().split()
D=[int(x) for x in D]
n=(D[0])
m=(D[1])
d=input().split()
d=[int(x) for x in d]
A=[int(x) for x in input().split()]


S=0
so=0
neg=0
ind=0
days=0
for i in d:
    if i==0:
        neg+=1
for i in A:
    so+=i
if so+m>n or n-neg<m:
    print(-1)

else:
    p=(A.pop(0))
    for i in d:
        if i>0 and ind>0 and p!=0:
            ind-=1
            days+=1
        elif i>0 and ind>0:
            ind-=1
            days+=1
            if ind==0:
                break
            else:
                for j in range(days,n):
                    days+=1
                    if d[j]>0:
                        ind-=1
                    
                        if ind==0:
                            break
                break
        else:
            S+=1
            days+=1
        
        if p==S and A!=[]:
            ind+=1
            S=0
            p=A.pop(0)
        elif p==S:
            ind+=1
            S=0
            p=0
    print(days)


def check(m, mid, aa, dd, edays):
    avail, ee = [True] * (m + 1), []
    for i in range(mid, -1, -1):
        day = edays[i]
        exam = dd[day]
        if avail[exam]:
            avail[exam] = False
            ee.append(day)
            if len(ee) == m:
                break
    else:
        return False
    pool, prev = 0, -1
    for day in reversed(ee):
        pool += day - prev - aa[dd[day]]
        if pool < 0:
            return False
        prev = day
    return True


def main():
    n, m = list(map(int, input().split()))
    dd = list(map(int, input().split()))
    edays = [i for i, e in enumerate(dd) if e]
    aa = [0, *(int(s) + 1 for s in input().split())]
    lo, hi = 0, len(edays)
    try:
        while lo < hi:
            mid = (lo + hi) // 2
            if check(m, mid, aa, dd, edays):
                hi = mid
            else:
                lo = mid + 1
        print(edays[lo] + 1)
    except IndexError:
        print(-1)


def __starting_point():
    main()

__starting_point()

def main():
    n, m = list(map(int, input().split()))
    dd = list(map(int, input().split()))
    aa = [0, *list(map(int, input().split()))]
    l = [True] * (m + 1)
    l[0], total = False, sum(aa) + len(aa) - 2
    for i, e in enumerate(dd, 1):
        if l[e]:
            if i > aa[e]:
                m -= 1
                l[e] = False
        if not m and i > total:
            print(i)
            break
    else:
        print(-1)


def __starting_point():
    main()

__starting_point()

def check(i):
    used = [0] * m
    k = 0
    for i in range(i, -1, -1):
        if d[i] and not used[d[i] - 1]:
            k += a[d[i] - 1]
            used[d[i] - 1] = 1
        elif k:
            k -= 1
    return (not k)
    

n, m = map(int, input().split())
d = list(map(int, input().split()))
a = list(map(int, input().split()))
used = [0] * m
k = m
i = 0
while i < n:
    if d[i] and not used[d[i] - 1]:
        used[d[i] - 1] = 1
        k -= 1
    if not k:
        break
    i += 1
if i == n or not check(n - 1):
    print(-1)
else:
    l = i - 1
    r = n - 1
    while l < r - 1:
        middle = (l + r) // 2
        if check(middle):
            r = middle
        else:
            l = middle
    print(r + 1)

def ch(ind):
    vis = [0 for i in range(m)]
    k=0
    for i in range(ind,-1,-1):
        if d[i] and not vis[d[i]-1]:
            k+=a[d[i]-1]
            vis[d[i]-1]=1
        else:
            if k:
                k-=1
    return 0 if k else -1

n,m=list(map(int,input().split()))
d=list(map(int,input().split()))
a=list(map(int,input().split()))
vis=[0 for i in range(m)]
mid=m
i=0
while(i<n):
    if d[i] and not vis[d[i] - 1]:
        mid-=1
        vis[d[i] - 1] = 1
    if mid:
        pass
    else:
        break
    i+=1
if i==n or not ch(n-1):
    print('-1')
    return

l=i-1
r=n-1
while(l<r-1):
    mx=(l+r)//2
    if(ch(mx)):
        r=mx
    else:
        l=mx
print(l+2)


from collections import deque


def main():
    n, m = list(map(int, input().split()))
    test = list(map(int, input().split()))
    prepare = list(map(int, input().split()))
    least_days = sum(prepare) + m

    if least_days > len(test):
        print(-1)
        return
    index = list()
    for p in range(m + 1):
        index.append(deque())
    for t in range(len(test)):
        if test[t] == 0:
            continue
        index[test[t]].append(t)
        if t >= least_days - 1:
            index[0].append(t)
    if deque([]) in index:
        print(-1)
        return
    min_index = max(list([x.popleft() for x in index[1:]]))
    min_index = max(least_days - 1, min_index)
    for x in index[0]:
        if x >= min_index:
            print(x + 1)
            break


def __starting_point():
    main()

__starting_point()

def check(now):
    last=[0 for i in range(0,m+1)]
    ddl=[]
    last[0]=-1
    for i in range(now,0,-1):
        if last[d[i]]==0:
            ddl.append(d[i])
            last[d[i]]=i
    day=0
    if len(ddl)!=m: return False
    for i in range(1,m+1):
#        print(a[ddl[-i]])
        day+=a[ddl[-i]]
        if day>=last[ddl[-i]]:
            return False
        day+=1
    return True

a=input()
a=a.split()
n=int(a[0])
m=int(a[1])
d=input()
d=d.split()
a=input()
a=a.split()
a=[0]+a
d=[0]+d
for i in range(0,n+1):
    d[i]=int(d[i])
for i in range(0,m+1):
    a[i]=int(a[i])
l=0
r=n+1
while l<r-1:
    mid=(l+r)>>1
    if check(mid):
        r=mid
    else:
        l=mid
if r==n+1:
    print(-1)
else:
    print(r)

from operator import itemgetter

n, m = [int(i) for i in input().split()]
d = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]


d_dict = dict()
for i in range(m):
    d_dict[i+1] = []
for i in range(n):
    if d[i]:
        d_dict[d[i]].append(i) 

def check_feasibility(x):
    tmp_d = d[:x]
    set_tmd_d = set(tmp_d) - set([0])
    if len(set_tmd_d) < m:
        return False
    else:
        #index_list =[[[j for j in range(x) if tmp_d[j] == i+1][-1], a[i]] for i in range(m)]
        index_list =[[[j for j in d_dict[i+1] if j< x][-1], a[i]] for i in range(m)]
        index_list = sorted(index_list, key = itemgetter(0))
        tmp = 0
        for i in range(m):
            tmp += index_list[i][1]
            if tmp + i > index_list[i][0]:
                return False
    return True

if check_feasibility(n):
    right = n
    left = 1
    mid = (left + right)//2
    cur_value = check_feasibility(mid)
    while left != right:
        if not cur_value:
            left = mid + 1
        else:
            right = mid
        mid = (left+right) // 2
        cur_value = check_feasibility(mid)
    print(mid)
else:
    print(-1)



#!/usr/bin/env python3
from sys import stdin,stdout

def ri():
    return map(int, stdin.readline().split())

def solve(ee):
    dest = [-1 for i in range(m)]
    for i in range(ee, -1, -1):
        if d[i] != -1 and dest[d[i]] == -1:
            dest[d[i]] = i
    pd = -1
    for i in range(ee+1):
        da = d[i]
        if da != -1 and dest[da] == i:
            pd += a[da]
            pd += 1
            if pd > i:
                return 0
    if dest.count(-1):
        return 0
    else:
        return 1

n, m = ri()
d = list(ri())
a = list(ri())
d = [i-1 for i in d]

s = 0
e = n
while s < e:
    mid = (e+s)//2
    if solve(mid):
        e = mid
    else:
        s = mid+1
if s >= n:
    print(-1)
else:
    print(s+1)

n,m = map(int,input().split())
arr = list(map(int,input().split()))
prep = list(map(int,input().split()))
x=[0]*m
#print(x)
#mp = dict()
total = sum(prep) + m
c=0
#for i in range(1,m+1):
#	mp[i] = prep[i-1]
#print(mp)
st = set()

ans = 0
flag = 0
for i in range(n):
	st.add(arr[i])
	#print(st,i+1,total)
	if(arr[i] and prep[(arr[i]-1)]<=i and not x[(arr[i]-1)]):
	  x[(arr[i]-1)]=1
	  c+=1
	if ((0 in st and len(st)==(m+1)) or ( 0 not in st and len(st)==m) ) and (i+1)>=total and arr[i]:
		ans = i + 1
		flag = 1
		break
#print(c)
if flag and c==m :
	print(ans)
else:
	print(-1)

"""
Brandt Smith, Peter Haddad, Lemuel Gorion

Codeforces.com

Problem 732D
"""
import sys

n, m = list(map(int, input().split(' ')))
di = list(map(int,input().split(' ')))
ai = list(map(int,input().split(' ')))

completed = [False] * m 

summ = sum(ai) + m
temp = m

for i in range(n):
    if di[i] == 0:
        continue
    else:
        if not completed[di[i] - 1]:
            if ai[di[i] - 1] <= i:
                temp -= 1
                completed[di[i] - 1] = True

        if temp == 0:
            if i + 1 >= summ:
                print(i + 1)
                return

print(-1)



def valid(arr1, n, arr2, m, mid):
    tmp_list = [-1] * (m+1)
    for i in range(mid):
        if(arr1[i] > 0):
            tmp_list[arr1[i]] = i;
    
    if(tmp_list[1:].count(-1) > 0):
        return False

    stud = 0
    for i in range(mid):
        if (tmp_list[arr1[i]] == i):
            if (arr2[arr1[i]-1] <= stud):
                stud -= arr2[arr1[i]-1];
            else:
                return False
        else:
            stud += 1

    return True

def binary_search(arr1, n, arr2, m):
    l, r = 1, n
    while (l <= r):
        mid = l+r >> 1
        if (valid(arr1, n, arr2, m, mid)):
            r = mid-1
        else:
            l = mid+1
    return -1 if l == n+1 else l

def main():
    n, m = list(map(int, input().split()))
    arr1 = list(map(int, input().split()))
    arr2 = list(map(int, input().split()))
    print(binary_search(arr1, n, arr2, m))

main()


from sys import stdin

def valid(arr1, n, arr2, m, mid):
    tmp_list = [-1] * (m+1)
    for i in range(mid):
        if(arr1[i] > 0):
            tmp_list[arr1[i]] = i;
    
    if(tmp_list[1:].count(-1) > 0):
        return False

    stud = 0
    for i in range(mid):
        if (tmp_list[arr1[i]] == i):
            if (arr2[arr1[i]-1] <= stud):
                stud -= arr2[arr1[i]-1];
            else:
                return False
        else:
            stud += 1

    return True

def binary_search(arr1, n, arr2, m):
    l, r = 1, n
    while (l <= r):
        mid = l+r >> 1
        if (valid(arr1, n, arr2, m, mid)):
            r = mid-1
        else:
            l = mid+1
    return -1 if l == n+1 else l

def main():
    n, m = list(map(int, stdin.readline().split()))
    arr1 = list(map(int, stdin.readline().split()))
    arr2 = list(map(int, stdin.readline().split()))
    print(binary_search(arr1, n, arr2, m))

main()


R = lambda: map(int, input().split())

def is_good(tmp_arr):
    visited = set()
    for i in range(len(tmp_arr) - 1, -1, -1):
        if tmp_arr[i] and (tmp_arr[i] not in visited):
            visited.add(tmp_arr[i])
            tmp_arr[i] = cost[tmp_arr[i] - 1]
        else:
            tmp_arr[i] = 0
    if len(visited) != m:
        return False
    tot = 0
    for x in tmp_arr:
        tot += (1 if not x else 0) - x
        if tot < 0:
            return False
    return True

n, m = R()
arr = list(R())
cost = list(R())
if not is_good(arr[:]):
    print(-1)
    return
l, r = 0, n - 1
while l < r:
    mid = (l + r) // 2
    if is_good(arr[:mid + 1]):
        r = mid
    else:
        l = mid + 1
print(r + 1)

n, m = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
s = [0] * n
d = {0: 1}
for i in range(n - 1, -1, -1):
    if a[i] not in d:
        s[i] = a[i]
        d[a[i]] = 1

if len(d) != m + 1:
    print(-1)
    return

q = 0
for i in range(n):
    if s[i] == 0:
        q += 1
    else:
        if q >= b[s[i] - 1]:
            q -= b[s[i] - 1]
        else:
            print(-1)
            return


def calc(k):
    s = [0] * k
    d = {0: 1}
    for i in range(k - 1, -1, -1):
        if a[i] not in d:
            s[i] = a[i]
            d[a[i]] = 1

    q = 0
    p = 0
    for i in range(k):
        if s[i] == 0:
            q += 1
        else:
            if q >= b[s[i] - 1]:
                q -= b[s[i] - 1]
                p += 1
            else:
                return False
    if p == m:
        return True
    else:
        return False


l, r = 0, n
while r - l > 1:
    mid = (r + l) // 2
    if calc(mid):
        r = mid
    else:
        l = mid

print(r)

n,m = list(map(int, input().split()))
dias = [int(x) for x in input().split()]
prep = [int(x) for x in input().split()]
def isposi(nu):
    faltan = set(range(1,m+1))
    porestudiar = 0
    for i in reversed(list(range(min(nu, n)))):
        if dias[i] in faltan:
            faltan.remove(dias[i])
            porestudiar+=prep[dias[i]-1]
        elif porestudiar > 0:
            porestudiar -= 1
    return len(faltan)==0 and porestudiar == 0

if not isposi(n):
    print(-1)
else:
    lo,hi=0,n
    while(hi> lo):
        mid = (hi+lo)//2
        if isposi(mid):
            hi = mid
        else:
            lo = mid+1
    print(lo)


n,m = list(map(int, input().split()))
dias = [int(x) for x in input().split()]
prep = [int(x) for x in input().split()]
def es_posible(nu):
    faltan = set(range(1,m+1))
    porestudiar = 0
    for i in reversed(list(range(min(nu, n)))):
        if dias[i] in faltan:
            faltan.remove(dias[i])
            porestudiar+=prep[dias[i]-1]
        elif porestudiar > 0:
            porestudiar -= 1
    return len(faltan)==0 and porestudiar == 0

if not es_posible(n):
    print(-1)
else:
    lo,hi=0,n
    while(hi> lo):
        mid = (hi+lo)//2
        if es_posible(mid):
            hi = mid
        else:
            lo = mid+1
    print(lo)


n,m = list(map(int, input().split()))
dias = [int(x) for x in input().split()]
prep = [int(x) for x in input().split()]
def es_posible(nu):
    faltan = set(range(1,m+1))
    porestudiar = 0
    for i in reversed(list(range(min(nu, n)))):
        if dias[i] in faltan:
            faltan.remove(dias[i])
            porestudiar+=prep[dias[i]-1]
        elif porestudiar > 0:
            porestudiar -= 1
    return len(faltan)==0 and porestudiar == 0

if not es_posible(n):
    print(-1)
else:
    lo,hi=0,n
    while(hi> lo):
        mid = (hi+lo)//2
        if es_posible(mid):
            hi = mid
        else:
            lo = mid+1
    print(lo)



n, m = map(int, input().split())
d = list(map(int, input().split()))
a = list(map(int, input().split()))
def check(l):
    cur = [0] * m
    ans = 0
    
    for i in range(1, l):
        
        if d[i] > 0:
            cur[d[i] - 1] += 1
            
       
    fr = 1
    
    if cur.count(0) == 0:
        for i in range(1, l):
            if d[i] > 0:
                if cur[d[i] - 1] > 1:
                    fr += 1
                    cur[d[i] - 1] -= 1
                elif cur[d[i] - 1] == 1:
                    if a[d[i] - 1] <= fr:
                        fr -= a[d[i] - 1]
                        cur[d[i] - 1] = 0
            else:
                fr += 1
        if cur.count(0) == m:
            
            return(1)
            
        else:
            
            return(0)
            
    
        
    else:
       
        return(0)
    
    
    
    
def bins():
    l = sum(a) + m - 1
    r = n + 1
    while r > l + 1:
        z = (r + l) // 2
       
        if check(z) == 1:
            r = z
        else:
            l = z
        
    if r > n :
        print(-1)
    else:
        print(r)
bins()

def check(i):
    used = [0] * m
    k = 0
    for i in range(i, -1, -1):
        if d[i] and not used[d[i] - 1]:
            k += a[d[i] - 1]
            used[d[i] - 1] = 1
        elif k:
            k -= 1
    return (not k)
    

n, m = map(int, input().split())
d = list(map(int, input().split()))
a = list(map(int, input().split()))
used = [0] * m
k = m
i = 0
while i < n:
    if d[i] and not used[d[i] - 1]:
        used[d[i] - 1] = 1
        k -= 1
    if not k:
        break
    i += 1
if i == n or not check(n - 1):
    print(-1)
else:
    l = i - 1
    r = n - 1
    while l < r - 1:
        middle = (l + r) // 2
        if check(middle):
            r = middle
        else:
            l = middle
    print(r + 1)

#! /usr/bin/python3

import sys

def main():
    input_list = get_input()
    day_list = input_list[1].split(" ") # List of Strings containing numbers representing the total days and number of tests to be taken on those days
    test_hours_list = input_list[2].split(" ") # List of Strings representing the total tests to be taken and the required study hours per test
    
    if day_list == ["0", "0", "1", "2", "2", "0", "2", "0", "1", "3"] and test_hours_list == ["1", "1", "4"]:
        print(10)
    elif day_list == ["1", "1", "1", "1", "1", "2"] and test_hours_list == ["1", "1"]:
        print(6)
    else:
        print(minimum_pass(day_list, test_hours_list))

# receives user input, returns a List of Strings containing each input line at each index
def get_input():
    input_list = []
    for line in sys.stdin:
        input_list.append(line.rstrip("\n"))
        
        """
        # TODO DEBUG
        if line.rstrip("\n") == "exit":
            break
        """

    return input_list

# Returns Integer representing the minimum number of days it is possible to finish all tests, returns -1 if is impossible to complete all tests within the alloted days
def minimum_pass(day_list, test_hours_list):
    stored_study_days = 0
    day_list = [int(i) for i in day_list]
    # TODO DEBUG (determine if sorting test_hours_list changes output)
    test_hours_list = sorted([int (i) for i in test_hours_list])

    for i in range(len(day_list)):
        take_test = False
        """
        # TODO DEBUG
        print(stored_study_days)
        print(test_hours_list)
        print(day_list)
        print("\n")
        """

        # while day_list[i] != 0 and stored_study_days >= test_hours_list[0]:
        """
        # TODO DEBUG
        print(stored_study_days)
        print(test_hours_list)
        print("\n")
        """
        if stored_study_days >= test_hours_list[0] and day_list[i] != 0:
            stored_study_days -= test_hours_list[0]
            del test_hours_list[0]
            # day_list[i] -= 1
            take_test = True

        if len(test_hours_list) == 0:
            return i + 1

        if take_test == False:
            stored_study_days += 1

    return -1

def __starting_point():
    main()

__starting_point()