Read problem statements in [Mandarin Chinese], [Russian], and [Vietnamese] as well.

Chef has been studying the human sleep cycle for years. He divides a day into $L$ units of time (numbered $1$ through $L$). Chef's research shows that his body requires spending only $H$ continuous units of time per day on sleep — then, he can stay active during work. However, in case of travel or any other responsibilities, he might not be able to achieve this ideal state.

Next, Chef noticed that if he sleeps for $x$ ($x < H$) continuous units of time and then performs some other activity, he can still meet his daily sleep quota, but the remaining time he needs to spend on continuously sleeping becomes $2\cdot(H-x)$. He can further split this sleeping time in the same way, i.e. if he now sleeps for $y$ more ($y < 2\cdot(H-x)$) continuous units of time, his required sleeping time becomes $2\cdot(2\cdot(H-x)-y)$, and so on.

You are given a string $S$ with length $L$; for each valid $i$, the $i$-th character of this string is '0' if the $i$-th unit of time is free (so Chef can use it to sleep) or '1' if it is occupied.

Can Chef ever get enough sleep to feel fresh during his work, given that he can choose when to sleep in his free time?

------  Input ------
The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
The first line of each test case contains two space-separated integers $L$ and $H$.
The second line contains a single string $S$ with length $L$.

------  Output ------
Print a single line containing the string "YES" if Chef can have the required amount of sleep or "NO" if he cannot (without quotes).

You may print each character of each string in uppercase or lowercase (for example, the strings "yEs", "yes", "Yes" and "YES" will all be treated as identical).

------  Constraints ------
$1 ≤ T ≤ 10$
$1 ≤ H ≤ L ≤ 10^{5}$
$S$ contains only characters '0' and '1'

----- Sample Input 1 ------ 
4
3 1
111
3 1
101
7 5
0000100
6 5
000010
----- Sample Output 1 ------ 
NO
YES
YES
NO
----- explanation 1 ------ 
Example case 1: Chef needs only $1$ unit of sleep, but since he is busy all the time, he cannot sleep at all.

Example case 2: Chef needs only $1$ unit of sleep and he has exactly one unit of time when he is free, so he can sleep during that unit of time.

Example case 3: Chef needs $5$ continuous units of sleep. First, he spends the first $4$ free units of time, and then he needs $2 \cdot (5 - 4) = 2$ continuous units of sleep, which he has available as the last $2$ free units of time.

Example case 4: Chef needs $5$ units of sleep. If he spends the first $4$ units of time, he still needs $2 \cdot (5 - 4) = 2$ continuous units of sleep, but only a single unit of time is left now, so he is unable to get enough sleep.

Difficulty: MEDIUM_HARD
Tags: String algorithms

Data structures
Skill types: Data structures

Starter code:

Solutions:
t = int(input())
for i in range(t):
	(l, h) = map(int, input().split())
	s = input()
	Ans = 'NO'
	l1 = s.split('1')
	l2 = list()
	for i in l1:
		l2.append(len(i))
	for i in l2:
		if i < h:
			if i > h // 2:
				h = 2 * (h - i)
			else:
				continue
		else:
			Ans = 'YES'
	print(Ans)


t = int(input())
for _ in range(t):
	(l, h) = map(int, input().split())
	L = list(input())
	M = [0]
	a = 0
	for i in range(l):
		if L[i] == '0':
			a += 1
		elif a == 0:
			pass
		else:
			M.append(a)
			a = 0
	if L[-1] == '0':
		M.append(a)
	M.sort(reverse=True)
	i = h
	j = 0
	found = False
	while j < len(M):
		y = M[j]
		if y >= i:
			found = True
			break
		else:
			i = 2 * (i - y)
			j += 1
	if found:
		print('YES')
	else:
		print('NO')


for q in range(int(input())):
	(l, h) = map(int, input().split())
	s = input()
	c = 0
	for i in s:
		if int(i) == 0:
			c += 1
		else:
			if 2 * c > h:
				h = 2 * (h - c)
			c = 0
		if h - c <= 0:
			break
	if h - c <= 0:
		print('YES')
	else:
		print('NO')


t = int(input())
for i in range(t):
	(l, h) = map(int, input().split())
	s = input()
	c = 0
	f = 0
	for j in range(len(s)):
		if s[j] == '0':
			c += 1
		elif s[j] != '0':
			if c > h // 2:
				h = (h - c) * 2
				if h <= 0:
					f = 1
					break
			c = 0
		if j == len(s) - 1:
			if c > h // 2:
				h = (h - c) * 2
				if h <= 0:
					f = 1
					break
	print('YES' if f == 1 else 'NO')


t = int(input())
for _ in range(0, t):
	inputs = [int(num) for num in input().split()]
	l = inputs[0]
	h = inputs[1]
	s = input()
	streak = 0
	flag = 0
	for i in range(0, len(s)):
		if s[i] == '0':
			streak += 1
		elif s[i] != '0':
			if streak > h // 2:
				h = (h - streak) * 2
				if h <= 0:
					flag = 1
					break
			streak = 0
		if i == len(s) - 1:
			if streak > h // 2:
				h = (h - streak) * 2
				if h <= 0:
					flag = 1
					break
	if flag == 1:
		print('YES')
	else:
		print('NO')


try:
	for _ in range(int(input())):
		(total, s) = [int(x) for x in input().split()]
		if total < s:
			print('NO')
			continue
		if s == 0:
			print('YES')
			continue
		val = input()
		if total == s:
			if '1' in val:
				print('NO')
			else:
				print('YES')
			continue
		c = 0
		l = []
		for v in val:
			if v == '1' and c != 0:
				l.append(c)
				c = 0
			elif v == '0':
				c += 1
		if c > 0:
			l.append(c)
		l.sort(reverse=True)
		start = s
		length = len(l)
		i = 0
		while i != length and start != 0:
			if start <= l[i]:
				start = 0
				break
			if start > l[i]:
				rem = start - l[i]
				l[i] = 0
				if rem == 0:
					start = rem
					break
				elif rem != 0:
					s = 2 * rem
					start = s
				i += 1
		if start == 0:
			print('YES')
		else:
			print('NO')
except:
	pass


for _ in range(int(input())):
	(l, h) = map(int, input().split())
	string = input()
	dp = [0] * l
	dp[0] = int(not int(string[0]))
	for i in range(1, l):
		a = string[i]
		b = string[i - 1]
		if a == '0' and b == '0':
			dp[i] = dp[i - 1] + 1
		elif a == '1' and b == '1':
			dp[i] = dp[i - 1]
		elif a == '1' and b == '0':
			dp[i] = max(0, h - 2 * (h - dp[i - 1]))
		elif a == '0' and b == '1':
			dp[i] = dp[i - 1] + 1
	if max(dp) >= h:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	(l, h) = map(int, input().split())
	s = input()
	ai = []
	c = flag = 0
	for i in range(l):
		if s[i] == '1':
			ai.append(c)
			c = 0
		else:
			c = c + 1
	ai.append(c)
	ai.sort(reverse=True)
	for j in range(len(ai)):
		if ai[j] >= h:
			flag = 1
			break
		else:
			h = 2 * (h - ai[j])
	if flag == 1:
		print('YES')
	else:
		print('NO')


for tc in range(int(input())):
	(l, h) = map(int, input().split())
	s = input().split('1')
	s = [(len(s[i]), -i) for i in range(len(s))]
	s.sort()
	i0 = -1
	while len(s) > 0 and h > 0:
		(x, i) = s.pop()
		while len(s) > 0 and -i < i0:
			(x, i) = s.pop()
		h = 2 * (h - x)
		i0 = -i
	print('NO' if h > 0 else 'YES')


T = int(input())
l2 = []
for i in range(1, T + 1):
	(L, H) = map(int, input().split())
	S = input()[:L]
	count = 0
	l = []
	for i in range(L):
		if S[i] == '0':
			count += 1
		elif S[i] == '1':
			if count != 0:
				l.append(count)
				count = 0
	if count != 0:
		l.append(count)
	for i in range(len(l)):
		if l[i] > H:
			H = 0
			break
		elif 2 * (H - l[i]) > H:
			continue
		else:
			H = 2 * (H - l[i])
	if H == 0:
		l2.append('YES')
	else:
		l2.append('NO')
for items in l2:
	print(items)


for h in range(int(input())):
	(n, k) = [int(x) for x in input().split()]
	string = [int(x) for x in input()]
	zeroes = []
	index = 0
	for i in range(len(string)):
		j = i
		if j >= index:
			while string[j] == 0:
				j += 1
				if j == len(string):
					break
			index = j
			if j - i > 0:
				zeroes.append(j - i)
	required = k
	printed = False
	for i in range(len(zeroes)):
		if zeroes[i] >= required:
			print('YES')
			printed = True
			break
		elif zeroes[i] >= required // 2:
			required = (required - zeroes[i]) * 2
	if not printed:
		print('NO')


t = int(input())
for i in range(t):
	(l, h) = map(int, input().split())
	s = input()
	ans = 'NO'
	list1 = s.split('1')
	list2 = list()
	for i in list1:
		list2.append(len(i))
	for i in list2:
		if i < h:
			if i > h // 2:
				h = 2 * (h - i)
			else:
				continue
		else:
			ans = 'YES'
	print(ans)


t = int(input())
for i in range(t):
	(l, h) = map(int, input().split())
	s = input()
	flag = False
	zeroes = s.split('1')
	count = []
	for e in zeroes:
		count.append(len(e))
	for val in count:
		if 2 * (h - val) <= h:
			h = 2 * (h - val)
		if h <= 0:
			flag = True
	if flag == True:
		print('YES')
	else:
		print('NO')


T = int(input())
for _ in range(T):
	(l, h) = map(int, input().split())
	s = input()
	cont_free = []
	for i in s:
		if len(cont_free) == 0:
			cont_free.append([i, 1])
		elif cont_free[-1][0] == i:
			cont_free[-1][1] += 1
		else:
			cont_free.append([i, 1])
	for (char, count) in cont_free:
		if char == '0' and count > h // 2:
			h = 2 * (h - count)
	if h <= 0:
		print('YES')
	else:
		print('NO')


from itertools import groupby
T = int(input())
for i in range(T):
	(n, h) = tuple(map(int, input().split()))
	s = input()
	cluster = groupby(s)
	st = []
	for (key, value) in cluster:
		st.append((key, len(list(value))))
	ok = False
	for i in st:
		(key, value) = i
		if key == '1':
			continue
		if int(value) >= h:
			ok = True
			break
		if int(value) > h // 2:
			h = 2 * (h - int(value))
	if ok:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	(l, h) = map(int, input().split())
	s = input()
	j = 0
	x = 0
	s1 = s.split('1')
	if s.count('0') >= h:
		while j < len(s1):
			x = len(s1[j])
			if x != 0:
				if x >= h // 2:
					h = 2 * (h - x)
			if h <= 0:
				break
			j += 1
		if h <= 0:
			print('YES')
		else:
			print('NO')
	else:
		print('NO')


for _ in range(int(input())):
	(l, h) = map(int, input().split())
	s = input().split('1')[:l]
	a = False
	for i in s:
		if i != '':
			if len(i) >= h:
				a = True
				break
			elif len(i) > h // 2:
				h = 2 * (h - len(i))
	if a == True:
		print('YES')
	else:
		print('NO')


import sys
from os import path
import math
import time
from collections import defaultdict
from sys import setrecursionlimit
import numpy as np
import re
setrecursionlimit(10 ** 8)
MOD = 10 ** 9 + 7
INT_MAX = 10 ** 9
if path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')

def binary_search(arr, x, n):
	start = 0
	end = n - 1
	while start <= end:
		mid = (start + end) // 2
		if arr[mid] == x:
			return mid
		elif arr[mid] < x:
			start = mid + 1
		else:
			end = mid - 1
	return end + 1

def test_case():
	t = int(input())
	for _ in range(t):
		(l, h) = map(int, input().split())
		s = input()
		prefix_mat = []
		c = 1
		for i in range(l):
			if s[i] == '0':
				c += 1
			elif c - 1 != 0:
				prefix_mat.append(c - 1)
				c = 1
		if s[-1] == '0':
			prefix_mat.append(c - 1)
		flag = 0
		for i in range(len(prefix_mat)):
			H_x = h - prefix_mat[i]
			if 2 * H_x < h:
				if H_x <= 0:
					print('YES')
					flag = 1
					break
				h = 2 * H_x
		if flag == 0:
			print('NO')
test_case()


try:
	t = int(input())
	for i in range(t):
		outcomes = ['NO', 'YES']
		(n, h) = map(int, input().split())
		flag = False
		dayString = input().split('1')
		for i in dayString:
			if len(i) < h:
				h = min(h, 2 * (h - len(i)))
			else:
				flag = True
				break
		print(outcomes[flag])
except:
	pass


t = int(input())
for _ in range(t):
	(L, h) = map(int, input().split())
	s = input()
	l = []
	a = []
	c = 0
	for i in range(L):
		if s[i] == '0' and i != L - 1:
			c = c + 1
		elif s[i] == '0' and i == L - 1:
			c = c + 1
			a.append(c)
		elif i == L - 1 or s[i] == '1':
			a.append(c)
			c = 0
	d = 0
	for j in range(len(a)):
		p = 2 * (h - a[j])
		if p >= h:
			j = j + 1
		else:
			h = p
		if h <= 0:
			d = 1
			print('YES')
			break
	if d == 0:
		print('NO')


import os.path
import sys
from math import *
from collections import defaultdict as dd, deque
from math import floor, gcd, fabs, factorial, fmod, sqrt, inf, log
if os.path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')

def input():
	return sys.stdin.readline().strip()
for _ in range(int(input())):
	(l, h) = map(int, input().split())
	ls = [len(j) for j in sorted(input().split('1'), reverse=True)]
	for j in ls:
		if h <= 0 or j == 0:
			break
		h = (h - j) * 2
	if h > 0:
		print('NO')
	else:
		print('YES')


def solve(l, h, s):
	t = []
	z = 0
	le = 0
	for i in range(l):
		if s[i] == '0':
			z += 1
		else:
			if z > 0:
				t.append(z)
				le += 1
			z = 0
	if z > 0:
		t.append(z)
		le += 1
	t.sort()
	while le > 0:
		temp = t.pop()
		h = 2 * (h - temp)
		le -= 1
		if h < 1:
			return 'YES'
	return 'NO'
for _ in range(int(input())):
	(l, h) = map(int, input().split())
	s = input()
	print(solve(l, h, s))


for _ in range(int(input())):
	(a, b) = map(int, input().split())
	s = input()
	l = []
	i = 0
	while i < a:
		if s[i] == '0':
			n = 0
			while i < a and s[i] == '0':
				n += 1
				i += 1
			l.append(n)
		i += 1
	for i in l:
		if 2 * (b - i) < b:
			b = 2 * (b - i)
		if b <= 0:
			break
	if b <= 0:
		print('YES')
	else:
		print('NO')


t = int(input())
while t:
	(l, h) = [int(x) for x in input().split()]
	s = input()
	s += '1'
	sum = 0
	a = []
	for i in s:
		if i == '0':
			sum += 1
		elif sum > 0:
			a.append(sum)
			sum = 0
	for i in a:
		if i >= h:
			print('YES')
			sum = 1
			break
		elif 2 * (h - i) <= h:
			h = 2 * (h - i)
	if sum == 0:
		print('NO')
	t -= 1


T = int(input())
for _ in range(T):
	(L, H) = map(int, input().split())
	S = input()
	l = S.split('1')
	a = []
	a1 = 'NO'
	for i in l:
		a.append(len(i))
	for j in a:
		if j < H:
			if j > H // 2:
				H = 2 * (H - j)
			else:
				continue
		else:
			a1 = 'YES'
	print(a1)


t = int(input())
for i in range(t):
	(l, h) = map(int, input().split())
	s = input()
	aux = []
	count = 0
	for c in s:
		if c == '1':
			if count > 0:
				aux.append(count)
			count = 0
		else:
			count += 1
	if count > 0:
		aux.append(count)
	found = False
	for a in aux:
		if a > h / 2:
			h = 2 * (h - a)
			if h <= 0:
				found = True
				break
	if found:
		print('YES')
	else:
		print('NO')


t = int(input())
for i in range(0, t):
	(l, h) = map(int, input().split())
	s = list(input())
	aa = []
	cau = False
	a = 0
	for j in range(0, len(s)):
		if s[j] == '0' and (not cau):
			cau = True
			a = 1
		elif s[j] == '0' and cau:
			a += 1
		if s[j] == '1':
			if cau and a > 0:
				aa.append(a)
			cau = False
			a = 0
		if j == len(s) - 1:
			if a > 0:
				aa.append(a)
	left = h
	for j in range(0, len(aa)):
		if left >= 2 * (left - aa[j]):
			left = 2 * (left - aa[j])
	if left <= 0:
		print('YES')
	else:
		print('NO')


t = int(input())
for i in range(t):
	(a, b) = map(int, input().split())
	x = input()
	lt = []
	count = 0
	for i in x:
		if i == '1':
			if count != 0:
				lt.append(count)
			count = 0
		else:
			count += 1
	if count != 0:
		lt.append(count)
	lt.sort(reverse=True)
	flag = 0
	for i in lt:
		if i >= b:
			flag = 1
			print('YES')
			break
		b = 2 * (b - i)
	if flag == 0:
		print('NO')


T = int(input())
while T != 0:
	(l, h) = map(int, input().split())
	s = input()
	arr = []
	count = 0
	for i in s:
		if i == '0':
			count += 1
		else:
			arr.append(count)
			if count == 0 and len(arr) != 0:
				arr.pop()
			count = 0
	if count != 0:
		arr.append(count)
	flag = False
	for free in arr:
		if free > h // 2:
			h = 2 * (h - free)
		if h <= 0:
			flag = True
			break
	if flag:
		print('YES')
	else:
		print('NO')
	T -= 1


for _ in range(int(input())):
	(L, H) = map(int, input().split())
	S = input()
	oc = 0
	z = []
	for ele in S:
		if ele == '0':
			oc += 1
		elif oc != 0:
			z.append(oc)
			oc = 0
	if oc != 0:
		z.append(oc)
	for ele in z:
		if ele > H / 2:
			H = 2 * (H - ele)
		if H <= 0:
			break
	if H <= 0:
		print('YES')
	else:
		print('NO')


from sys import stdin
for __ in range(int(stdin.readline())):
	(l, h) = map(int, stdin.readline().split())
	s = stdin.readline().strip()
	cnt = 0
	for i in s:
		if i == '0':
			cnt += 1
		else:
			if 2 * (h - cnt) < h:
				h = 2 * (h - cnt)
			cnt = 0
	if 2 * (h - cnt) < h:
		h = 2 * (h - cnt)
	print('YES') if h <= 0 else print('NO')


try:
	t = int(input())
	for _ in range(t):
		(l, h) = map(int, input().split())
		s = input()
		arr = []
		cnt = 0
		f = 0
		for i in range(l):
			if s[i] == '0':
				cnt += 1
			if s[i] == '1' and cnt > 0:
				arr.append(cnt)
				cnt = 0
		if cnt > 0:
			arr.append(cnt)
		f = 0
		for i in range(len(arr)):
			if h <= 0:
				f = 1
			if arr[i] > h // 2:
				h = 2 * (h - arr[i])
		if h <= 0:
			print('YES')
		else:
			print('NO')
except:
	pass


t = int(input())
for _ in range(t):
	(n, h) = map(int, input().split())
	s = input()
	arr = []
	count = 0
	for i in range(n):
		if s[i] == '0':
			count = count + 1
		else:
			if count != 0:
				arr.append(count)
			count = 0
	if count != 0:
		arr.append(count)
	ans = 0
	for num in arr:
		if num >= h:
			ans = 1
			break
		if 2 * num > h:
			h = 2 * (h - num)
	if ans == 1:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	(_, h) = map(int, input().split())
	c = input()
	cnt = 0
	for i in c:
		if i == '0':
			cnt += 1
		if i == '1' and cnt:
			rh = 2 * (h - cnt)
			h = rh if rh < h else h
			cnt = 0
		if cnt >= h or h <= 0:
			h = 0
			break
	print('YES' if not h else 'NO')


t = int(input())
for i in range(t):
	(l, h) = map(int, input().split())
	s = input()
	l1 = s.split('1')
	l2 = []
	for j in l1:
		if j != '':
			l2.append(len(j))
	if l2 == []:
		print('NO')
	else:
		for k in l2:
			if k >= h:
				print('YES')
				break
			elif k > h // 2:
				h = 2 * (h - k)
		else:
			print('NO')


t = int(input())
while t > 0:
	(L, H) = map(int, input().split())
	s = input()
	ans = 'NO'
	l1 = s.split('1')
	l2 = list()
	for i in l1:
		l2.append(len(i))
	for x in l2:
		if x < H:
			if x > H // 2:
				H = 2 * (H - x)
			else:
				continue
		else:
			ans = 'YES'
	print(ans)
	t = t - 1


for _ in range(int(input())):
	(l, h) = map(int, input().split())
	sch = input()
	ans = 'NO'
	ones = sch.split('1')
	temp = []
	for i in ones:
		temp.append(len(i))
	for i in temp:
		if i < h:
			if i > h // 2:
				h = 2 * (h - i)
			else:
				continue
		else:
			ans = 'YES'
	print(ans)


from collections import deque, defaultdict, Counter
from itertools import product, groupby, permutations, combinations
from math import gcd, floor, inf
from bisect import bisect_right, bisect_left
cases = int(input())
for _ in range(cases):
	(l, h) = map(int, input().split())
	s = input()
	free = []
	for (i, grp) in groupby(s):
		if i == '0':
			free.append(len(list(grp)))
	if sum(free) < h:
		print('NO')
		continue
	free = free[::-1]
	while h > 0 and free:
		last = free.pop()
		if last * 2 <= h:
			continue
		h = 2 * (h - last)
	if h > 0:
		print('NO')
	else:
		print('YES')


from math import *
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = input()
	a = [[s[0], 1]]
	for i in range(1, n):
		if s[i] == s[i - 1]:
			a[-1][1] += 1
		else:
			a.append([s[i], 1])
	pos = 0
	while pos < len(a):
		if a[pos][0] == '0':
			if a[pos][1] > k // 2:
				k = 2 * (k - a[pos][1])
		pos += 1
	if k <= 0:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	(l, h) = map(int, input().split())
	a = list(input())
	i = 1
	b = []
	s = 0
	if '0' not in a:
		print('NO')
		continue
	if a[0] == '0':
		s = 1
	while i < l:
		if a[i] == '0' and a[i - 1] == '0':
			s += 1
		elif a[i] == '0':
			s = 1
		elif a[i] == '1' and a[i - 1] != '1':
			b.append(s)
		i += 1
	if a[-1] == '0':
		b.append(s)
	for i in b:
		if i <= h and i != 0:
			h = min(2 * (h - i), h)
		else:
			print('YES')
			h = 0
			break
		if h == 0:
			print('YES')
			break
	if h > 0:
		print('NO')


for _ in range(int(input())):
	(l, h) = map(int, input().split())
	s = input()
	a = s.split('1')
	a = ' '.join(a).split()
	flag = 0
	if l == s.count('0'):
		print('YES')
	elif len(a) == 0:
		print('NO')
	else:
		for i in a:
			b = 2 * (h - len(i))
			if b <= h:
				h = b
				if h <= 0:
					flag = 1
					break
		if flag == 0:
			print('NO')
		else:
			print('YES')


for i in range(int(input())):
	flag = False
	(l, h) = [int(i) for i in input().split()]
	s = input()
	s = s.split('1')
	f = []
	s = sorted(s, reverse=True)
	for i in s:
		f.append(len(i))
	if 0 in f:
		f.remove(0)
	if f != None:
		for j in f:
			if j >= h:
				flag = True
				break
			else:
				h = 2 * (h - j)
	if flag:
		print('YES')
	else:
		print('NO')


def cons_count(stri):
	n_s = []
	i = 0
	while i < len(stri):
		if stri[i] == '0':
			c = 1
			j = i + 1
			while j < len(stri):
				if stri[i] == stri[j]:
					c += 1
				else:
					break
				j += 1
			n_s.append(c)
			i += c
			continue
		i += 1
	return n_s

def mainfunc(stri, l, h):
	n_s = cons_count(stri)
	k = 0
	while k < len(n_s) and h:
		if h <= n_s[k]:
			return 'YES'
		else:
			temp = 2 * (h - n_s[k])
			if temp < h:
				h = temp
		k += 1
	return 'NO'
for _ in range(int(input())):
	(l, h) = map(int, input().split())
	stri = input()
	print(mainfunc(stri, l, h))


T = int(input())
for t in range(T):
	(l, h) = map(int, input().split())
	a = list(input())
	for i in range(len(a)):
		a[i] = int(a[i])
	s = []
	c = 0
	for i in range(len(a)):
		if a[i] == 0:
			c += 1
		elif i == 0:
			pass
		elif a[i - 1] == 0:
			s.append(c)
			c = 0
	if c != 0:
		s.append(c)
	s.sort()
	i = len(s) - 1
	while i >= 0:
		h -= s[i]
		if h <= 0:
			break
		h *= 2
		i -= 1
	if h <= 0:
		print('YES')
	else:
		print('NO')


def binarySearch(arr, l, r, x):
	ans = -1
	while l <= r:
		mid = l + (r - l) // 2
		if arr[mid] >= x:
			ans = mid
			r = mid - 1
		else:
			l = mid + 1
	return ans

def continous_zero(s):
	lst = []
	c = 0
	for i in range(len(s) - 1):
		if s[i] == '0':
			if s[i] == s[i + 1]:
				c += 1
				if i == len(s) - 2:
					lst.append(c + 1)
			else:
				lst.append(c + 1)
				c = 0
	lst.sort()
	return lst

def check_slept(lst, l, h):
	while h > lst[-1]:
		h = 2 * (h - lst[-1])
		lst.remove(lst[-1])
		if len(lst) == 0:
			return 'NO'
		else:
			continue
	else:
		return 'YES'
for i in range(int(input())):
	(l, h) = map(int, input().split())
	s = input()
	lst = continous_zero(s)
	if len(lst) != 0:
		print(check_slept(lst, l, h))
	elif h == 1:
		c = 0
		for j in s:
			if j == '0':
				c += 1
		if c != 0:
			print('YES')
		else:
			print('NO')
	else:
		print('NO')


def consc_count(stri):
	res = []
	i = 0
	while i < len(stri):
		if stri[i] == '0':
			c = 1
			j = i + 1
			while j < len(stri):
				if stri[i] == stri[j]:
					c += 1
				else:
					break
				j += 1
			res.append(c)
			i += c
			continue
		i += 1
	res.sort(reverse=True)
	return res

def mainfunc(stri, l, h):
	res = consc_count(stri)
	if res:
		if h <= res[0]:
			return 'YES'
		temp = 2 * (h - res[0])
		ind = 1
		while ind < len(res) and temp:
			if temp <= res[ind]:
				return 'YES'
			temp = 2 * (temp - res[ind])
			ind += 1
	return 'NO'
for _ in range(int(input())):
	(l, h) = map(int, input().split())
	stri = input()
	print(mainfunc(stri, l, h))


for _ in range(int(input())):
	(l, h) = map(int, input().split())
	s = input()
	s = s.split('1')
	l = [len(i) for i in s if len(i) != 0]
	ans = 'NO'
	for i in l:
		if i >= h:
			ans = 'YES'
			break
		elif i > h // 2:
			h = 2 * (h - i)
		else:
			continue
	print(ans)


t = int(input())
while t > 0:
	(l, h) = map(int, input().split())
	s = input()
	units = []
	c = 0
	for i in range(l):
		if s[i] == '0':
			c += 1
		else:
			units.append(c)
			c = 0
	units.append(c)
	units = [i for i in units if i != 0]
	for i in range(len(units)):
		if units[i] > h // 2:
			h = 2 * (h - units[i])
		if h <= 0:
			break
	if h <= 0:
		print('YES')
	else:
		print('NO')
	t -= 1


def compute(S, L, H):
	temp = S.split('1')
	zeroes = []
	for each in temp:
		if len(each) > 0:
			zeroes.append(len(each))
	for zero in zeroes:
		if 2 * (H - zero) < H:
			H = 2 * (H - zero)
		if H <= 0:
			break
	return H <= 0
t = int(input())
for i in range(t):
	(l, h) = [int(x) for x in input().split()]
	s = input()
	ans = compute(s, l, h)
	if ans:
		print('YES')
	else:
		print('NO')


t = int(input())
for i in range(0, t):
	p = input().split(' ')
	l = int(p[0])
	h = int(p[1])
	s = input()
	s = s.split('1')
	ml = []
	for j in s:
		if j != '':
			ml.append(j)
	if len(ml) == 0:
		print('NO')
	else:
		d = dict()
		for var in ml:
			d[var] = len(var)
		d = sorted(d.items(), key=lambda x: x[1], reverse=True)
		flag = 0
		for pp in d:
			current = pp[1]
			if current >= h:
				flag = 1
				print('YES')
				break
			else:
				h = 2 * (h - current)
		if flag == 0:
			print('NO')


try:
	for _ in range(int(input())):
		A = [int(x) for x in input().split()]
		s = input()
		arr = []
		(i, p) = (0, 0)
		while i < len(s):
			if s[i] == '0':
				p += 1
			if s[i] == '1':
				if p != 0:
					arr.append(p)
					p = 0
			i += 1
		if p != 0:
			arr.append(p)
		for j in arr:
			x = 2 * (A[1] - j)
			if x < A[1]:
				A[1] = x
		if A[1] <= 0:
			print('YES')
		else:
			print('NO')
except:
	pass


def get_next_required_sleep(current_required_sleep, start_idle, end_idle):
	sleep_duration = end_idle - start_idle + 1
	next_required_sleep = 0 if sleep_duration >= current_required_sleep else min(current_required_sleep, (current_required_sleep - sleep_duration) * 2)
	return next_required_sleep
n_testcase = int(input())
for testcase in range(n_testcase):
	(day_length, required_sleep) = (int(x) for x in input().split())
	works = input()
	start_idle = day_length
	for (i, work) in enumerate(works):
		if work == '0':
			start_idle = min(start_idle, i)
		if work == '1':
			if start_idle < day_length:
				end_idle = i - 1
				required_sleep = get_next_required_sleep(required_sleep, start_idle, end_idle)
				start_idle = day_length
	if start_idle < day_length:
		end_idle = day_length - 1
		required_sleep = get_next_required_sleep(required_sleep, start_idle, end_idle)
	print('YES' if required_sleep == 0 else 'NO')


for _ in range(int(input())):
	(l, h) = map(int, input().split())
	s = input()[:l]
	lst = s.split('1')
	flag = True
	zeros = []
	for i in lst:
		zeros.append(len(i))
	for i in zeros:
		if i >= h:
			print('YES')
			flag = False
			break
		elif i > h // 2:
			h = 2 * (h - i)
		else:
			continue
	if flag:
		print('NO')


import sys
from os import path
if path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
t = int(sys.stdin.readline().rstrip())
while t > 0:
	t -= 1
	(n, h) = map(int, sys.stdin.readline().rstrip().split())
	a = list(input())
	c = 0
	flag = 0
	s = False
	for x in range(n):
		if a[x] == '0':
			c += 1
		else:
			if c > h / 2:
				h = 2 * (h - c)
			c = 0
			if h < 0:
				break
	if c > h / 2:
		h = 2 * (h - c)
	if h <= 0:
		print('YES')
	else:
		print('NO')


for t in range(int(input())):
	(l, h) = map(int, input().split())
	total = input()
	ans = 'NO'
	l1 = total.split('1')
	l2 = []
	for i in l1:
		l2.append(len(i))
	for i in l2:
		if i < h:
			if i > h // 2:
				h = 2 * (h - i)
			else:
				continue
		else:
			ans = 'YES'
	print(ans)


for _ in range(int(input())):
	(l, h) = list(map(int, input().split()))
	s = input().split('1')
	a = []
	for i in s:
		a += [len(i)]
	a.sort(reverse=True)
	for i in a:
		if i == 0 or h <= 0:
			break
		h = (h - i) * 2
	if h > 0:
		print('NO')
	else:
		print('YES')