Chef has $N$ small boxes arranged on a line from $1$ to $N$. For each valid $i$, the weight of the $i$-th box is $W_i$. Chef wants to bring them to his home, which is at the position $0$. He can hold any number of boxes at the same time; however, the total weight of the boxes he's holding must not exceed K at any time, and he can only pick the ith box if all the boxes between Chef's home and the ith box have been either moved or picked up in this trip.
Therefore, Chef will pick up boxes and carry them home in one or more round trips. Find the smallest number of round trips he needs or determine that he cannot bring all boxes home.

-----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 $N$ and $K$.
- The second line contains $N$ space-separated integers $W_1, W_2, \ldots, W_N$.

-----Output-----
For each test case, print a single line containing one integer ― the smallest number of round trips or $-1$ if it is impossible for Chef to bring all boxes home.

-----Constraints-----
- $1 \le T \le 100$
- $1 \le N, K \le 10^3$
- $1 \le W_i \le 10^3$ for each valid $i$

-----Example Input-----
4
1 1 
2
2 4
1 1
3 6
3 4 2
3 6
3 4 3

-----Example Output-----
-1
1
2
3

-----Explanation-----
Example case 1: Since the weight of the box higher than $K$, Chef can not carry that box home in any number of the round trip.
Example case 2: Since the sum of weights of both boxes is less than $K$, Chef can carry them home in one round trip.
Example case 3: In the first round trip, Chef can only pick up the box at position $1$. In the second round trip, he can pick up both remaining boxes at positions $2$ and $3$.
Example case 4: Chef can only carry one box at a time, so three round trips are required.

Source: codechef | Difficulty: EASY
Tags: Greedy algorithms

Constructive algorithms

Implementation

Ad-hoc


Solutions:
T = int(input())
for _ in range(T):
	(N, K) = map(int, input().split())
	Wi = list(map(int, input().split()))
	W0 = max(Wi)
	sum = 0
	trip = 1
	while len(Wi) > 0:
		sum = sum + Wi[0]
		if sum <= K:
			Wi.pop(0)
		else:
			trip += 1
			sum = Wi.pop(0)
	if W0 > K:
		trip = -1
	print(trip)


for _ in range(int(input())):
	(w, k) = list(map(int, input().split()))
	l = list(map(int, input().split()))
	if max(l) <= k:
		i = 0
		r = 0
		while i < w:
			a = 0
			for j in range(w - i):
				a += l[i + j]
				if a > k:
					j -= 1
					break
			r += 1
			i += j + 1
		print(r)
	else:
		print(-1)


t = int(input())
while t > 0:
	(n, k) = map(int, input().split())
	w = list(map(int, input().split()))
	sum = 0
	c = 0
	f = 0
	for i in range(n):
		if w[i] > k:
			f = 1
			break
	if f == 1:
		print(-1)
	elif f != 1:
		for i in range(n):
			if sum + w[i] <= k:
				sum = sum + w[i]
			else:
				c = c + 1
				sum = w[i]
		print(c + 1)
	t = t - 1


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	ans = 1
	sum = 0
	j = 0
	while j < n:
		if l[j] > k:
			ans = -1
			break
		if sum + l[j] > k:
			sum = 0
			ans += 1
		else:
			sum = sum + l[j]
			j += 1
	if ans >= 0:
		print(ans)
	else:
		print(-1)


for t in range(int(input())):
	(n, k) = map(int, input().split())
	l = [int(x) for x in input().split()]
	ans = 0
	trip = 0
	for i in range(n):
		if l[i] > k:
			trip = -1
			break
		ans += l[i]
		if ans > k:
			ans = l[i]
			if i == n - 1:
				trip += 1
			trip += 1
		elif i == n - 1:
			trip += 1
	print(trip)


t = int(input())
while t != 0:
	(n, k) = map(int, input().split())
	w = list(map(int, input().split()))
	(s, trips) = (0, 1)
	for i in w:
		if i > k:
			trips = -1
			break
		elif i <= k:
			s += i
			if s > k:
				trips += 1
				s = i
	print(trips)
	t -= 1


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	if max(a) > k:
		print(-1)
	else:
		c = 0
		s = 0
		for i in range(n):
			if s + a[i] <= k:
				s += a[i]
			else:
				s = a[i]
				c += 1
		print(c + 1)


T = int(input())
for _ in range(T):
	(n, k) = map(int, input().split())
	w = list(map(int, input().split()))
	round1 = 0
	cum = 0
	if max(w) > k:
		print(-1)
	else:
		for i in range(n):
			cum += w[i]
			if cum > k:
				round1 += 1
				cum = w[i]
			elif cum == k:
				round1 += 1
				cum = 0
		else:
			if cum > 0:
				round1 += 1
			print(round1)


t = int(input())
for i in range(t):
	(a, b) = map(int, input().split())
	w = list(map(int, input().split()))
	total_weight = 0
	counts = 1
	for j in range(a):
		if w[j] > b:
			counts = -1
			break
		if total_weight + w[j] <= b:
			total_weight += w[j]
		else:
			counts += 1
			total_weight = w[j]
	print(counts)


from math import *
import sys

def input():
	return sys.stdin.readline().replace('\n', '').strip()
sys.setrecursionlimit(10 ** 9)
for _ in range(int(input())):
	(n, k) = list(map(int, input().split()))
	l = list(map(int, input().split()))
	s = 0
	ans = 0
	box_c = 0
	for i in range(n):
		if l[i] > k:
			ans = -1
			break
		if s + l[i] > k:
			if box_c == 0:
				ans = -1
				break
			else:
				box_c = 1
				ans += 1
				s = l[i]
		else:
			s += l[i]
			box_c += 1
	else:
		if s != 0 and box_c > 0:
			ans += 1
	print(ans)


T = int(input())
while T:
	(N, K) = map(int, input().split())
	Weight = list(map(int, input().split()))
	flag = 0
	final_digit = 0
	count = 0
	visited = []
	if N == 1:
		if Weight[0] > K:
			flag = 1
		else:
			count += 1
	else:
		sum = 0
		for i in range(N - 1):
			if i not in visited:
				if Weight[i] > K:
					flag = 1
					break
				else:
					visited.append(i)
					sum = Weight[i]
					j = i + 1
					for j in range(j, N):
						if sum + Weight[j] > K:
							if j == N - 1:
								final_digit = 1
							break
						else:
							visited.append(j)
							sum = sum + Weight[j]
				count += 1
		if final_digit == 1:
			if Weight[N - 1] > K:
				flag = 1
			else:
				count += 1
	if flag == 1:
		print(-1)
	else:
		print(count)
	T -= 1


def counting(lst, a, b):
	c = 1
	k = b
	for i in range(a):
		b -= lst[i]
		if b == 0 and i + 1 < a:
			c += 1
			b = k
		elif b < 0:
			c += 1
			b = k
			b -= lst[i]
	return c
for i in range(int(input())):
	(a, b) = map(int, input().split())
	lst = list(map(int, input().split()))
	if max(lst) <= b:
		print(counting(lst, a, b))
	else:
		print(-1)


a = int(input())
for i in range(a):
	(m, o) = input().split()
	(n, k) = [int(m), int(o)]
	b = list(map(int, input().split()))
	u = 0
	z = 1
	for j in b:
		if j > k:
			z = 0
			break
		elif u + j <= k:
			u = u + j
		else:
			u = j
			z = z + 1
	if z == 0:
		print(-1)
	else:
		print(z)


for _ in range(int(input())):
	(n, k) = list(map(int, input().split()))
	W = list(map(int, input().split()))
	W_cp = W.copy()
	count = 1
	curr = 0
	for (i, w) in enumerate(W):
		if w > k:
			count = -1
			break
		curr += w
		if curr > k:
			curr = w
			count += 1
	print(count)


t = int(input())
for i in range(t):
	(n, k) = list(map(int, input().split()))
	l = list(map(int, input().split()))
	if max(l) > k:
		print(-1)
	else:
		s = 0
		op = 0
		for i in range(len(l)):
			s += l[i]
			if s <= k:
				pass
			else:
				s -= l[i]
				s = 0
				s += l[i]
				op += 1
		print(op + 1)


for _ in range(int(input())):
	(N, K) = list(map(int, input().split()))
	W = list(map(int, input().split()))
	(carry, trips) = (0, 0)
	for Wi in W:
		if Wi > K:
			print('-1')
			break
		if carry + Wi <= K:
			carry += Wi
		else:
			trips += 1
			carry = Wi
	else:
		print(trips + 1)


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	w = list(map(int, input().split()))
	curr_w = 0
	trips = 0
	for wi in w:
		if wi > k:
			trips = -2
			break
		elif curr_w + wi > k:
			trips += 1
			curr_w = wi
		else:
			curr_w += wi
	print(trips + 1)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	w = list(map(int, input().split()))
	c = 0
	i = 0
	a = 0
	while i < len(w):
		if w[i] > k:
			print(-1)
			break
		a = a + w[i]
		if a > k:
			c = c + 1
			a = w[i]
		if i == len(w) - 1:
			c = c + 1
		i = i + 1
	else:
		if c == 0:
			print(1)
		else:
			print(c)


T = int(input())
for i in range(T):
	(N, K) = map(int, input().split())
	w = list(map(int, input().split()))
	if max(w) <= K:
		x = y = 0
		for i in range(len(w)):
			x += w[i]
			if x > K:
				y += 1
				x = w[i]
		if x > 0:
			y += 1
		print(y)
	else:
		print('-1')


try:
	for t in range(int(input())):
		(n, k) = list(map(int, input().split()))
		l = list(map(int, input().split()))
		c = 0
		z = k
		for j in range(0, n):
			if l[j] <= z:
				z = z - l[j]
				if j + 1 < n and l[j + 1] > z:
					z = k
					c = c + 1
			else:
				c = -2
				break
		if c == -2:
			print(-1)
		else:
			print(c + 1)
except EOFError as e:
	pass


MOD = 1000000007
for _ in range(int(input())):
	(n, k) = list(map(int, input().split()))
	weights = list(map(int, input().split()))
	if max(weights) > k:
		print(-1)
	else:
		carry = 0
		rounds = 0
		for w in weights:
			if carry + w <= k:
				carry += w
			else:
				rounds += 1
				carry = w
		if carry > 0:
			rounds += 1
		print(rounds)


for _ in range(int(input())):
	(n, k) = list(map(int, input().strip().split()))
	string = list(map(int, input().strip().split()))
	count = 1
	temp = k
	for i in string:
		if i > k:
			count = -1
			break
		temp -= i
		if temp < 0:
			temp = k - i
			count += 1
	print(count)


t = int(input())
for i in range(1, t + 1):
	(n, k) = map(int, input().split())
	s = 0
	p = 1
	l = []
	l = list(map(int, input().split()))
	for w in range(n):
		s = s + l[w]
		if l[w] > k:
			p = -1
			break
		if s > k:
			s = l[w]
			p += 1
			continue
	print(p)


def fun(lst, k):
	weight = 0
	ans = 1
	for el in lst:
		if el > k:
			return -1
		elif weight + el <= k:
			weight += el
		else:
			ans += 1
			weight = el
	return ans
for _ in range(int(input())):
	(n, k) = list(map(int, input().split()))
	lst = [int(i) for i in input().split()]
	print(fun(lst, k))


T = int(input())
for i in range(T):
	(N, K) = map(int, input().split())
	l = list(map(int, input().split()))
	b = 0
	for i in l:
		if i > K:
			print(-1)
			b = 1
			break
	if b == 1:
		continue
	t = 0
	l1 = []
	while sum(l) > 0:
		t += 1
		for i in range(len(l)):
			if sum(l1) + l[i] <= K:
				l1.append(l[i])
			else:
				break
		for i in l1:
			l.remove(i)
		l1.clear()
	print(t)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	w = [int(x) for x in input().split()]
	ans = 0
	cur = 0
	i = 0
	while i < n:
		if w[i] > k:
			ans = -1
			break
		if cur + w[i] > k:
			ans += 1
			cur = 0
		else:
			cur += w[i]
			i += 1
	if ans == -1:
		print(-1)
	else:
		print(ans + 1)


t = int(input())
for i in range(t):
	(x, y) = (0, 0)
	(n, m) = list(map(int, input().split()))
	l = list(map(int, input().split()))
	if max(l) > m:
		print(-1)
	else:
		for i in range(len(l)):
			y += l[i]
			if y > m:
				y = l[i]
				x += 1
		if y > 0:
			x += 1
		print(x)


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	w = list(map(int, input().split()))
	T = 0
	p = []
	flag = 0
	for j in range(n):
		if w[j] > k:
			print(-1)
			flag = 1
			break
		if T + w[j] <= k:
			T = T + w[j]
		else:
			T = 0
			T = T + w[j]
			p.append(T)
	if flag == 0:
		print(len(p) + 1)


def numbercount(k, w):
	prev = w[0]
	rounds = 0
	if w[0] > k:
		return '-1'
	for weight in w[1:]:
		if weight > k:
			return '-1'
		if weight + prev > k:
			rounds += 1
			prev = weight
		else:
			prev += weight
	rounds += 1
	return rounds
for _ in range(int(input())):
	N = list(map(int, input().split()))
	(n, k) = (N[0], N[1])
	w = list(map(int, input().split()))
	print(numbercount(k, w))


def chefandwork():
	test = int(input().strip())
	for t in range(test):
		(n, k) = [int(x) for x in input().strip().split(' ')]
		weights = [int(x) for x in input().strip().split(' ')]
		trips = 1
		tripW = 0
		for w in range(len(weights)):
			if weights[w] > k:
				trips = -1
				break
			tripW += weights[w]
			if tripW > k:
				tripW = weights[w]
				trips += 1
		print(trips)
chefandwork()


for _ in range(int(input())):
	(n, k) = list(map(int, input().split()))
	arr = list(map(int, input().split()))
	count = 0
	flag = True
	curr_sum = 0
	for i in arr:
		if i > k:
			flag = False
		else:
			curr_sum += i
			if curr_sum > k:
				curr_sum = i
				count += 1
	if curr_sum <= k:
		count += 1
	if flag == False:
		print(-1)
	else:
		print(count)


for _ in range(int(input())):
	(n, w) = map(int, input().split())
	a = list(map(int, input().split()))
	s = 0
	c = 0
	b = []
	for i in range(n):
		if a[i] > w:
			c = 1
			break
		elif s + a[i] < w:
			s += a[i]
			if i == n - 1:
				b.append(s + a[i])
		elif s + a[i] == w:
			s = s + a[i]
			b.append(s)
			s = 0
		elif i == n - 1:
			b.append(s)
			b.append(a[i])
		else:
			b.append(s)
			s = a[i]
	if c:
		print(-1)
	else:
		print(len(b))


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))[:n]
	if max(l) > k:
		print('-1')
	else:
		count = 0
		s = 0
		for i in range(n):
			if s + l[i] <= k:
				s += l[i]
			else:
				s = l[i]
				count += 1
		print(count + 1)


t = int(input())
while t > 0:
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	sum = 0
	c = 0
	f = 0
	for j in range(0, n):
		if l[j] > k:
			f = 1
			break
	if f == 1:
		print('-1')
	elif f != 1:
		for j in range(0, n):
			if sum + l[j] <= k:
				sum = sum + l[j]
			else:
				c = c + 1
				sum = l[j]
		print(c + 1)
	t = t - 1


t = int(input())
for ni in range(t):
	(n, k) = map(int, input().split())
	l = [int(i) for i in input().split()]
	if max(l) > k:
		print(-1)
	else:
		count = 0
		suml = 0
		i = 0
		while i < n:
			if suml + l[i] <= k:
				suml = suml + l[i]
			else:
				count = count + 1
				suml = l[i]
			i = i + 1
		print(count + 1)


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	w = list(map(int, input().split()))
	count = 0
	sum = 0
	if max(w) > k:
		print(-1)
	else:
		for j in w:
			if sum + j <= k:
				sum += j
			else:
				sum = j
				count += 1
		print(count + 1)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	w = list(map(int, input().split()))
	l = 0
	trips = 0
	while len(w) > 0:
		if w[0] <= k:
			l += w[0]
			if l <= k:
				w.pop(0)
				continue
			else:
				trips += 1
				l = 0
				continue
		else:
			print(-1)
			break
	else:
		trips += 1
		print(trips)


for i in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	c = 1
	s = 0
	for i in a:
		s += i
		if i > k:
			c = -1
			break
		elif s > k:
			s = i
			c += 1
	if c == 0:
		print('-1')
	else:
		print(c)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	br = 0
	for i in l:
		if i > k:
			print(-1)
			br = 1
			break
	if br == 1:
		continue
	t = 0
	l2 = []
	while sum(l) > 0:
		t += 1
		for i in range(len(l)):
			if sum(l2) + l[i] <= k:
				l2.append(l[i])
			else:
				break
		for i in l2:
			l.remove(i)
		l2.clear()
	print(t)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	w = list(map(int, input().split()))
	r = 0
	c = 0
	if max(w) > k:
		print(-1)
	else:
		for i in range(n):
			c += w[i]
			if c > k:
				r += 1
				c = w[i]
			elif c == k:
				r += 1
				c = 0
		else:
			if c > 0:
				r += 1
			print(r)


for i in range(int(input())):
	(n, k) = list(map(int, input().split()))
	l = list(map(int, input().split()))
	ro = 0
	s = 0
	f = 1
	for i in range(n):
		if l[i] > k:
			print(-1)
			f = 0
			break
		s += l[i]
		if s > k:
			s = l[i]
			ro += 1
	if s and f:
		print(ro + 1)
	elif f:
		print(ro)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	count = 0
	w = 0
	for i in arr:
		if i > k:
			count = -2
			break
		if w + i <= k:
			w += i
		else:
			w = i
			count += 1
	print(count + 1)


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	w = list(map(int, input().split()))
	c = 0
	ans = 0
	for i in w:
		if i > k:
			ans = -2
			break
		if c + i <= k:
			c += i
		else:
			c = i
			ans += 1
	print(ans + 1)


T = int(input())
for t in range(T):
	(N, K) = map(int, input().split())
	W = list(map(int, input().split()))
	count = 1
	sumW = 0
	for i in W:
		sumW += i
		if i > K:
			count -= count + 1
			break
		elif sumW > K:
			sumW = i
			count += 1
	print(count)


t = int(input())
for _ in range(t):
	(n, k) = [int(x) for x in input().split()]
	w = [int(x) for x in input().split()]
	i = 0
	total = 0
	c = 0
	flag = 0
	while i < n:
		if w[i] > k:
			flag = 1
			break
		total += w[i]
		if total > k:
			total = 0
			c += 1
		else:
			i += 1
	if flag == 1:
		print(-1)
	else:
		print(c + 1)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	w = list(map(int, input().split()))
	c = 1
	t = 0
	for i in w:
		if i > k:
			c = -1
			break
		elif i <= k:
			t += i
			if t > k:
				c += 1
				t = i
	print(c)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	weights = list(map(int, input().split()))
	trips = 1
	if max(weights) > k:
		print(-1)
	else:
		summ = 0
		i = 0
		while i < n:
			if summ + weights[i] <= k:
				summ = summ + weights[i]
			else:
				summ = weights[i]
				trips += 1
			i += 1
		print(trips)


for i in range(int(input())):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	m = max(l)
	(count, t) = (0, 0)
	if m > k:
		print('-1')
	else:
		for x in l:
			count = count + x
			if count > k:
				t += 1
				count = x
			elif count == k:
				t += 1
				count = 0
		if count != 0:
			t += 1
		print(t)


T = int(input())
for i in range(T):
	(n, k) = map(int, input().split())
	w = list(map(int, input().split()))
	highest = max(w)
	total = 0
	count = 1
	j = 0
	while j < n and highest <= k:
		total = total + w[j]
		if total > k:
			count = count + 1
			total = 0
			j = j - 1
		j = j + 1
	if highest > k:
		print(-1)
	else:
		print(count)


l = int(input())
for i in range(l):
	n = input().split()
	k = int(n[1])
	ws = list(map(int, input().split(' ')))
	flag = False
	for w in ws:
		if w > k:
			flag = True
			print(-1)
			break
	if flag:
		continue
	p = 0
	r = 0
	while p < len(ws):
		r = r + 1
		c = 0
		t = len(ws)
		while p < t and c + ws[p] <= k:
			c = c + ws[p]
			p = p + 1
	print(r)


import math
for i in range(int(input())):
	(n, k) = map(int, input().split())
	weights = list(map(int, input().split()))
	trips = 1
	tripw = 0
	for i in range(n):
		if weights[i] > k:
			trips = -1
			break
		tripw += weights[i]
		if tripw > k:
			tripw = weights[i]
			trips += 1
	print(trips)


for _ in range(int(input())):
	(N, K) = map(int, input().split())
	W = list(map(int, input().split()))
	if max(W) > K:
		print(-1)
		continue
	cum = 0
	count = 0
	for i in range(N):
		cum += W[i]
		if cum > K:
			count += 1
			cum = W[i]
		elif cum == K:
			count += 1
			cum = 0
	else:
		if cum > 0:
			count += 1
	print(count)


for __ in range(int(input())):
	(n, k) = list(map(int, input().split()))
	arr = list(map(int, input().split()))
	i = 0
	c = 0
	while True:
		if arr[i] > k:
			ans = -1
			break
		else:
			w = 0
			flag = 0
			for j in range(i, n):
				if w + arr[j] <= k:
					w += arr[j]
					flag = 1
					i = j + 1
				else:
					i = j
					break
			if flag == 1:
				c += 1
				ans = c
			if i >= n:
				break
	print(ans)


o = int(input())
for i in range(o):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	c = 1
	v = 0
	for i in l:
		v += i
		if i > k:
			c = -1
			break
		elif v > k:
			v = i
			c += 1
	if c == 0:
		print('-1')
	else:
		print(c)


for t in range(int(input())):
	(n, k) = map(int, input().split())
	w = list(map(int, input().split(' ')))
	c = 1
	t = 0
	if max(w) > k:
		print(-1)
	else:
		for i in range(n):
			if t + w[i] <= k:
				t += w[i]
			else:
				c += 1
				t = w[i]
		print(c)


t = int(input())
while t:
	(n, k) = list(map(int, input().split()))
	arr = list(map(int, input().split()))
	ans = 0
	temp = 0
	if max(arr) > k:
		print(-1)
		t -= 1
		continue
	for a in arr:
		if a > k:
			break
		if temp + a > k:
			ans += 1
			temp = a
		elif temp + a == k:
			ans += 1
			temp = 0
		else:
			temp += a
	if temp < k and temp != 0:
		ans += 1
	if ans == 0:
		ans = -1
	print(ans)
	t -= 1


for _ in range(int(input())):
	(N, K) = map(int, input().split())
	A = list(map(int, input().split()))
	if max(A) > K:
		print('-1')
	else:
		count = 0
		s = 0
		for i in range(N):
			if s + A[i] <= K:
				s += A[i]
			else:
				s = A[i]
				count += 1
		print(count + 1)


for t in range(int(input())):
	(n, k) = map(int, input().split())
	B = list(map(int, input().split()))
	flag = 1
	w = 0
	for i in range(n):
		if B[i] > k:
			flag = 0
			break
		elif w + B[i] <= k:
			w += B[i]
		else:
			w = B[i]
			flag += 1
	if flag == 0:
		print('-1')
	else:
		print(flag)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	list_a = list(map(int, input().split()))
	sum = 0
	result = 1
	for char in list_a:
		if char > k:
			result = -1
			break
		elif char <= k:
			sum += char
			if sum <= k:
				continue
			elif sum > k:
				result += 1
				sum = char
	print(result)


t = int(input())
for tc in range(t):
	(n, k) = map(int, input().split())
	w = list(map(int, input().split()))
	s = 0
	x = 1
	for j in w:
		s += j
		if j > k:
			x = -1
			break
		elif s > k:
			s = j
			x += 1
	if x == 0:
		print('-1')
	else:
		print(x)


for t in range(int(input())):
	(n, k) = map(int, input().split())
	w = list(map(int, input().split()))
	(i, j) = (0, 0)
	r = 0
	while j != n:
		if sum(w[i:j + 1]) < k:
			j += 1
			if j == n:
				r += 1
		elif sum(w[i:j + 1]) == k:
			r += 1
			j += 1
			i = j
		else:
			i = j
			if w[i] > k:
				j = n
				r = -1
			else:
				r += 1
	print(r)


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	w = list(map(int, input().split()))
	count = 0
	while w != []:
		w1 = []
		for i in range(n):
			if sum(w1) + w[i] <= k:
				w1.append(w[i])
			else:
				break
		if w1 == []:
			count = -1
			break
		else:
			w[:len(w1)] = []
			n -= len(w1)
			count += 1
	print(count)


T = int(input())
N = K = 0
while T > 0:
	string = input() + ' '
	k1 = ''
	count = 0
	for i in range(len(string)):
		if string[i] != ' ':
			k1 = k1 + string[i]
		else:
			count += 1
			if count == 1:
				N = int(k1)
			elif count == 2:
				K = int(k1)
			k1 = ''
	string = input() + ' '
	A = []
	A.append('')
	for i in range(len(string)):
		if string[i] != ' ':
			k1 = k1 + string[i]
		else:
			A.append(int(k1))
			k1 = ''
	sum = 0
	count = 0
	isBool = True
	for i in range(1, len(A)):
		if sum + A[i] <= K:
			sum = sum + A[i]
		elif A[i] > K:
			isBool = False
			break
		else:
			count += 1
			sum = A[i]
	if isBool == True:
		print(count + 1)
	else:
		print(-1)
	T -= 1


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	if max(arr) > k:
		print(-1)
	else:
		count = 0
		while arr != []:
			weight = 0
			for i in range(arr.__len__()):
				if weight + arr[i] > k:
					weight = 0
					arr = arr[i:]
					count += 1
					break
				weight += arr[i]
			if 1 <= sum(arr) <= k:
				arr = []
				count += 1
		print(count)


t = int(input())
for _ in range(t):
	(n, k) = list(map(int, input().split()))
	w = list(map(int, input().split()))
	p = 0
	ans = 0
	flag = False
	while p < n:
		pick = 0
		if w[p] > k:
			flag = True
			break
		else:
			while p < n:
				if pick + w[p] <= k:
					pick += w[p]
					p += 1
				else:
					break
			ans += 1
			pick = 0
	if flag:
		print(-1)
	else:
		print(ans)


import sys

def get_ints():
	return map(int, sys.stdin.readline().strip().split())

def get_array():
	return list(map(int, sys.stdin.readline().strip().split()))
for t in range(int(input())):
	(N, K) = get_ints()
	B = get_array()
	flag = 1
	w = 0
	for i in range(N):
		if B[i] > K:
			flag = 0
			break
		elif w + B[i] <= K:
			w += B[i]
		else:
			w = B[i]
			flag += 1
	if flag == 0:
		print('-1')
	else:
		print(flag)


T = int(input())
for j in range(T):
	(N, K) = map(int, input().split())
	W = list(map(int, input().split(' ')))
	C = 0
	s = 0
	if max(W) > K:
		print(-1)
	else:
		for i in range(N):
			if s + W[i] <= K:
				s += W[i]
			else:
				s = W[i]
				C += 1
		print(C + 1)


for i in range(int(input())):
	(N, K) = map(int, input().split())
	L = list(map(int, input().split()))
	T = 0
	p = []
	flag = 0
	for j in range(N):
		if L[j] > K:
			print(-1)
			flag = 1
			break
		if T + L[j] <= K:
			T = T + L[j]
		else:
			T = 0
			T = T + L[j]
			p.append(T)
	if flag == 0:
		print(len(p) + 1)


for _ in range(int(input())):
	(n, k) = list(map(int, input().split()))
	s = 0
	res = 0
	for i in map(int, input().split()):
		if i > k:
			res = -1
			s = 0
			break
		if s + i <= k:
			s += i
		else:
			s = i
			res += 1
	if s > 0:
		res += 1
	print(res)