You are a king and you are at war. If the enemy breaks through your frontline you lose.
Enemy can break the line only if the sum of morale of any $K$ continuous soldiers is strictly less than $M$. So, you being a motivational orator decides to boost their morale by giving a speech. On hearing it morale of a soldier multiplies by $X$ which depends on you and your speech (i.e. $X$ can be any positive value) but atmost only $K$ continuous speakers can hear your speech.
N soldiers are standing on the frontline with $A[i]$ morale. 
Determine the minimum number of speeches you need to give.

-----Input:-----
The first line contains three space seperated integers $N,K,M$.
The next line contains $N$ space integers, ith of which denotes the morale of $ith$ soldier.

-----Output:-----
Output the minimum number of speeches required. In case if it is impossible to achieve, print $-1$.

-----Constraints:-----
$1 \leq N,M \leq 10^5$
$1 \leq k \leq N$
$0 \leq Ai \leq 10^5$ 

-----Sample Input:-----
6 2 5
1 1 1 1 1 1

-----Sample Output:-----
2

-----Explanation:-----
We multiply 2nd ,3rd  and 5th,6th by 5. Resulting array will be 1 5 5 1 5 5.

Source: codechef | Difficulty: UNKNOWN_DIFFICULTY


Solutions:
(n, k, m) = map(int, input().split())
ar = list(map(int, input().split()))
fsum = [ar[0]]
for i in range(1, n):
	fsum.append(fsum[i - 1] + ar[i])
i = k
c = 0
while i <= n:
	if i == k:
		s = fsum[i - 1]
	else:
		s = fsum[i - 1] - fsum[i - k - 1]
	if s == 0:
		c = -1
		break
	if s < m:
		c += 1
		if i < n:
			for j in range(i, i - k - 1, -1):
				if ar[j - 1] > 0:
					j += k - 1
					i = j
					break
		if i < n:
			for j in range(i, i - k - 1, -1):
				if ar[j - 1] > 0:
					j += k - 1
					i = j
					break
	i += 1
i = k
while i <= n:
	if i == k:
		s = fsum[i - 1]
	else:
		s = fsum[i - 1] - fsum[i - k - 1]
	if s == 0:
		c = -1
		break
	i += 1
print(c)


def main():
	(n, k, m) = list(map(int, input().split()))
	arr = list(map(int, input().split()))
	dp = [-1]
	for i in range(n):
		if arr[i] > 0:
			dp.append(i)
		else:
			dp.append(dp[-1])
	dp.pop(0)
	start = 0
	count = 0
	total = 0
	ans = 0
	index = -1
	rem = k
	for i in range(n):
		if index != -1:
			if i - index <= rem:
				arr[i] *= m
			else:
				index = -1
		total += arr[i]
		count += 1
		if count == k:
			count -= 1
			if total < m:
				index = dp[i]
				if index == -1 or i - index + 1 > k:
					print(-1)
					return
				rem = k - (i - index + 1)
				total -= arr[index]
				arr[index] *= m
				total += arr[index]
				ans += 1
				index = i
			total -= arr[start]
			start += 1
	print(ans)
main()


(N, K, M) = list(map(int, input().split()))
A = list(map(int, input().split()))
tt = 0
i = 0
while i < N:
	k1 = -1
	j = 0
	c = 0
	while j < K and i < N:
		if A[i] != 0:
			k1 = i
		c = c + A[i]
		i = i + 1
		j = j + 1
	while c >= M and i < N:
		if A[i] != 0:
			k1 = i
		c = c + A[i] - A[i - K]
		i = i + 1
	if k1 < 0:
		tt = -1
		break
	elif c < M and j == K:
		tt = tt + 1
		i = k1 + K
print(tt)


nkm = list(map(int, input().split(' ')))
n = nkm[0]
k = nkm[1]
m = nkm[2]
li = list(map(int, input().split(' ')))
i = k - 1
j = k - 1
t = 1
c = 0
while i < n:
	if li[i] != 0:
		c += 1
		j = k - 1
		i = i + 2 * k - 1
	else:
		i -= 1
		j -= 1
		if j < 0:
			t = 0
			break
if t == 1:
	print(c)
else:
	print('-1')