Problem p02623 (python)

Fixed submission:
# /usr/bin/python3
# -*- coding: utf-8 -*-
from queue import Queue
from queue import LifoQueue as Stack
from math import sqrt, floor, ceil, log2, log10, pi
from fractions import gcd
from itertools import permutations, combinations
from operator import itemgetter
from functools import cmp_to_key


INF=1001001001
__MOD__=(10**9)+7
yn = 'YNeos'
judge = False
cnt = 0
ans = None


def lcm(a, b):
    return (a*b) // gcd(a,b)

def intinput():
    return int(input())

def mulinputs():
    return map(int,input().split())

def lineinputs(func=intinput):
    datas = []
    while True:
        try:
            datas.append(func())
        except EOFError:
            break
    return datas

class ModInt():
    def __init__(self, x):
        self.__x = (x % __MOD__)
    def __add__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((self.__x + other.__x)%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((self.__x + other.__x)%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")
    def __radd__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((other.__x + self.__x)%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((other.__x + self.__x)%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")

    def __sub__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((self.__x - other.__x)%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((self.__x - other.__x)%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")
    def __rsub__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((other.__x - self.__x)%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((other.__x - self.__x)%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")

    def __mul__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((self.__x * other.__x)%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((self.__x * other.__x)%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")
    def __rmul__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((other.__x * self.__x)%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((other.__x * self.__x)%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")

    def __truediv__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((self.__x * other.__modinv())%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((self.__x * other.__modinv())%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")
    def __rtruediv__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((other.__x * self.__modinv())%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((other.__x * self.__modinv())%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")

    def __pow__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__(pow(self.__x, other.__x, __MOD__)))
        elif type(other) == ModInt:
            return self.__class__(pow(self.__x, other.__x, __MOD__))
        else:
            raise Exception("Not Int or Not ModInt")
    def __rpow__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__(pow(other.__x, self.__x, __MOD__)))
        elif type(other) == ModInt:
            return self.__class__(pow(other.__x, self.__x, __MOD__))
        else:
            raise Exception("Not Int or Not ModInt")

    def __modinv(self, m=__MOD__):
        a = self.__x
        if a == 0:
            raise ZeroDivisionError()
        if gcd(a, m) != 1:
            raise Exception("%sの逆数は求まりません。" % a)
        b, u, v = m, 1, 0
        while b != 0:
            t = a//b;
            a -= t*b
            a, b = b, a
            u -= t * v
            u, v = v, u
        u %= m
        if u < 0:
            u += m
        return u
    def __int__(self):
        return self.__x
    def __str__(self):
        return str(self.__x)



if __name__ == '__main__':
    N, M, K = mulinputs()
    an = list(map(int, input().split()))
    bm = list(map(int, input().split()))

#     # i, j, la, lb, t = 0, 0, len(an), len(bm), 0
#     # l = max(la, lb)
#     # while True:
#     #     if i < la and j < lb:
#     #         a, b = an[i], bm[j]
#     #     elif i < la:
#     #         a, b = an[i], INF
#     #     elif j < lb:
#     #         a, b = INF, bm[j]
#     #     else:
#     #         break
#     #     c = 0
#     #     if a <= b:
#     #         c = a
#     #         i += 1
#     #     else:
#     #         c = b
#     #         j += 1
#     #     if t + c <= K:
#     #         t += c
#     #         cnt += 1
#     #     else:
#     #         break
#     # # t = 0
#     # # while len(an) != 0 or len(bm) != 0:
#     # #     a, b = INF, INF
#     # #     if len(an) > 0:
#     # #         a = an.pop()
#     # #     if len(bm) > 0:
#     # #         b = bm.pop()
#     # #     if t + min(a, b) > K:
#     # #         break
#     # #     if a >= b:
#     # #         t += a
#     # #         cnt += 1
#     # #         bm.append(b)
#     # #     else:
#     # #         t += b
#     # #         cnt += 1
#     # #         an.append(a)
# # 
#     # # 出力
#     # print(cnt)
# 
# 
#     la, lb = len(an), len(bm)
#     def dfs(i, j, t, c):
#         a = INF if i >= la else an[i]
#         b = INF if j >= lb else bm[j]
#         if t + min(a,b) > K:
#             return c
#         return max(dfs(i+1, j, t+a, c+1), dfs(i, j+1, t+b, c+1), c)
# 
#     print(dfs(0,0,0,0))


    # 復習
    # 参考：https://atcoder.jp/contests/abc172/submissions/14775432
    ans, aidx, bidx = 0, 0, 0
    # 何も考えずにaから、bから条件を満たす本を収集する
    while True:
        if aidx == len(an):
            break
        if ans+an[aidx] <= K:
            ans += an[aidx]
            aidx +=1
        else:
            break
    while True:
        if bidx == len(bm):
            break
        if ans + bm[bidx] <= K:
            ans += bm[bidx]
            bidx += 1
        else:
            break
    ansidx = aidx + bidx
    # 上で求めたものから、どれくらいaの本を少なくすればbの本を読めるか、を計算する
    while aidx > 0:
        aidx -=1
        ans -= an[aidx]
        while True:
            if bidx == len(bm):
                break
            if ans + bm[bidx] <= K:
                ans += bm[bidx]
                bidx += 1
            else:
                break
        ansidx = max(ansidx, aidx+bidx)
    print(ansidx)

Buggy submission (verdict: Runtime Error):
# /usr/bin/python3
# -*- coding: utf-8 -*-
from queue import Queue
from queue import LifoQueue as Stack
from math import sqrt, floor, ceil, log2, log10, pi
from fractions import gcd
from itertools import permutations, combinations
from operator import itemgetter
from functools import cmp_to_key


INF=1001001001
__MOD__=(10**9)+7
yn = 'YNeos'
judge = False
cnt = 0
ans = None


def lcm(a, b):
    return (a*b) // gcd(a,b)

def intinput():
    return int(input())

def mulinputs():
    return map(int,input().split())

def lineinputs(func=intinput):
    datas = []
    while True:
        try:
            datas.append(func())
        except EOFError:
            break
    return datas

class ModInt():
    def __init__(self, x):
        self.__x = (x % __MOD__)
    def __add__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((self.__x + other.__x)%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((self.__x + other.__x)%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")
    def __radd__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((other.__x + self.__x)%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((other.__x + self.__x)%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")

    def __sub__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((self.__x - other.__x)%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((self.__x - other.__x)%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")
    def __rsub__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((other.__x - self.__x)%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((other.__x - self.__x)%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")

    def __mul__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((self.__x * other.__x)%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((self.__x * other.__x)%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")
    def __rmul__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((other.__x * self.__x)%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((other.__x * self.__x)%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")

    def __truediv__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((self.__x * other.__modinv())%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((self.__x * other.__modinv())%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")
    def __rtruediv__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((other.__x * self.__modinv())%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((other.__x * self.__modinv())%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")

    def __pow__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__(pow(self.__x, other.__x, __MOD__)))
        elif type(other) == ModInt:
            return self.__class__(pow(self.__x, other.__x, __MOD__))
        else:
            raise Exception("Not Int or Not ModInt")
    def __rpow__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__(pow(other.__x, self.__x, __MOD__)))
        elif type(other) == ModInt:
            return self.__class__(pow(other.__x, self.__x, __MOD__))
        else:
            raise Exception("Not Int or Not ModInt")

    def __modinv(self, m=__MOD__):
        a = self.__x
        if a == 0:
            raise ZeroDivisionError()
        if gcd(a, m) != 1:
            raise Exception("%sの逆数は求まりません。" % a)
        b, u, v = m, 1, 0
        while b != 0:
            t = a//b;
            a -= t*b
            a, b = b, a
            u -= t * v
            u, v = v, u
        u %= m
        if u < 0:
            u += m
        return u
    def __int__(self):
        return self.__x
    def __str__(self):
        return str(self.__x)



if __name__ == '__main__':
    N, M, K = mulinputs()
    an = list(map(int, input().split()))
    bm = list(map(int, input().split()))

#     # i, j, la, lb, t = 0, 0, len(an), len(bm), 0
#     # l = max(la, lb)
#     # while True:
#     #     if i < la and j < lb:
#     #         a, b = an[i], bm[j]
#     #     elif i < la:
#     #         a, b = an[i], INF
#     #     elif j < lb:
#     #         a, b = INF, bm[j]
#     #     else:
#     #         break
#     #     c = 0
#     #     if a <= b:
#     #         c = a
#     #         i += 1
#     #     else:
#     #         c = b
#     #         j += 1
#     #     if t + c <= K:
#     #         t += c
#     #         cnt += 1
#     #     else:
#     #         break
#     # # t = 0
#     # # while len(an) != 0 or len(bm) != 0:
#     # #     a, b = INF, INF
#     # #     if len(an) > 0:
#     # #         a = an.pop()
#     # #     if len(bm) > 0:
#     # #         b = bm.pop()
#     # #     if t + min(a, b) > K:
#     # #         break
#     # #     if a >= b:
#     # #         t += a
#     # #         cnt += 1
#     # #         bm.append(b)
#     # #     else:
#     # #         t += b
#     # #         cnt += 1
#     # #         an.append(a)
# # 
#     # # 出力
#     # print(cnt)
# 
# 
#     la, lb = len(an), len(bm)
#     def dfs(i, j, t, c):
#         a = INF if i >= la else an[i]
#         b = INF if j >= lb else bm[j]
#         if t + min(a,b) > K:
#             return c
#         return max(dfs(i+1, j, t+a, c+1), dfs(i, j+1, t+b, c+1), c)
# 
#     print(dfs(0,0,0,0))


    # 復習
    ans, aidx, bidx = 0, 0, 0
    while True:
        if ainx == len(an):
            break
        if ans+an[aidx] <= K:
            ans += an[aidx]
            aidx +=1
        else:
            break
    while True:
        if bidx = len(bm):
            break
        if ans + bm[bidx] <= K:
            ans += bm[bidx]
            bidx += 1
        else:
            break
    ansidx = aidx + bidx
    while aidx > 0:
        aidx -=1
        ans -= an[aidx]
        while True:
            if bidx == len(bm):
                break
            if ans + bm[bidx] <= K:
                ans += bm[bidx]
                bidx += 1
            else:
                break
        ansidx = max(ansidx, aidx+bidx)
    print(ansidx)

Buggy submission (verdict: Runtime Error):
# /usr/bin/python3
# -*- coding: utf-8 -*-
from queue import Queue
from queue import LifoQueue as Stack
from math import sqrt, floor, ceil, log2, log10, pi
from fractions import gcd
from itertools import permutations, combinations
from operator import itemgetter
from functools import cmp_to_key


INF=1001001001
__MOD__=(10**9)+7
yn = 'YNeos'
judge = False
cnt = 0
ans = None


def lcm(a, b):
    return (a*b) // gcd(a,b)

def intinput():
    return int(input())

def mulinputs():
    return map(int,input().split())

def lineinputs(func=intinput):
    datas = []
    while True:
        try:
            datas.append(func())
        except EOFError:
            break
    return datas

class ModInt():
    def __init__(self, x):
        self.__x = (x % __MOD__)
    def __add__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((self.__x + other.__x)%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((self.__x + other.__x)%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")
    def __radd__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((other.__x + self.__x)%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((other.__x + self.__x)%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")

    def __sub__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((self.__x - other.__x)%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((self.__x - other.__x)%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")
    def __rsub__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((other.__x - self.__x)%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((other.__x - self.__x)%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")

    def __mul__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((self.__x * other.__x)%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((self.__x * other.__x)%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")
    def __rmul__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((other.__x * self.__x)%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((other.__x * self.__x)%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")

    def __truediv__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((self.__x * other.__modinv())%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((self.__x * other.__modinv())%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")
    def __rtruediv__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((other.__x * self.__modinv())%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((other.__x * self.__modinv())%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")

    def __pow__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__(pow(self.__x, other.__x, __MOD__)))
        elif type(other) == ModInt:
            return self.__class__(pow(self.__x, other.__x, __MOD__))
        else:
            raise Exception("Not Int or Not ModInt")
    def __rpow__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__(pow(other.__x, self.__x, __MOD__)))
        elif type(other) == ModInt:
            return self.__class__(pow(other.__x, self.__x, __MOD__))
        else:
            raise Exception("Not Int or Not ModInt")

    def __modinv(self, m=__MOD__):
        a = self.__x
        if a == 0:
            raise ZeroDivisionError()
        if gcd(a, m) != 1:
            raise Exception("%sの逆数は求まりません。" % a)
        b, u, v = m, 1, 0
        while b != 0:
            t = a//b;
            a -= t*b
            a, b = b, a
            u -= t * v
            u, v = v, u
        u %= m
        if u < 0:
            u += m
        return u
    def __int__(self):
        return self.__x
    def __str__(self):
        return str(self.__x)



if __name__ == '__main__':
    N, M, K = mulinputs()
    an = list(map(int, input().split()))
    bm = list(map(int, input().split()))

    # i, j, la, lb, t = 0, 0, len(an), len(bm), 0
    # l = max(la, lb)
    # while True:
    #     if i < la and j < lb:
    #         a, b = an[i], bm[j]
    #     elif i < la:
    #         a, b = an[i], INF
    #     elif j < lb:
    #         a, b = INF, bm[j]
    #     else:
    #         break
    #     c = 0
    #     if a <= b:
    #         c = a
    #         i += 1
    #     else:
    #         c = b
    #         j += 1
    #     if t + c <= K:
    #         t += c
    #         cnt += 1
    #     else:
    #         break
    # # t = 0
    # # while len(an) != 0 or len(bm) != 0:
    # #     a, b = INF, INF
    # #     if len(an) > 0:
    # #         a = an.pop()
    # #     if len(bm) > 0:
    # #         b = bm.pop()
    # #     if t + min(a, b) > K:
    # #         break
    # #     if a >= b:
    # #         t += a
    # #         cnt += 1
    # #         bm.append(b)
    # #     else:
    # #         t += b
    # #         cnt += 1
    # #         an.append(a)
# 
    # # 出力
    # print(cnt)


    la, lb = len(an), len(bm)
    def dfs(i, j, t, c):
        a = INF if i >= la else an[i]
        b = INF if j >= lb else bm[j]
        if t + min(a,b) > K:
            return c
        return max(dfs(i+1, j, t+a, c+1), dfs(i, j+1, t+b, c+1), c)

    print(dfs(0,0,0,0))

Buggy submission (verdict: Runtime Error):
# /usr/bin/python3
# -*- coding: utf-8 -*-
from queue import Queue
from queue import LifoQueue as Stack
from math import sqrt, floor, ceil, log2, log10, pi
from fractions import gcd
from itertools import permutations, combinations
from operator import itemgetter
from functools import cmp_to_key


INF=1001001001
__MOD__=(10**9)+7
yn = 'YNeos'
judge = False
cnt = 0
ans = None


def lcm(a, b):
    return (a*b) // gcd(a,b)

def intinput():
    return int(input())

def mulinputs():
    return map(int,input().split())

def lineinputs(func=intinput):
    datas = []
    while True:
        try:
            datas.append(func())
        except EOFError:
            break
    return datas

class ModInt():
    def __init__(self, x):
        self.__x = (x % __MOD__)
    def __add__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((self.__x + other.__x)%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((self.__x + other.__x)%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")
    def __radd__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((other.__x + self.__x)%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((other.__x + self.__x)%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")

    def __sub__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((self.__x - other.__x)%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((self.__x - other.__x)%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")
    def __rsub__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((other.__x - self.__x)%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((other.__x - self.__x)%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")

    def __mul__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((self.__x * other.__x)%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((self.__x * other.__x)%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")
    def __rmul__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((other.__x * self.__x)%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((other.__x * self.__x)%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")

    def __truediv__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((self.__x * other.__modinv())%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((self.__x * other.__modinv())%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")
    def __rtruediv__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((other.__x * self.__modinv())%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((other.__x * self.__modinv())%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")

    def __pow__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__(pow(self.__x, other.__x, __MOD__)))
        elif type(other) == ModInt:
            return self.__class__(pow(self.__x, other.__x, __MOD__))
        else:
            raise Exception("Not Int or Not ModInt")
    def __rpow__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__(pow(other.__x, self.__x, __MOD__)))
        elif type(other) == ModInt:
            return self.__class__(pow(other.__x, self.__x, __MOD__))
        else:
            raise Exception("Not Int or Not ModInt")

    def __modinv(self, m=__MOD__):
        a = self.__x
        if a == 0:
            raise ZeroDivisionError()
        if gcd(a, m) != 1:
            raise Exception("%sの逆数は求まりません。" % a)
        b, u, v = m, 1, 0
        while b != 0:
            t = a//b;
            a -= t*b
            a, b = b, a
            u -= t * v
            u, v = v, u
        u %= m
        if u < 0:
            u += m
        return u
    def __int__(self):
        return self.__x
    def __str__(self):
        return str(self.__x)



if __name__ == '__main__':
    N, M, K = mulinputs()
    an = list(map(int, input().split()))
    bm = list(map(int, input().split()))

    # i, j, la, lb, t = 0, 0, len(an), len(bm), 0
    # l = max(la, lb)
    # while True:
    #     if i < la and j < lb:
    #         a, b = an[i], bm[j]
    #     elif i < la:
    #         a, b = an[i], INF
    #     elif j < lb:
    #         a, b = INF, bm[j]
    #     else:
    #         break
    #     c = 0
    #     if a <= b:
    #         c = a
    #         i += 1
    #     else:
    #         c = b
    #         j += 1
    #     if t + c <= K:
    #         t += c
    #         cnt += 1
    #     else:
    #         break
    # # t = 0
    # # while len(an) != 0 or len(bm) != 0:
    # #     a, b = INF, INF
    # #     if len(an) > 0:
    # #         a = an.pop()
    # #     if len(bm) > 0:
    # #         b = bm.pop()
    # #     if t + min(a, b) > K:
    # #         break
    # #     if a >= b:
    # #         t += a
    # #         cnt += 1
    # #         bm.append(b)
    # #     else:
    # #         t += b
    # #         cnt += 1
    # #         an.append(a)
# 
    # # 出力
    # print(cnt)


    la, lb = len(an), len(bm)
    def dfs(i, j, t, c):
        if i >= la and j >= lb:
            return c
        elif i >= la and j < lb:
            a, b = INF, bm[j]
        elif i < la and j >= lb:
            a, b = an[i], INF
        else:
            a, b = an[i], bm[j]
        if t + min(a,b) > K:
            return c
        if a < b:
            return dfs(i+1, j, t+a, c+1)
        elif a > b:
            return dfs(i, j+1, t+b, c+1)
        else:
            return max(dfs(i+1, j, t+a, c+1), dfs(i, j+1, t+a, c+1))

    print(dfs(0,0,0,0))