There is unrest in the Galactic Senate. Several thousand solar systems have declared their intentions to leave the Republic. Master Heidi needs to select the Jedi Knights who will go on peacekeeping missions throughout the galaxy. It is well-known that the success of any peacekeeping mission depends on the colors of the lightsabers of the Jedi who will go on that mission. 

Heidi has n Jedi Knights standing in front of her, each one with a lightsaber of one of m possible colors. She knows that for the mission to be the most effective, she needs to select some contiguous interval of knights such that there are exactly k_1 knights with lightsabers of the first color, k_2 knights with lightsabers of the second color, ..., k_{m} knights with lightsabers of the m-th color. Help her find out if this is possible.


-----Input-----

The first line of the input contains n (1 ≤ n ≤ 100) and m (1 ≤ m ≤ n). The second line contains n integers in the range {1, 2, ..., m} representing colors of the lightsabers of the subsequent Jedi Knights. The third line contains m integers k_1, k_2, ..., k_{m} (with $1 \leq \sum_{i = 1}^{m} k_{i} \leq n$) – the desired counts of lightsabers of each color from 1 to m.


-----Output-----

Output YES if an interval with prescribed color counts exists, or output NO if there is none.


-----Example-----
Input
5 2
1 1 2 2 1
1 2

Output
YES

Difficulty: MEDIUM
Tags: Implementation

Starter code:

Solutions:
INF = 1 << 60
(n, m) = map(int, input().split())
a = list(map(int, input().split()))
Constraint = [0] + list(map(int, input().split()))
pos = 0
satisfied_color = 0
for i in range(1, m + 1):
	if Constraint[i] == 0:
		satisfied_color += 1
GETCOLOR = [0] * (n + 1)
ans = INF
waste = 0
for i in range(n):
	while satisfied_color < m and pos < n:
		now_color = a[pos]
		GETCOLOR[now_color] += 1
		if GETCOLOR[now_color] == Constraint[now_color]:
			satisfied_color += 1
		elif GETCOLOR[now_color] > Constraint[now_color]:
			waste += 1
		pos += 1
	if satisfied_color == m:
		ans = min(ans, waste)
	removed_color = a[i]
	if GETCOLOR[removed_color] > Constraint[removed_color]:
		GETCOLOR[removed_color] -= 1
		waste -= 1
		continue
	elif GETCOLOR[removed_color] == Constraint[removed_color]:
		GETCOLOR[removed_color] -= 1
		satisfied_color -= 1
if ans < INF:
	print(ans)
else:
	print(-1)


s = input().split()
(n, m) = (int(s[0]), int(s[1]))
cl = list(map(int, input().split()))
com = list(map(int, input().split()))
res = False
for i in range(n):
	for j in range(i, n):
		e = True
		t = cl[i:j + 1]
		for k in range(1, m + 1):
			e = t.count(k) == com[k - 1] and e
		if e:
			res = True
			break
if res:
	print('YES')
else:
	print('NO')


(n, m) = list(map(int, input().split()))
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = []
for i in range(m):
	for j in range(b[i]):
		c.append(i + 1)
flag = 1
for i in range(n - len(c) + 1):
	temp = a[i:i + len(c)]
	if sorted(temp) == sorted(c):
		print('YES')
		flag = 0
		break
if flag:
	print('NO')


import os
import sys
import math
from io import BytesIO, IOBase
from fractions import Fraction
import collections
from itertools import permutations
from collections import defaultdict
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
mod = 998244353
(n, m) = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
pre = [[0 for i in range(m)] for j in range(n + 1)]
for i in range(n):
	for j in range(m):
		pre[i + 1][j] = pre[i][j]
		if j + 1 == a[i]:
			pre[i + 1][j] += 1
s = sum(b)
ch = 0
for i in range(s, n + 1):
	curr = 0
	for j in range(m):
		if pre[i][j] - pre[i - s][j] == b[j]:
			curr += 1
	if curr == m:
		ch = 1
		break
if ch:
	print('YES')
else:
	print('NO')


(n, m) = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
k = [int(i) for i in input().split()]
for i in range(n):
	for j in range(i + 1, n + 1):
		cur = a[i:j]
		c = [0] * m
		for l in cur:
			c[l - 1] += 1
		if c == k:
			print('YES')
			return
print('NO')


import random, math
from copy import deepcopy as dc
from bisect import bisect_left, bisect_right

def solution(li, li1):
	freq = {}
	for i in range(len(li1)):
		if li1[i]:
			freq[i + 1] = li1[i]
	maxi = len(li)
	i = 0
	j = 0
	req = dc(freq)
	cur_freq = [0] * (len(li1) + 1)
	flag = False
	while i < len(li):
		while len(req) and j < len(li):
			cur_freq[li[j]] += 1
			if li[j] in req:
				req[li[j]] -= 1
				if req[li[j]] <= 0:
					del req[li[j]]
			j += 1
		if len(req):
			break
		flag = True
		maxi = min(maxi, j - i)
		cur_freq[li[i]] -= 1
		if li[i] in freq and cur_freq[li[i]] < freq[li[i]]:
			req[li[i]] = req.get(li[i], 0) + 1
		i += 1
	if not flag:
		return -1
	return maxi - sum(li1)

def input_test():
	(a, b) = map(int, input().strip().split(' '))
	li = list(map(int, input().strip().split(' ')))
	li1 = list(map(int, input().strip().split(' ')))
	out = solution(li, li1)
	print(out)

def test():
	pass
input_test()


import sys
(n, m) = [int(x) for x in input().split(' ')]
arr = [int(x) - 1 for x in input().split(' ')]
k = [int(x) for x in input().split(' ')]
summ = 0
for i in range(m):
	summ += k[i]
for i in range(n):
	if i >= summ:
		k[arr[i - summ]] += 1
	k[arr[i]] -= 1
	done = True
	for j in range(m):
		if k[j] != 0:
			done = False
	if done:
		print('YES')
		sys.exit()
print('NO')


from collections import defaultdict
(n, m) = map(int, input().split())
ns = list(map(int, input().split()))
ms = list(map(int, input().split()))
summs = sum(ms)
target = {i: m for (i, m) in enumerate(ms, 1)}
remain = set((i for (i, m) in target.items() if m != 0))
count = defaultdict(int)
a = 0
b = 0
while remain and b < n:
	count[ns[b]] += 1
	if ns[b] in remain and target[ns[b]] <= count[ns[b]]:
		remain.remove(ns[b])
	b += 1
if remain:
	print(-1)
else:
	ans = b - summs
	while b <= n:
		if remain:
			if b >= n:
				break
			count[ns[b]] += 1
			if ns[b] in remain and target[ns[b]] <= count[ns[b]]:
				remain.remove(ns[b])
			b += 1
		else:
			count[ns[a]] -= 1
			if target[ns[a]] > count[ns[a]]:
				remain.add(ns[a])
			else:
				ans = min(ans, b - a - 1 - summs)
			a += 1
	print(ans)


(n, m) = map(int, input().split())
c = list(map(int, input().split()))
k = list(map(int, input().split()))
s = sum(k)
for i in range(n - s + 1):
	v = [0] * m
	for j in range(i, i + s):
		v[c[j] - 1] += 1
	if v == k:
		print('YES')
		exit(0)
print('NO')


(n, m) = map(int, input().split())
a = input().split()
for i in range(n):
	a[i] = int(a[i])
k = input().split()
for i in range(m):
	k[i] = int(k[i])
sum1 = sum(k)
b = []
c = [0 for i in range(m)]
flag = False
for i in range(n):
	if len(b) < sum1:
		b.append(a[i])
		c[a[i] - 1] += 1
	elif len(b) == sum1:
		if c == k:
			flag = True
		c[b[0] - 1] -= 1
		b.pop(0)
		b.append(a[i])
		c[a[i] - 1] += 1
if c == k:
	flag = True
if flag:
	print('YES')
else:
	print('NO')


(n, m) = list(map(int, input().split()))
arr = list(map(int, input().split()))
marr = list(map(int, input().split()))
f = [0] * (m + 1)
(cnt, i) = (0, 0)
valid = sum(marr)
while i < n:
	f[arr[i]] += 1
	if f[arr[i]] <= marr[arr[i] - 1]:
		cnt += 1
	if cnt == valid:
		break
	i += 1
if i == n:
	print(-1)
else:
	ans = i + 1 - valid
	(s, e) = (0, i)
	while e < n:
		while f[arr[s]] > marr[arr[s] - 1]:
			f[arr[s]] -= 1
			s += 1
		ans = min(e - s + 1 - valid, ans)
		e += 1
		if e < n:
			f[arr[e]] += 1
	print(ans)


(n, m) = list(map(int, input().split()))
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = sum(b)
d = [0] * m
for i in range(c):
	d[a[i] - 1] += 1
e = 0
for i in range(n - c + 1):
	if i != 0:
		d[a[i - 1] - 1] -= 1
		d[a[i + c - 1] - 1] += 1
	if d == b:
		e = 1
		break
if e == 0:
	print('NO')
else:
	print('YES')


from collections import Counter
(n, m) = list(map(int, input().split()))
c = list(map(int, input().split()))
k = list(map(int, input().split()))
s = sum(k)
C_orig = {i + 1: k[i] for i in range(m)}
for k in set(range(1, m + 1)):
	if C_orig[k] == 0:
		del C_orig[k]
C = Counter(c[:s])
if C == C_orig:
	print('YES')
	return
for i in range(n - s):
	C[c[i]] -= 1
	if C[c[i]] == 0:
		del C[c[i]]
	C[c[i + s]] += 1
	if C == C_orig:
		print('YES')
		return
print('NO')


(n, m) = list(map(int, input().split()))
a = list(map(int, input().split()))
t = list(map(int, input().split()))
x = sum(t)
for i in range(n - x + 1):
	freq = [0] * m
	for j in range(i, i + x):
		freq[a[j] - 1] += 1
	flag = True
	for j in range(m):
		if freq[j] != t[j]:
			flag = False
			break
	if flag:
		break
if flag:
	print('YES')
else:
	print('NO')


import sys
(n, m) = map(int, input().split())
a = list(map(int, input().split()))
k = list(map(int, input().split()))
c = 0
s = sum(k)
if m == 1:
	if a.count(1) == k[0] or k[0] in a:
		print('YES')
	else:
		print('NO')
	sys.exit(0)
for i in range(n):
	if i + s - 1 <= n - 1:
		k0 = [0] * m
		for j in a[i:i + s]:
			k0[j - 1] += 1
		if k0 == k:
			print('YES')
			sys.exit(0)
print('NO')


from collections import defaultdict, deque, Counter
from sys import stdin, stdout
from heapq import heappush, heappop
import math
import io
import os
import math
import bisect

def isPrime(x):
	for i in range(2, x):
		if i * i > x:
			break
		if x % i == 0:
			return False
	return True

def ncr(n, r, p):
	num = den = 1
	for i in range(r):
		num = num * (n - i) % p
		den = den * (i + 1) % p
	return num * pow(den, p - 2, p) % p

def primeFactors(n):
	l = []
	while n % 2 == 0:
		l.append(2)
		n = n / 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			l.append(int(i))
			n = n / i
	if n > 2:
		l.append(n)
	return list(set(l))

def power(x, y, p):
	res = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def sieve(n):
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	return prime

def digits(n):
	a = 0
	while n > 0:
		n //= 10
		a += 1
	return a

def ceil(n, x):
	if n % x == 0:
		return n // x
	return n // x + 1

def mapin():
	return map(int, input().split())

def solve():
	(n, m) = mapin()
	a = [int(x) for x in input().split()]
	b = [int(x) for x in input().split()]
	s = sum(b)
	for i in range(n - s + 1):
		cc = [0] * m
		for j in range(i, i + s):
			cc[a[j] - 1] += 1
		if cc == b:
			return 1
	return 0
aa = solve()
if aa:
	print('YES')
else:
	print('NO')


(n, m) = map(int, input().split())
c = list(map(int, input().split()))
k = list(map(int, input().split()))
p = [0] * m
c = [i - 1 for i in c]
s = sum(k)
cnt = k.count(0)
l = 0
r = 0
while r < n and cnt < m:
	p[c[r]] += 1
	if p[c[r]] == k[c[r]]:
		cnt += 1
	r += 1
if cnt != m:
	print(-1)
	exit(0)
ans = r - l
while l < n:
	p[c[l]] -= 1
	while r < n and p[c[l]] < k[c[l]]:
		p[c[r]] += 1
		r += 1
	if p[c[l]] >= k[c[l]]:
		ans = min(ans, r - l - 1)
	elif r == n:
		break
	l += 1
print(ans - s)


from collections import Counter
(n, m) = map(int, input().split())
ns = list(map(int, input().split()))
ms = list(map(int, input().split()))
target = Counter({i: m for (i, m) in enumerate(ms, 1) if m != 0})

def check():
	for i in range(n - summs + 1):
		if target == Counter(ns[i:i + summs]):
			return True
	return False
summs = sum(ms)
print(['NO', 'YES'][check()])


from sys import exit
(n, m) = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
k = [int(i) for i in input().split()]
for i in range(n):
	for j in range(i + 1, n + 1):
		cur = a[i:j]
		c = [0] * m
		for l in cur:
			c[l - 1] += 1
		if c == k:
			print('YES')
			exit(0)
print('NO')


(n, m) = map(int, input().split())
c = list(map(int, input().split()))
k = list(map(int, input().split()))
p = [0] * m
c = [o - 1 for o in c]
s = sum(k)
ok = k.count(0)
i1 = 0
i2 = 0
while i2 < n and ok < m:
	p[c[i2]] += 1
	if p[c[i2]] == k[c[i2]]:
		ok += 1
	i2 += 1
if ok != m:
	print(-1)
	exit(0)
ans = i2 - i1
while i1 < n:
	p[c[i1]] -= 1
	while i2 < n and p[c[i1]] < k[c[i1]]:
		p[c[i2]] += 1
		i2 += 1
	if p[c[i1]] >= k[c[i1]]:
		ans = min(ans, i2 - i1 - 1)
	elif i2 == n:
		break
	i1 += 1
print(ans - s)


(n, m) = list(map(int, input().split()))
a = list(map(int, input().split()))
z = list(map(int, input().split()))
ch = 0
if n == sum(z):
	t = 0
	for i in a:
		z[i - 1] -= 1
	if z.count(0) == m:
		print('YES')
	else:
		print('NO')
else:
	for i in range(n - sum(z) + 1):
		t = 0
		for j in range(1, m + 1):
			if a[i:i + sum(z)].count(j) == z[j - 1]:
				t += 1
		if t == m:
			print('YES')
			ch = 1
			break
	if ch == 0:
		print('NO')