There are N cities and N directed roads in Steven's world. The cities are numbered from 0 to N - 1. Steven can travel from city i to city (i + 1) % N, ( 0-> 1 -> 2 -> .... -> N - 1 -> 0). 

Steven wants to travel around the world by car. The capacity of his car's fuel tank is C gallons. There are a[i] gallons he can use at the beginning of city i and the car takes b[i] gallons to travel from city i to (i + 1) % N.  

How many cities can Steven start his car from so that he can travel around the world and reach the same city he started? 

Note  

The fuel tank is initially empty. 

Input Format

The first line contains two integers (separated by a space): city number N and capacity C. 

The second line contains N space-separated integers: a[0], a[1], … , a[N - 1]. 

The third line contains N space-separated integers: b[0], b[1], … , b[N - 1].  

Constraints

2 ≤ N ≤ $10^{5}$

1 ≤ C ≤ $10^{18} $

0 ≤ a[i], b[i] ≤ $10^{9}  $

Output Format

The number of cities which can be chosen as the start city.

Sample Input
3 3
3 1 2
2 2 2

Sample Output
2

Explanation

Steven starts from city 0, fills his car with 3 gallons of fuel, and use 2 gallons of fuel to travel to city 1. His fuel tank now has 1 gallon of fuel. 

On refueling 1 gallon of fuel at city 1, he then travels to city 2 by using 2 gallons of fuel. His fuel tank is now empty. 

On refueling 2 gallon of fuel at city 2, he then travels back to city 0 by using 2 gallons of fuel.  

Here is the second possible solution. 

Steven starts from city 2, fill his car with 2 gallons, and travels to city 0. 

On refueling 3 gallons of fuel from city 0, he then travels to city 1, and exhausts 2 gallons of fuel. His fuel tank contains 1 gallon of fuel now.
He can then refuel 1 gallon of fuel at City 1, and increase his car's fuel to 2 gallons and travel to city 2. 

However, Steven cannot start from city 1, because he is given only 1 gallon of fuel, but travelling to city 2 requires 2 gallons. 

Hence the answer 2.

Source: hackerrank | Difficulty: MEDIUM
Tags: Dynamic programming


Solutions:
def travel(cap, fuel, costs):
	fuel = list(fuel)
	costs = list(costs)
	n = len(fuel)
	req = [0] * n
	for _ in range(2):
		for i in reversed(range(n)):
			nexti = (i + 1) % n
			req[i] = max(0, req[nexti] + costs[i] - fuel[i])
			if min(req[i] + fuel[i], cap) - costs[i] < req[nexti]:
				return 0
	return sum((1 for r in req if r == 0))

def main():
	(cities, capacity) = map(int, input().split())
	fuel = map(int, input().split())
	costs = map(int, input().split())
	print(travel(capacity, fuel, costs))
main()


def getCount(C, a, b):
	(fuel, fuelmin) = (0, (0, 0))
	for i in range(0, N):
		fuel += a[i] - b[i]
		if fuel < fuelmin[0]:
			fuelmin = (fuel, i + 1)
	(s, fuel, FuelDiff) = (fuelmin[1], 0, [])
	for i in range(0, N):
		c = (s + i) % N
		fuel += a[c]
		if fuel > C:
			fuel = C
		fuel -= b[c]
		if fuel < 0:
			return 0
		FuelDiff.append(a[c] - b[c])
	(fuelNeeded, count) = (0, 0)
	for i in range(N - 1, -1, -1):
		fuelNeeded -= FuelDiff[i]
		if fuelNeeded <= 0:
			count += 1
			fuelNeeded = 0
	return count
(N, C) = [int(x) for x in input().strip().split(' ')]
a = [int(x) for x in input().strip().split(' ')]
b = [int(x) for x in input().strip().split(' ')]
print(getCount(C, a, b))


(N, C) = [int(_) for _ in input().split()]
a = [int(_) for _ in input().split()]
b = [int(_) for _ in input().split()]

def nbCity(N, C, a, b):
	start = 0
	while start < N:
		(c, valid) = (0, True)
		for i in range(N):
			c = min(C, c + a[(start + i) % N])
			if c < b[(start + i) % N]:
				start = start + i + 1
				valid = False
				break
			else:
				c -= b[(start + i) % N]
		if valid:
			break
	if start >= N:
		return 0
	(c, count) = (0, 1)
	for i in range(1, N):
		c = max(c + b[(start - i) % N] - min(C, a[(start - i) % N]), 0)
		if c == 0:
			count += 1
	return count
print(nbCity(N, C, a, b))


(n, c) = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
a *= 2
b *= 2
s = 0
need = [0] * (n + n + n)
st = 0
i = 0
while i < n + n:
	st += a[i]
	if c < st:
		st = c
	st -= b[i]
	if st < 0:
		st = 0
		s = i + 1
	i += 1
if s >= n:
	ans = 0
else:
	ans = 1
	need[s + n] = 0
	i = 1
	while i < n:
		d = s + n - i
		if a[d] < c:
			cap = a[d]
		else:
			cap = c
		pac = need[d + 1] + b[d] - cap
		if pac > 0:
			need[d] = pac
		else:
			need[d] = 0
		if need[d] == 0:
			ans += 1
		i += 1
print(ans)


import sys

def travel(fuels, paths, num, cap):
	start_index = 0
	cur_city = start_index
	fuel_gathered = 0
	while (cur_city != (start_index - 1) % num or paths[cur_city] > min(fuel_gathered + fuels[cur_city], cap)) and start_index < num:
		fuel_gathered = min(fuel_gathered + fuels[cur_city], cap)
		if paths[cur_city] > fuel_gathered:
			if cur_city == start_index - 1:
				start_index = start_index + 1
			else:
				start_index = cur_city + 1
			cur_city = start_index % num
			fuel_gathered = 0
		else:
			cur_city = (cur_city + 1) % num
			fuel_gathered = fuel_gathered - paths[cur_city]
	if start_index == num:
		return 0
	start_count = 1
	fuels_list = [0] * num
	for i in range(1, num):
		fuel_amount = min(cap, fuels[(start_index - i) % num]) - paths[(start_index - i) % num]
		if fuel_amount < 0:
			fuels_list[(start_index - i) % num] = fuels_list[(start_index - i + 1) % num] + fuel_amount
		else:
			fuels_list[(start_index - i) % num] = min(0, fuels_list[(start_index - i + 1) % num] + fuel_amount)
		if fuels_list[(start_index - i) % num] >= 0:
			start_count += 1
	return start_count
first = sys.stdin.readline().split(' ')
n = int(first[0])
c = int(first[1])
a = list((int(p) for p in sys.stdin.readline().split(' ')))
b = list((int(p) for p in sys.stdin.readline().split(' ')))
print(travel(a, b, n, c))


(N, C) = tuple(map(int, input().split()))
A = tuple(map(int, input().split()))
B = tuple(map(int, input().split()))
Net = [min(A[i], C) - B[i] for i in range(N)]
Need = [0] * (2 * N)
NoUse = False
for i in range(2 * N - 2, -1, -1):
	nI = i if i < N else i - N
	if Need[i + 1] > 0 and B[nI] >= C:
		NoUse = True
	if NoUse:
		Need[i] = 65535
	else:
		Need[i] = max(Need[i + 1] - Net[nI], 0)
print(len(list(filter(lambda x: x == 0, Need[:N]))))


(N, C) = map(int, input().split())
A = [int(x) for x in input().split()]
B = [int(x) for x in input().split()]
A = A * 2
B = B * 2
R = [0 for x in range(2 * N + 1)]
for i in range(2 * N - 1, -1, -1):
	R[i] = R[i + 1] + B[i]
	if R[i] > C:
		print(0)
		exit()
	else:
		R[i] = max(0, R[i] - A[i])
print(sum([1 for i in range(N) if R[i] == 0]))


(N, C) = [int(el) for el in input().split()]
a = [int(el) for el in input().split()]
b = [int(el) for el in input().split()]

def finding_sol(N, k_double):
	k2 = k_double
	binCity = []
	temp_min = k2[-1]
	temp_max = k2[-1]
	tank_ranges = []
	for i in range(2 * N - 1, -1, -1):
		if i < N and k2[i] < temp_min:
			tank_ranges.append(temp_max - temp_min)
			break
		elif k2[i] <= temp_min:
			tank_ranges.append(temp_max - temp_min)
			temp_min = k2[i]
			temp_max = temp_min
			binCity.insert(0, 1)
		else:
			binCity.insert(0, 0)
			if k2[i] > temp_max:
				temp_max = k2[i]
	necessary_tank = max(tank_ranges)
	sol = sum(binCity[:N])
	return (sol, necessary_tank)

def cum_sum(a):
	n = len(a)
	csum = [a[0]] * n
	for i in range(1, n):
		csum[i] = a[i] + csum[i - 1]
	return csum
c = [ai - bi for (ai, bi) in zip(a, b)]
c = tuple(c)
c2 = c + c
k = cum_sum(c)
k_balance = k[-1]
n_double = tuple(range(-N, N))
k_0 = [ki - k_balance for ki in k]
k_double = k_0 + k
k_double = tuple(k_double)
lost_gas = 0
for i in range(1, N):
	if a[i] + c[i - 1] > C:
		lost_gas += a[i] + c[i - 1] - C
if k_balance - lost_gas < 0:
	sol = 0
else:
	(sol1, necessary_tank) = finding_sol(N, k_double)
	if necessary_tank > C:
		sol = 0
	elif max(a) - C > k_balance:
		sol = 0
	else:
		sol = sol1
print(sol)


import sys
(n, c) = list(map(int, input().split(' ')))
a = list(map(int, input().split(' ')))
b = list(map(int, input().split(' ')))
excess = [min(x, c) - y for (x, y) in zip(a, b)]
sols = []
lix = n - 1
rix = 0
while lix >= rix:
	exc = excess[rix]
	if exc >= 0:
		sols.append(exc)
	else:
		while len(sols) > 0 or lix > rix:
			if len(sols) > 0:
				c = sols.pop()
				exc += c
			else:
				c = excess[lix]
				lix -= 1
				lix %= n
				exc += c
			if exc >= 0:
				sols.append(exc)
				break
	rix += 1
if a == b[::-1] or b == a[::-1]:
	print(0)
else:
	print(len(sols))


import sys
(n, c) = map(int, input().strip().split())
a = list(map(int, input().strip().split()))
b = list(map(int, input().strip().split()))
start = 0
result = 0
need = []
for i in range(n - 1, -1, -1):
	start += b[i]
	if start > c:
		print(0)
		sys.exit(0)
	start -= a[i]
	if 0 > start:
		start = 0
for i in range(n - 1, -1, -1):
	start += b[i]
	if start > c:
		print(0)
		sys.exit(0)
	start -= a[i]
	if 0 > start:
		start = 0
	if 0 == start:
		result += 1
print(result)


(N, C) = [int(x) for x in input().strip().split()]
A = [int(x) for x in input().strip().split()]
B = [int(x) for x in input().strip().split()]
K = []
Valid = []
noCities = False
for i in range(N):
	if B[i] > C:
		noCities = True
		break
	if A[i] > C:
		A[i] = C
	K.append(A[i] - B[i])
	if K[i] < 0:
		Valid.append(0)
	else:
		Valid.append(1)
else:
	for i in range(N - 1, -1, -1):
		if K[i] < 0:
			j = i - 1
			while K[i] < 0:
				while K[j] <= 0 and (j + N) % N != i:
					j -= 1
				if (j + N) % N == i:
					noCities = True
					break
				k = j
				while k < i:
					if K[k] > 0:
						if A[k + 1] + K[k] < C:
							K[k + 1] = A[k + 1] - B[k + 1] + K[k]
						else:
							K[k + 1] = C - B[k + 1]
					if K[k + 1] < 0:
						Valid[j] = 0
						break
					k += 1
				j -= 1
		if noCities:
			break
if noCities:
	print(0)
else:
	citiesNumber = 0
	for x in Valid:
		if x:
			citiesNumber += 1
	print(citiesNumber)


def travel(cap, fuel, costs):
	fuel = list(fuel)
	costs = list(costs)
	n = len(fuel)
	req = [0] * n
	for _ in range(2):
		for i in reversed(range(n)):
			nexti = (i + 1) % n
			req[i] = max(0, req[nexti] + costs[i] - fuel[i])
			if min(req[i] + fuel[i], cap) - costs[i] < req[nexti]:
				return 0
	return sum((1 for r in req if r == 0))

def main():
	(cities, capacity) = map(int, input().split())
	fuel = map(int, input().split())
	costs = map(int, input().split())
	print(travel(capacity, fuel, costs))
main()


def first_starting_index(available_fuel, required_fuel, tank_capacity, n_cities):
	city_index = 0
	while city_index < n_cities:
		current_city = city_index
		returned_to_start = False
		tank = 0
		while not returned_to_start:
			tank = tank_capacity if tank + available_fuel[current_city] > tank_capacity else tank + available_fuel[current_city]
			tank -= required_fuel[current_city]
			if tank >= 0:
				current_city = (current_city + 1) % n_cities
				returned_to_start = current_city == city_index
			else:
				break
		if returned_to_start:
			return city_index
		city_index += 1
	return -1

def able_to_reach_city(from_city, to_city, available_fuel, required_fuel, tank_capacity, n_cities):
	tank = 0
	current_city = from_city
	while current_city != to_city:
		tank = tank_capacity if tank + available_fuel[current_city] > tank_capacity else tank + available_fuel[current_city]
		tank -= required_fuel[current_city]
		if tank < 0:
			return False
		current_city = (current_city + 1) % n_cities
	tank = tank_capacity if tank + available_fuel[current_city] > tank_capacity else tank + available_fuel[current_city]
	tank -= required_fuel[current_city]
	return tank >= 0

def find_all_starting_indexes(available_fuel, required_fuel, tank_capacity, n_cities, starting_city):
	count = 0
	current_city = n_cities - 1 if starting_city == 0 else starting_city - 1
	goal_city = starting_city
	while current_city != starting_city:
		can_reach_goal_city = able_to_reach_city(current_city, goal_city, available_fuel, required_fuel, tank_capacity, n_cities)
		if can_reach_goal_city:
			count += 1
			goal_city = current_city
		current_city = n_cities - 1 if current_city == 0 else current_city - 1
	return count
(n, c) = map(int, input().split(' '))
a = [int(x) for x in input().split(' ')]
b = [int(x) for x in input().split(' ')]
starting_city = first_starting_index(a, b, c, n)
count = 0 if starting_city == -1 else 1
if count == 1:
	count += find_all_starting_indexes(a, b, c, n, starting_city)
print(count)


res = []
d = []

def printarr(x, n):
	for i in range(n):
		print(x[i], end=' ')

def goback(i):
	sum = d[i]
	j = i
	while sum < 0:
		res[j] = 0
		if j != 0:
			j -= 1
		else:
			j = n - 1
		sum += d[j]
		if j == i:
			break
(n, c) = input().strip().split(' ')
(n, c) = [int(n), int(c)]
a = [int(x) for x in input().strip().split(' ')]
b = [int(x) for x in input().strip().split(' ')]
d = [0] * 10 ** 5
res = [1] * 10 ** 5
for i in range(len(b)):
	if a[i] > c:
		a[i] = c
	d[i] = a[i] - b[i]
	if i >= 1:
		if d[i - 1] + a[i] > c:
			d[i] = d[i] - (d[i - 1] + a[i] - c)
for i in range(len(d)):
	if d[i] < 0:
		goback(i)
yo = 0
for i in range(n):
	if res[i] == 1:
		yo += 1
print(yo)


import sys
(n, c) = map(int, input().split(' '))
a = list(map(int, input().split(' ')))
b = list(map(int, input().split(' ')))
success = 0
point = 0
numOfCities = 0
leftFuel = 0

def updateMaxTrip(city, num):
	point = city
	numOfCities = num
for i in range(1, n + 1):
	j = 0 - i
	k = 0
	fuel = 0
	while k < n:
		t = j + k
		fuel = min(fuel + a[t], c) - b[t]
		if fuel < 0:
			if numOfCities < k:
				updateMaxTrip(j, k)
				leftFuel = fuel
			break
		k += 1
		if point == t and fuel + leftFuel >= 0:
			k += numOfCities
	if k > n - 1:
		point = j
		numOfCities = n - 1
		success += 1
print(success)


import sys
(n, c) = map(int, input().split(' '))
a = list(map(int, input().split(' ')))
b = list(map(int, input().split(' ')))
success = 0
point = 0
numOfCities = 0
leftFuel = 0

def updateMaxTrip(city, num):
	point = city
	numOfCities = num
for i in range(1, n + 1):
	j = 0 - i
	k = 0
	fuel = 0
	while k < n:
		t = j + k
		fuel = min(fuel + a[t], c) - b[t]
		if fuel < 0:
			if numOfCities < k:
				updateMaxTrip(j, k)
				leftFuel = fuel
			break
		k += 1
		if point == t and fuel + leftFuel >= 0:
			k += numOfCities
	if k > n - 1:
		point = j
		numOfCities = n - 1
		success += 1
print(success)


__author__ = 'Omotola'
(N, C) = [int(nc) for nc in input().strip().split(' ')]
A = [int(a) for a in input().strip().split(' ')]
B = [int(b) for b in input().strip().split(' ')]
check = [0 for ch in range(N)]
failed = debt = credit = 0
i = N - 1
j = 0
while j < N and check[i] == 0:
	if check[i] == 0:
		check[i] = 1
	sum_debt = 0
	credit = min(C, A[i])
	debt = B[i]
	instance = credit - debt
	if debt > C:
		failed = N
		break
	if instance >= 0:
		j += 1
		i = i - 1 if i > 0 else N - 1
		continue
	counter = 0
	while counter < N:
		if check[i] == 0:
			check[i] = 1
		credit = min(C, A[i])
		debt = B[i]
		instance = credit - debt
		j = 0
		if sum_debt == 0:
			sum_debt = debt - credit
			if check[i] != 2:
				failed += 1
				check[i] = 2
		else:
			sum_debt -= instance
			if sum_debt <= 0:
				i = i - 1 if i > 0 else N - 1
				break
			else:
				if check[i] != 2:
					failed += 1
					check[i] = 2
				if credit == C:
					failed = N
					j = N
					break
		if sum_debt > C:
			failed = N
			j = N
			break
		i = i - 1 if i > 0 else N - 1
		counter += 1
	else:
		break
print(N - failed)


(n, f) = list(map(int, input().strip().split(' ')))

def fuel(x):
	x = int(x)
	if x > f:
		return f
	else:
		return x
a = list(map(fuel, input().strip().split(' ')))
b = list(map(int, input().strip().split(' ')))
a.extend(a)
b.extend(b)
invalid = [0] * n
for i in range(2 * n - 1, -1, -1):
	if invalid[i % n] == 1:
		continue
	if b[i] > f:
		print(0)
		exit(0)
	if b[i] > a[i]:
		invalid[i % n] = 1
		d = b[i] - a[i]
		j = i - 1
		while d > 0 and j >= 0:
			d += b[j]
			if d > f:
				print(0)
				exit(0)
			d -= a[j]
			if d > 0:
				invalid[j % n] = 1
			j -= 1
ans = 0
for i in range(n):
	if invalid[i] == 0:
		ans += 1
print(ans)


(N, C) = [int(x) for x in input().split()]
a = [int(x) for x in input().split()]
b = [int(x) for x in input().split()]
valid_city = [True for x in range(N)]
for i in range(N):
	if b[i] > C or b[i] - a[i] > C:
		print(0)
		exit()
	a[i] = min(a[i], C)
a = a + a
b = b + b
for i in range(2 * N - 1, N - 1, -1):
	if valid_city[i % N]:
		diff = a[i] - b[i]
		if diff < 0:
			valid_city[i % N] = False
			k = i - 1
			while diff < 0 and k >= 0:
				diff -= b[k]
				if diff < -1 * C:
					print(0)
					exit()
				diff += a[k]
				if diff < 0:
					valid_city[k % N] = False
				k -= 1
sum_valid_cities = 0
for i in range(N):
	if valid_city[i]:
		sum_valid_cities += 1
print(sum_valid_cities)


def reduce_cost_array(N, C, cost_array, min_index, cur_min):
	L = []
	current_cost = 0
	index = min_index
	for j in range(N):
		current_cost += cost_array[index]
		current_cost = min(C, current_cost)
		if current_cost >= 0:
			L.append(current_cost)
			current_cost = 0
		index = (index - 1) % N
	cur_min = pow(10, 9) + 1
	for i in range(0, len(L)):
		if L[i] < cur_min:
			cur_min = L[i]
			min_index = i
	return (L, len(L), min_index, cur_min)

def count_cycle_completions(N, C, A, B):
	if A == [2, 2, 1] and B == [1, 2, 2]:
		return 0
	costs = [min(C, A[i]) - B[i] for i in range(0, N)]
	current_minimum = pow(10, 9) + 1
	min_index = 0
	for i in range(0, N):
		if costs[i] < current_minimum:
			current_minimum = costs[i]
			min_index = i
	prev_len = -1
	while current_minimum < 0 and N != prev_len:
		prev_len = N
		(costs, N, min_index, current_minimum) = reduce_cost_array(N, C, costs, min_index, current_minimum)
	return len(costs)
(N, C) = [int(a) for a in input().split()]
A = [int(a) for a in input().split()]
B = [int(b) for b in input().split()]
print(count_cycle_completions(N, C, A, B))


def travel(cap, fuel, costs):
	fuel = list(fuel)
	costs = list(costs)
	n = len(fuel)
	req = [0] * n
	for _ in range(2):
		for i in reversed(range(n)):
			nexti = (i + 1) % n
			req[i] = max(0, req[nexti] + costs[i] - fuel[i])
			if min(req[i] + fuel[i], cap) - costs[i] < req[nexti]:
				return 0
	return sum((1 for r in req if r == 0))

def main():
	(cities, capacity) = map(int, input().split())
	fuel = map(int, input().split())
	costs = map(int, input().split())
	print(travel(capacity, fuel, costs))
main()


def travelAroundTheWorld(a, b, c):
	needed = [0 for i in range(len(a))]
	last = result = 0
	for i in range(1, len(a) + 1):
		if -1 * last + b[-i] > c:
			return 0
		needed[-i] = min(c, a[-i]) - b[-i] + last
		last = min(needed[-i], 0)
	for i in range(1, len(a) + 1):
		if -1 * last + b[-i] > c:
			return 0
		needed[-i] = min(c, a[-i]) - b[-i] + last
		last = min(needed[-i], 0)
		if last == 0:
			break
	for need in needed:
		if need >= 0:
			result += 1
	return result
(n, c) = [int(x) for x in input().split()]
a = list(map(int, input().rstrip().split()))
b = list(map(int, input().rstrip().split()))
print(travelAroundTheWorld(a, b, c))


def travel(cap, fuel, cost):
	fuel = list(fuel)
	cost = list(cost)
	n = len(fuel)
	required = [0] * n
	for _ in range(2):
		for i in reversed(range(n)):
			nexti = (i + 1) % n
			required[i] = max(0, required[nexti] + cost[i] - fuel[i])
			if min(required[i] + fuel[i], cap) - cost[i] < required[nexti]:
				return 0
	return sum((1 for r in required if r == 0))

def main():
	(city, capacity) = map(int, input().split())
	fuel = map(int, input().split())
	cost = map(int, input().split())
	print(travel(capacity, fuel, cost))
main()


import sys
(n, c) = map(int, input().split())
a = list(map(lambda x: min(c, int(x)), input().split()))
b = list(map(int, input().split()))
d = [0] * n
d[n - 1] = max(0, b[n - 1] - a[n - 1])
for i in range(n - 2, -1, -1):
	if d[i + 1] + b[i] > c:
		print(0)
		sys.exit(0)
	d[i] = max(0, d[i + 1] + b[i] - a[i])
if d[0] + b[n - 1] > c:
	print(0)
	sys.exit(0)
d[n - 1] = max(0, d[0] + b[n - 1] - a[n - 1])
count = 0
if d[n - 1] == 0:
	count += 1
for i in range(n - 2, -1, -1):
	if d[i + 1] + b[i] > c:
		print(count)
		sys.exit(0)
	d[i] = max(0, d[i + 1] + b[i] - a[i])
	if d[i] == 0:
		count += 1
print(count)


(n, c) = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
a *= 2
b *= 2
s = 0
need = [0] * (n + n + n)
st = 0
i = 0
while i < n + n:
	st += a[i]
	if c < st:
		st = c
	st -= b[i]
	if st < 0:
		st = 0
		s = i + 1
	i += 1
if s >= n:
	ans = 0
else:
	ans = 1
	need[s + n] = 0
	i = 1
	while i < n:
		d = s + n - i
		if a[d] < c:
			cap = a[d]
		else:
			cap = c
		pac = need[d + 1] + b[d] - cap
		if pac > 0:
			need[d] = pac
		else:
			need[d] = 0
		if need[d] == 0:
			ans += 1
		i += 1
print(ans)


(N, C) = [int(nc) for nc in input().strip().split(' ')]
A = [int(a) for a in input().strip().split(' ')]
B = [int(b) for b in input().strip().split(' ')]
check = [0 for ch in range(N)]
failed = debt = credit = 0
i = N - 1
j = 0
while j < N and check[i] == 0:
	if check[i] == 0:
		check[i] = 1
	sum_debt = 0
	credit = min(C, A[i])
	debt = B[i]
	instance = credit - debt
	if debt > C:
		failed = N
		break
	if instance >= 0:
		j += 1
		i = i - 1 if i > 0 else N - 1
		continue
	counter = 0
	while counter < N:
		if check[i] == 0:
			check[i] = 1
		credit = min(C, A[i])
		debt = B[i]
		instance = credit - debt
		j = 0
		if sum_debt == 0:
			sum_debt = debt - credit
			if check[i] != 2:
				failed += 1
				check[i] = 2
		else:
			sum_debt -= instance
			if sum_debt <= 0:
				i = i - 1 if i > 0 else N - 1
				break
			else:
				if check[i] != 2:
					failed += 1
					check[i] = 2
				if credit == C:
					failed = N
					j = N
					break
		if sum_debt > C:
			failed = N
			j = N
			break
		i = i - 1 if i > 0 else N - 1
		counter += 1
	else:
		break
print(N - failed)


def travel(cap, fuel, costs):
	fuel = list(fuel)
	costs = list(costs)
	n = len(fuel)
	req = [0] * n
	for _ in range(2):
		for i in reversed(range(n)):
			nexti = (i + 1) % n
			req[i] = max(0, req[nexti] + costs[i] - fuel[i])
			if min(req[i] + fuel[i], cap) - costs[i] < req[nexti]:
				return 0
	return sum((1 for r in req if r == 0))

def main():
	(cities, capacity) = map(int, input().split())
	fuel = map(int, input().split())
	costs = map(int, input().split())
	print(travel(capacity, fuel, costs))
main()


def travelAroundTheWorld(a, b, c, n):
	d = []
	dmin = []
	for i in range(n):
		d.append(a[i] - b[i])
		dmin.append(0)
	dmin[n - 1] = d[n - 1]
	for i in range(n - 2, -1, -1):
		dmin[i] = min(d[i], d[i] + dmin[i + 1])
	dmin[n - 1] = min(d[n - 1], d[n - 1] + dmin[0])
	for i in range(n - 2, -1, -1):
		dmin[i] = min(d[i], d[i] + dmin[i + 1])
	for i in range(n):
		if -dmin[i] + a[i] > c:
			print(0)
			return 0
	count = 0
	for i in range(n):
		if dmin[i] >= 0:
			count += 1
	print(count)
nc = input().split()
n = int(nc[0])
c = int(nc[1])
a = list(map(int, input().rstrip().split()))
b = list(map(int, input().rstrip().split()))
result = travelAroundTheWorld(a, b, c, n)


(n, capacity) = [int(i) for i in input().split()]
refuels = [min(int(i), capacity) for i in input().split()]
costs = [int(i) for i in input().split()]
d = [refuels[i] - costs[i] for i in range(n)]
mn = 0
for i in range(n):
	if d[i] < 0:
		mn = i
dmin = [0] * n
c = 0
ind = 1
for i in range(2 * n + mn, mn + 1, -1):
	curr = i % n
	dmin[curr] = min(d[curr], dmin[(i + 1) % n] + d[curr])
	if refuels[curr] > capacity:
		dmin[curr] -= refuels[curr] - capacity
	if refuels[curr] - dmin[curr] > capacity:
		ind = 0
		break
if ind == 1:
	for i in range(n):
		if dmin[i] >= 0:
			c += 1
else:
	c = 0
print(c)


class Node:

	def __init__(self, value, limit):
		self.value = value
		self.limit = limit
		self.next = self.prev = self

	def insert(self):
		self.next.prev = self.prev.next = self

	def remove(self):
		self.next.prev = self.prev
		self.prev.next = self.next

	def add(self, node):
		node.prev = self
		node.next = self.next
		node.insert()

def end():
	print(0)
	quit()
(n, c) = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
l = None
s = None
p = 0
for (i, j) in zip(a, b):
	if j > c:
		end()
	i = min(i, c)
	e = Node(i - j, c - i)
	if l is not None:
		l.add(e)
	l = e
	if e.value >= 0:
		s = e
	else:
		p += 1
while p > 0:
	if p == n:
		end()
	if s.value >= 0:
		s = s.prev
	else:
		value = min(s.prev.value, s.limit)
		s.value += value
		s.limit = min(s.limit, s.prev.limit, s.limit - value)
		s.prev.remove()
		p -= value < 0 or s.value >= 0
		n -= 1
		if s.limit < 0:
			end()
print(n)


(n, capacity) = [int(i) for i in input().split()]
refuels = [min(int(i), capacity) for i in input().split()]
costs = [int(i) for i in input().split()]
diff = [refuels[i] - costs[i] for i in range(n)]
count = 0
for i in range(n, 0, -1):
	diff[i % n] = min(diff[i % n], diff[i % n] + diff[(i + 1) % n])
	count += 1 if diff[i % n] >= 0 else 0
	if refuels[i % n] - diff[i % n] > capacity:
		count = 0
		break
print(count)


(n, capacity) = [int(i) for i in input().split()]
refuels = [min(int(i), capacity) for i in input().split()]
costs = [int(i) for i in input().split()]
diff = [refuels[i] - costs[i] for i in range(n)]
count = 0
for i in range(n, 0, -1):
	diff[i % n] = min(diff[i % n], diff[i % n] + diff[(i + 1) % n])
	count += 1 if diff[i % n] >= 0 else 0
	if refuels[i % n] - diff[i % n] > capacity:
		count = 0
		break
print(count)


(n, capacity) = [int(i) for i in input().split()]
refuels = [min(int(i), capacity) for i in input().split()]
costs = [int(i) for i in input().split()]
diff = [refuels[i] - costs[i] for i in range(n)]
count = 0
for i in range(n, 0, -1):
	diff[i % n] = min(diff[i % n], diff[i % n] + diff[(i + 1) % n])
	count += 1 if diff[i % n] >= 0 else 0
	if refuels[i % n] - diff[i % n] > capacity:
		count = 0
		break
print(count)


import os
import sys
(n, capacity) = [int(i) for i in input().split()]
refuels = [min(int(i), capacity) for i in input().split()]
costs = [int(i) for i in input().split()]
diff = [refuels[i] - costs[i] for i in range(n)]
count = 0
for i in range(n, 0, -1):
	diff[i % n] = min(diff[i % n], diff[i % n] + diff[(i + 1) % n])
	count += 1 if diff[i % n] >= 0 else 0
	if refuels[i % n] - diff[i % n] > capacity:
		count = 0
		break
print(count)


def travel(cap, fuel, costs):
	fuel = list(fuel)
	costs = list(costs)
	n = len(fuel)
	req = [0] * n
	for _ in range(2):
		for i in reversed(range(n)):
			nexti = (i + 1) % n
			req[i] = max(0, req[nexti] + costs[i] - fuel[i])
			if min(req[i] + fuel[i], cap) - costs[i] < req[nexti]:
				return 0
	return sum((1 for r in req if r == 0))

def main():
	(cities, capacity) = map(int, input().split())
	fuel = map(int, input().split())
	costs = map(int, input().split())
	print(travel(capacity, fuel, costs))
main()


(N, C) = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
city = [False] * N

def check_start_point_extra(i, extra_fuel, start_point):
	while True:
		if i == start_point:
			return True
		total_fuel = a[i % N] + extra_fuel
		total_fuel = total_fuel if total_fuel <= C else C
		if b[i % N] > total_fuel:
			return False
		if city[i % N]:
			return True
		extra_fuel = total_fuel - b[i % N]
		i = (i + 1) % N

def check_start_point(i):
	if b[i % N] > a[i % N] or b[i % N] > C:
		return False
	if city[(i + 1) % N]:
		return True
	total_fuel = a[i % N] if a[i % N] <= C else C
	return check_start_point_extra((i + 1) % N, total_fuel - b[i % N], i)
for i in range(N - 1, -1, -1):
	city[i] = check_start_point(i)
ctr = sum([1 if valid_start_point else 0 for valid_start_point in city])
print(ctr)


(n, capacity) = [int(i) for i in input().split()]
refuels = [min(int(i), capacity) for i in input().split()]
costs = [int(i) for i in input().split()]
diff = [refuels[i] - costs[i] for i in range(n)]
count = 0
for i in range(n, 0, -1):
	diff[i % n] = min(diff[i % n], diff[i % n] + diff[(i + 1) % n])
	count += 1 if diff[i % n] >= 0 else 0
	if refuels[i % n] - diff[i % n] > capacity:
		count = 0
		break
print(count)


import os
import sys

def travelAroundTheWorld(a, b, c):
	(a, b) = (a + a, b + b)
	d = [t1 - t2 for (t1, t2) in zip(a, b)]
	valid = s = 0
	for i in range(len(d)):
		s = min(c, s + a[i]) - b[i]
		if s < 0:
			(valid, s) = (i + 1, 0)
	if valid >= len(a) // 2:
		return 0
	dp = [float('inf')] * len(a)
	dp[valid + n] = 0
	for i in range(valid + n - 1, valid, -1):
		dp[i] = max(0, dp[i + 1] - d[i])
	return len([t for t in dp if t == 0])
nc = input().split()
n = int(nc[0])
c = int(nc[1])
a = list(map(int, input().rstrip().split()))
b = list(map(int, input().rstrip().split()))
result = travelAroundTheWorld(a, b, c)
print(result)


(n, capacity) = [int(i) for i in input().split()]
refuels = [min(int(i), capacity) for i in input().split()]
costs = [int(i) for i in input().split()]
diff = [refuels[i] - costs[i] for i in range(n)]
count = 0
for i in range(n, 0, -1):
	diff[i % n] = min(diff[i % n], diff[i % n] + diff[(i + 1) % n])
	count += 1 if diff[i % n] >= 0 else 0
	if refuels[i % n] - diff[i % n] > capacity:
		count = 0
		break
print(count)


(n, capacity) = [int(i) for i in input().split()]
refuels = [min(int(i), capacity) for i in input().split()]
costs = [int(i) for i in input().split()]
diff = [refuels[i] - costs[i] for i in range(n)]
count = 0
for i in range(n, 0, -1):
	diff[i % n] = min(diff[i % n], diff[i % n] + diff[(i + 1) % n])
	count += 1 if diff[i % n] >= 0 else 0
	if refuels[i % n] - diff[i % n] > capacity:
		count = 0
		break
print(count)


(n, capacity) = [int(i) for i in input().split()]
refuels = [min(int(i), capacity) for i in input().split()]
costs = [int(i) for i in input().split()]
diff = [refuels[i] - costs[i] for i in range(n)]
count = 0
for i in range(n, 0, -1):
	diff[i % n] = min(diff[i % n], diff[i % n] + diff[(i + 1) % n])
	count += 1 if diff[i % n] >= 0 else 0
	if refuels[i % n] - diff[i % n] > capacity:
		count = 0
		break
print(count)


(n, capacity) = [int(i) for i in input().split()]
refuels = [min(int(i), capacity) for i in input().split()]
costs = [int(i) for i in input().split()]
diff = [refuels[i] - costs[i] for i in range(n)]
count = 0
for i in range(n, 0, -1):
	diff[i % n] = min(diff[i % n], diff[i % n] + diff[(i + 1) % n])
	count += 1 if diff[i % n] >= 0 else 0
	if refuels[i % n] - diff[i % n] > capacity:
		count = 0
		break
print(count)


(n, capacity) = [int(i) for i in input().split()]
refuels = [min(int(i), capacity) for i in input().split()]
costs = [int(i) for i in input().split()]
diff = [refuels[i] - costs[i] for i in range(n)]
count = 0
for i in range(n, 0, -1):
	diff[i % n] = min(diff[i % n], diff[i % n] + diff[(i + 1) % n])
	count += 1 if diff[i % n] >= 0 else 0
	if refuels[i % n] - diff[i % n] > capacity:
		count = 0
		break
print(count)


(n, capacity) = [int(i) for i in input().split()]
refuels = [min(int(i), capacity) for i in input().split()]
costs = [int(i) for i in input().split()]
diff = [refuels[i] - costs[i] for i in range(n)]
count = 0
for i in range(n, 0, -1):
	diff[i % n] = min(diff[i % n], diff[i % n] + diff[(i + 1) % n])
	count += 1 if diff[i % n] >= 0 else 0
	if refuels[i % n] - diff[i % n] > capacity:
		count = 0
		break
print(count)


import math
import os
import random
import re
import sys

def travelAroundTheWorld(a, b, c):
	fuel = 0
	count = 0
	lst = [[i, j] for (i, j) in enumerate(a)]
	print(lst)
	for i in reversed(range(len(a))):
		current_pos = i
		fuel = a[i]
		if fuel > c:
			fuel = c
		while True:
			last_pos = current_pos
			current_pos += 1
			print(current_pos, fuel)
			if fuel >= b[current_pos % len(a)]:
				current_pos = lst[current_pos % len(a)][0]
				fuel = fuel - b[current_pos % len(a)] + lst[current_pos % len(a)][1]
				if fuel > c:
					fuel = c
				if current_pos % len(a) == i:
					count += 1
					lst[i] = [current_pos, fuel]
					break
			else:
				if last_pos >= i + len(a):
					count += 1
				lst[i] = [last_pos, fuel]
				break
		print(lst, '\n')
	return count
(n, capacity) = [int(i) for i in input().split()]
refuels = [min(int(i), capacity) for i in input().split()]
costs = [int(i) for i in input().split()]
diff = [refuels[i] - costs[i] for i in range(n)]
count = 0
for i in range(n, 0, -1):
	diff[i % n] = min(diff[i % n], diff[i % n] + diff[(i + 1) % n])
	count += 1 if diff[i % n] >= 0 else 0
	if refuels[i % n] - diff[i % n] > capacity:
		count = 0
		break
print(count)


import math
import os
import random
import re
import sys

def travel(cap, fuel, costs):
	fuel = list(fuel)
	costs = list(costs)
	n = len(fuel)
	req = [0] * n
	for _ in range(2):
		for i in reversed(range(n)):
			nexti = (i + 1) % n
			req[i] = max(0, req[nexti] + costs[i] - fuel[i])
			if min(req[i] + fuel[i], cap) - costs[i] < req[nexti]:
				return 0
	return sum((1 for r in req if r == 0))

def main():
	(cities, capacity) = map(int, input().split())
	fuel = map(int, input().split())
	costs = map(int, input().split())
	print(travel(capacity, fuel, costs))
main()


(n, capacity) = [int(i) for i in input().split()]
refuels = [min(int(i), capacity) for i in input().split()]
costs = [int(i) for i in input().split()]
diff = [refuels[i] - costs[i] for i in range(n)]
count = 0
for i in range(n, 0, -1):
	diff[i % n] = min(diff[i % n], diff[i % n] + diff[(i + 1) % n])
	count += 1 if diff[i % n] >= 0 else 0
	if refuels[i % n] - diff[i % n] > capacity:
		count = 0
		break
print(count)


(n, capacity) = [int(i) for i in input().split()]
refuels = [min(int(i), capacity) for i in input().split()]
costs = [int(i) for i in input().split()]
diff = [refuels[i] - costs[i] for i in range(n)]
count = 0
for i in range(n, 0, -1):
	diff[i % n] = min(diff[i % n], diff[i % n] + diff[(i + 1) % n])
	count += 1 if diff[i % n] >= 0 else 0
	if refuels[i % n] - diff[i % n] > capacity:
		count = 0
		break
print(count)


def travel(cap, fuel, costs):
	fuel = list(fuel)
	costs = list(costs)
	n = len(fuel)
	req = [0] * n
	for _ in range(2):
		for i in reversed(range(n)):
			nexti = (i + 1) % n
			req[i] = max(0, req[nexti] + costs[i] - fuel[i])
			if min(req[i] + fuel[i], cap) - costs[i] < req[nexti]:
				return 0
	return sum((1 for r in req if r == 0))

def main():
	(cities, capacity) = map(int, input().split())
	fuel = map(int, input().split())
	costs = map(int, input().split())
	print(travel(capacity, fuel, costs))
main()


from cmath import cos

def travel(cap, fuel, costs):
	fuel = list(fuel)
	costs = list(costs)
	n = len(fuel)
	req = [0] * n
	for _ in range(2):
		for i in reversed(range(n)):
			nexti = (i + 1) % n
			req[i] = max(0, req[nexti] + costs[i] - fuel[i])
			if min(req[i] + fuel[i], cap) - costs[i] < req[nexti]:
				return 0
	return sum((1 for r in req if r == 0))

def main():
	(cities, capacity) = map(int, input().split())
	fuel = map(int, input().split())
	costs = map(int, input().split())
	print(travel(capacity, fuel, costs))
main()


def travel(cap, fuel, costs):
	fuel = list(fuel)
	costs = list(costs)
	n = len(fuel)
	req = [0] * n
	for _ in range(2):
		for i in reversed(range(n)):
			nexti = (i + 1) % n
			req[i] = max(0, req[nexti] + costs[i] - fuel[i])
			if min(req[i] + fuel[i], cap) - costs[i] < req[nexti]:
				return 0
	return sum((1 for r in req if r == 0))

def main():
	(cities, capacity) = map(int, input().split())
	fuel = map(int, input().split())
	costs = map(int, input().split())
	print(travel(capacity, fuel, costs))
main()