Maksim has $n$ objects and $m$ boxes, each box has size exactly $k$. Objects are numbered from $1$ to $n$ in order from left to right, the size of the $i$-th object is $a_i$.

Maksim wants to pack his objects into the boxes and he will pack objects by the following algorithm: he takes one of the empty boxes he has, goes from left to right through the objects, and if the $i$-th object fits in the current box (the remaining size of the box is greater than or equal to $a_i$), he puts it in the box, and the remaining size of the box decreases by $a_i$. Otherwise he takes the new empty box and continues the process above. If he has no empty boxes and there is at least one object not in some box then Maksim cannot pack the chosen set of objects.

Maksim wants to know the maximum number of objects he can pack by the algorithm above. To reach this target, he will throw out the leftmost object from the set until the remaining set of objects can be packed in boxes he has. Your task is to say the maximum number of objects Maksim can pack in boxes he has.

Each time when Maksim tries to pack the objects into the boxes, he will make empty all the boxes he has before do it (and the relative order of the remaining set of objects will not change).


-----Input-----

The first line of the input contains three integers $n$, $m$, $k$ ($1 \le n, m \le 2 \cdot 10^5$, $1 \le k \le 10^9$) — the number of objects, the number of boxes and the size of each box.

The second line of the input contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le k$), where $a_i$ is the size of the $i$-th object.


-----Output-----

Print the maximum number of objects Maksim can pack using the algorithm described in the problem statement.


-----Examples-----
Input
5 2 6
5 2 1 4 2

Output
4

Input
5 1 4
4 2 3 4 1

Output
1

Input
5 3 3
1 2 3 1 1

Output
5



-----Note-----

In the first example Maksim can pack only $4$ objects. Firstly, he tries to pack all the $5$ objects. Distribution of objects will be $[5], [2, 1]$. Maxim cannot pack the next object in the second box and he has no more empty boxes at all. Next he will throw out the first object and the objects distribution will be $[2, 1], [4, 2]$. So the answer is $4$.

In the second example it is obvious that Maksim cannot pack all the objects starting from first, second, third and fourth (in all these cases the distribution of objects is $[4]$), but he can pack the last object ($[1]$).

In the third example Maksim can pack all the objects he has. The distribution will be $[1, 2], [3], [1, 1]$.

Difficulty: introductory

Starter code:

Solutions:
n, m, k = [int(_) for _ in input().split()]
a = [int(_) for _ in input().split()]

b = k
count = 0
for obj in a[::-1]:
    if obj > k:
        break
    if obj > b:
        if m > 1:
            m -= 1
            b = k - obj
            count += 1
        else:
            break
    else:
        b -= obj
        count += 1

print(count)



n,m,k = [int(x) for x in input().split()]
a = [int(x) for x in input().split()]
a = a[::-1]
boxes = 0
ans = 0
loc = 0
for i in range(n):
    loc += a[i]
    if loc > k:
        boxes += 1
        loc = a[i]
    if boxes == m:
        break
    ans += 1
    # print(ans,boxes,loc)
print(ans)



n,m,k = list(map(int, input().split()))
list_a = list(map(int, input().split()))
list_a.reverse()
count_b = 0
sum_now = 0
ans = 0
i = 0
while i < n:
	if count_b >= m:
		ans = i - 1
		break
	sum_now += list_a[i]
	if sum_now > k:
		sum_now = 0
		count_b +=1
	else:
		i += 1
else:
	ans = n-1
print(ans+1)


n, m, k = map(int, input().split())
a = list(map(int, input().split()))

# left = -1
# right = n-1

# while right - left > 1:
# 	mid = (right+left)//2
	
# 	count = 0
# 	curr = 0
# 	for i in range(mid, n):
# 		if curr + a[i] <= k:
# 			curr += a[i]
# 		else:
# 			count += 1
# 			curr = a[i]
# 	count += 1
	
# 	if count > m:
# 		left = mid
# 	else:
# 		right = mid

# print(n-right)

count = 0
curr = 0
i = n
while count < m and i >= 0:
	i -= 1
	if curr + a[i] <= k:
		curr += a[i]
	else:
		count += 1
		curr = a[i]

print(n-i-1)

def fit(a, m, k, res):
	k1 = k
	for ai in a[-res:]:
		if ai <= k1:
			k1 -= ai
		else:
			k1 = k-ai
			if m == 1:
				return False
			else:
				m -= 1
	return True
	# С нек. момента моё воспоминание об алгоритме, описанном в условии, изменилось (исправлено)


def bisect(n, m, k, a):
	left, right = 0, n+1
	while left + 1 < right:
		middle = (left + right) // 2
		if fit(a, m, k, middle):
			left = middle
		else:
			right = middle
	return left


def main():
	n, m, k = list(map(int, input().split()))
	a = tuple(map(int, input().split()))
	print(bisect(n, m, k, a))
main()


n,m,k = [int(s) for s in input().split()]
a = [int(s) for s in input().split()]
ans = 0
boxi = 0
rem_size = k
for i in range(n-1, -1, -1):
    if a[i] > k:
        break
    if a[i] > rem_size:
        if boxi >= m-1:
            break
        else:
            boxi += 1
            rem_size = k
    rem_size -= a[i]
    ans += 1

print(ans)

from sys import stdin
n,m,k=list(map(int,stdin.readline().strip().split()))
s=tuple(map(int,stdin.readline().strip().split()))
x=0
y=0
ans=0
for i in range(n-1,-1,-1):
    if x==m:
        break
    if y+s[i]>k:
        if s[i]>k:
            break
        x+=1
        if x==m:
            break
        ans+=1
        y=s[i]
    else:
        y+=s[i]
        ans+=1
    
print(ans)


n,m,k=[int(x)for x in input().split()]
ns=[int(x)for x in input().split()]
ns.reverse()
rem=k
num=0
ans=[]
for i in range(n):
    if rem>=ns[i]:
        rem-=ns[i]
        num+=1
    else:
        ans.append(num)
        rem=k-ns[i]
        num=1
if num>0:
    ans.append(num)

# print(ans)

if len(ans)<=m:
    print(sum(ans))
else:
    a=[sum(ans[:m])]
    # for i in range(m,len(ans)):
    #     a.append(a[-1]+ans[i]-ans[i-m])
    print(max(a))

def main():
    nobj, nbox, boxsize = list(map(int, input().split()))
    obj = list(map(int, input().split()))
    box = boxsize
    curr = 0
    ans = 0
    i = nobj - 1
    while i >= 0:
        o = obj[i]
        #print('box: ' + str(box) + ' i = ' + str(i) + ', o = ' + str(o))
        if o <= box:
            box -= o
            ans += 1
        else:
            curr += 1
            box = boxsize
            if curr >= nbox:
                break
            continue
        i -= 1
    print(ans)

def __starting_point():
    main()

__starting_point()

# coding=utf-8

n, m, k = map(int, input().split())

a = [int(i) for i in input().split()]

cur = 0
ans = 0
box = k
i = n - 1

while i >= 0:
    obj = a[i]
    if obj <= box:
        box -= obj
        ans += 1
    else:
        cur += 1
        box = k
        if cur >= m:
            break
        continue
    i -= 1

print(ans)

# coding=utf-8

n, m, k = map(int, input().split())

a = [int(i) for i in input().split()]

cur = 0
ans = 0
box = k
i = n - 1

while i >= 0:
    obj = a[i]
    if obj <= box:
        box -= obj
        ans += 1
    else:
        cur += 1
        box = k
        if cur >= m:
            break
        continue
    i -= 1

print(ans)

n, m, k = list(map(int, input().split()))
a = list(map(int, input().split()))

a = a[::-1]

res = 0
weight = 0

for i in range(n):
    weight += a[i]
    if weight > k:
        weight = a[i]
        m -= 1
    if m <= 0:
        break
    res += 1

print(res)


import sys

def minp():
	return sys.stdin.readline().strip()

n,mm,k = map(int,minp().split())
a = list(map(int,minp().split()))
def tt(x):
	m = mm-1
	c = 0
	for j in range(x,n):
		i = a[j]
		if c + i > k:
			if m == 0 or i > k:
				return False
			c = i
			m -= 1
			#if i == k:
			#	if m == 0:
			#		return False
			#	m -= 1
			#	c = 0
		else:
			c += i
	return True
l = 0
r = n
while l < r:
	c = (l+r)//2
	if tt(c):
		r = c
	else:
		l = c+1
print(n-r)

import sys

def minp():
	return sys.stdin.readline().strip()

n,mm,k = list(map(int,minp().split()))
a = list(map(int,minp().split()))
def tt(x):
	m = mm-1
	c = 0
	res = 0
	for i in reversed(a):
		if c + i > k:
			if m == 0 or i > k:
				return res
			c = i
			m -= 1
			#if i == k:
			#	if m == 0:
			#		return False
			#	m -= 1
			#	c = 0
		else:
			c += i
		res += 1
	return res
print(tt(0))
#l = 0
#r = n
#while l < r:
#	c = (l+r)//2
#	if tt(c):
#		r = c
#	else:
#		l = c+1
#print(n-r)


import sys
input = sys.stdin.readline

def main():
    n, m, k = map(int, input().split())
    a = list(map(int, input().split()))
    if min(a) > k:
        return 0
    a = a[::-1]
    current = 0
    answer = 0
    for i in range(n):
        if current + a[i] <= k:
            current += a[i]
            answer += 1
        else:
            current = 0
            m -= 1
            if m == 0:
                break
            else:
                if current + a[i] < k:
                    current += a[i]
                    answer += 1
                elif current + a[i] == k:
                    answer += 1
                    m -= 1
                    if m == 0:
                        break
                else:
                    continue
    return answer
def __starting_point():
    print(main())
__starting_point()

n,m,k=list(map(int,input().split()))
arr=list(map(int,input().split()))
arr1=[0]*n
i=n-1
prevval=0
ans=0
while(i>=0 and m>0):
	if(prevval+arr[i]<=k):
		prevval+=arr[i]
	else:
		m-=1
		prevval=arr[i]
	i-=1
	ans+=1
if(m==0):
	ans-=1
print(ans)


n,m,k=list(map(int,input().split()))#object,箱,size,
A=list(map(int,input().split()))#size


A.reverse()
inb=0
box=0
i=0
while box<m and i<n:
    if inb+A[i]<=k:
       inb+=A[i]
       i+=1
    else:
        box+=1
        inb=0
    
print(i)


import sys
import math

n,m,k=map(int,input().split())
jobs=[int(x) for x in input().strip().split()]
steve=jobs[:]
nade=steve[::-1]
suma,con,kik=0,0,0
for i in range(n):
    if(nade[i]>k):
        break
    if(suma+nade[i]<k):
        #print("A")
        suma+=nade[i]
        kik+=1
        if(i<n-1):
            if(suma+nade[i+1]>k):
                suma=0
                con+=1
    elif(suma+nade[i]==k):
        #print("B")
        #print("SPC CASE",suma,nade[i],suma+nade[i])
        con+=1
        kik+=1
        suma=0
    elif(suma+nade[i]>k):
        #print("C")
        con+=1
        suma=0
    #print(suma,kik)
    if(con>=m):
        break
print(kik)

import math
import sys
n,m,k = map(int, sys.stdin.readline().split())
a =[int(x) for x in sys.stdin.readline().split()]
a.reverse()
ans = 0
bag = m - 1
size = k
for x in a:
    if size < x:
        if bag > 0:
            bag -= 1
            size = k - x
        else: break
    else: size -= x
    ans += 1
sys.stdout.write(str(ans))

def bS(alist, item):
    first = 0
    last = len(alist)-1
    found = False
    posi=-1	
    while (first<=last+1) and (not found):
        midpoint = (first + last)//2
        #print(midpoint,alist[midpoint-1] )
        if (alist[midpoint]>=item):#and (alist[midpoint+1] <= item):
            found = True
            posi=midpoint
        else:
            if item < alist[midpoint]:
                last = midpoint-1
            else:
                first = midpoint+1
	
    return posi


n,m,k=list(map(int,input().split()))
a=list(input().split())
maxi=0
cc=0
now=-1
alr=0
alfa=[0]*n
last=0
for ii in range(n):
    i=n-ii-1
    alfa[ii]=int(a[i])+last
    last=alfa[ii]

#print(alfa)
if alfa[-1]>m*k:
    pos=bS(alfa,m*k)
else:
    pos=n-1

#print(pos)
ii=n-pos-1
#b=a[ii+1:].copy()
b=a
b.reverse()
maxi=0
start=0
#for start in range(n):
if (1==1):
    #if n-start<maxi:
    #    break
    alr=0
    cc=0
    for i in b[start:]:
        alr+=int(i)
        cc+=1
        
        if alr>k:
            alr=int(i)
            if alr>k:
                cc-=1
            m-=1
            if m==0:
                cc-=1
                break
    if cc>maxi:
        maxi=cc
        
    
print(maxi)   




   

    


def go():
    n, m, k = [int(i) for i in input().split(' ')]
    a = [int(i) for i in input().split(' ')]
    current_box = k
    m -= 1
    c = 0
    for i in range(n - 1, -1, -1):
        if a[i] <= current_box:
            current_box -= a[i]
            c += 1
        elif a[i] > current_box:
            current_box = k - a[i]
            if m == 0:
                break
            m -= 1
            c += 1
    return c

print(go())


n, m, k = list(map(int, input().split()))
a = list(map(int, input().split()))
a.reverse()
last = 0
for i in range(n):
    if a[i] > last:
        if m == 0:
            print(i)
            return
        else:
            m -= 1
            last = k - a[i]
    else:
        last -= a[i]
print(n)


n,m,k=list(map(int,input().split()))
cnt=0
count=0
sum=0
a=[int(s) for s in input().split()]
for i in range(n-1,-1,-1):
    sum+=a[i]
    if sum>k:
        sum=a[i]
        count+=1
        if count>=m:
            break
    cnt+=1
print(cnt)



n,k,m=list(map(int,input().split()))
l=[int(i) for i in input().split()]
def ispzbl(l,n,m,k,mid):
    z=l[mid:]
    if not z:
        return True 
    s=0
    box=1
    for i in z:
        s+=i 
        if s>m:
            box+=1 
            s=i
    return box<=k
low=0 
high=n-1 
while low<=high:
    mid=(low+high)//2
   # print(mid)
    if ispzbl(l,n,m,k,mid):
        ans=mid 
        high=mid-1 
    else:
        low=mid+1 
#print(ans)
print(n-ans)