Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

n, m = map(int, input().split())
hole_ids = [int(input()) - 1 for _ in range(m)]
X = 1000000007


def solve(n, hole_ids):
    # nums = []
    nums = [0] * n
    for i in range(n):
        if i in hole_ids:
            # nums.append(0)
            nums[i] = 0
            continue

        if i == 0:
            # nums.append(1)
            nums[i] = 1
        elif i == 1:
            # 1つ前から1段上がるから2つ前から2個飛ばし
            # nums.append(nums[-1] + 1)
            nums[i] = nums[i-1] + 1
        else:
            # nums.append((nums[-1] % X + nums[-2] % X) % X)
            nums[i] = (nums[i-1] + nums[i-2]) % X
    return nums[-1]


print(solve(n, hole_ids))


### FIXED CODE ###

n, m = map(int, input().split())
hole_ids = {int(input()) - 1: 0 for _ in range(m)}
X = 1000000007


def solve(n, hole_ids):
    # nums = []
    nums = [0] * n
    for i in range(n):
        if i in hole_ids:
            # nums.append(0)
            nums[i] = 0
            continue

        if i == 0:
            # nums.append(1)
            nums[i] = 1
        elif i == 1:
            # 1つ前から1段上がるから2つ前から2個飛ばし
            # nums.append(nums[-1] + 1)
            nums[i] = nums[i-1] + 1
        else:
            # nums.append((nums[-1] % X + nums[-2] % X) % X)
            nums[i] = (nums[i-1] + nums[i-2]) % X
    return nums[-1]


print(solve(n, hole_ids))
### BUGGY CODE ###

n,q=map(int,input().split())
ab=[[] for _ in range(n)]
for i in range(n-1):
    a,b=map(int,input().split())
    ab[a-1].append(b)
    ab[b-1].append(a)
ans=[0]*n
for i in range(q):
    p,x=map(int,input().split())
    ans[p-1]+=x
yn=[0]*n
yn[0]=1
n1=1
queue=[]
queue2=[]
for i in range(n+10):
    for j in range(len(ab[n1-1])):
        n2=ab[n1-1][j]
        if yn[n2-1]==0:
            yn[n2-1]=1
            queue.append(n2)
    for j in range(len(queue)):
        ans[queue[0]-1]+=ans[n1-1]
        queue2.append(queue.pop(0))
    if len(queue)==0 and len(queue2)==0:
        break
    n1=queue2.pop(0)
print(*ans)


### FIXED CODE ###

from collections import deque
n,q=map(int,input().split())
num=[[] for _ in range(n)]
for i in range(n-1):
    a,b=map(int,input().split())
    num[a-1].append(b)
    num[b-1].append(a)
ans=[0]*n
for i in range(q):
    p,x=map(int,input().split())
    ans[p-1]+=x
queue=deque()
queue.append(0)
seen=[False]*n
for i in range(n):
    if len(queue)==0:
        break
    num1=queue.popleft()
    seen[num1]=True
    num2=num[num1]
    for j in range(len(num2)):
        if seen[num2[j]-1]==False:
            ans[num2[j]-1]+=ans[num1]
            queue.append(num2[j]-1)
for i in ans:
    print(i)
### BUGGY CODE ###

import numpy as np
import scipy.sparse as sps
import scipy.misc as spm
import collections as col
import functools as func
import itertools as ite
import fractions as frac
import math as ma
import cmath as cma
import copy as cp
import sys
def sinput(): return sys.stdin.readline().strip()
def iinput(): return int(sinput())
def imap(): return map(int, sinput().split())
def fmap(): return map(float, sinput().split())
def iarr(n=0):
    if n: return [0 for _ in range(n)]
    else: return list(imap())
def farr(): return list(fmap())
def sarr(n=0):
    if n: return ["" for _ in range(n)]
    else: return sinput().split()
def barr(n): return [False for _ in range(n)]
sys.setrecursionlimit(10**7)
MOD = 10**9 + 7; EPS = sys.float_info.epsilon
PI = np.pi; EXP = np.e; INF = np.inf

n = iinput()
a = iarr()

ans = 1
for num in a: ans *= num
if ans > 10**18: ans = -1
if 0 in a: ans = 0
print(ans)



### FIXED CODE ###

import numpy as np
import scipy.sparse as sps
import scipy.misc as spm
import collections as col
import functools as func
import itertools as ite
import fractions as frac
import math as ma
import cmath as cma
import copy as cp
import sys
def sinput(): return sys.stdin.readline().strip()
def iinput(): return int(sinput())
def imap(): return map(int, sinput().split())
def fmap(): return map(float, sinput().split())
def iarr(n=0):
    if n: return [0 for _ in range(n)]
    else: return list(imap())
def farr(): return list(fmap())
def sarr(n=0):
    if n: return ["" for _ in range(n)]
    else: return sinput().split()
def barr(n): return [False for _ in range(n)]
sys.setrecursionlimit(10**7)
MOD = 10**9 + 7; EPS = sys.float_info.epsilon
PI = np.pi; EXP = np.e; INF = np.inf

n = iinput()
a = iarr()

ans = 1
for num in a:
    ans *= num
    if ans > 10**18: ans = -1; break
if 0 in a: ans = 0
print(ans)
### BUGGY CODE ###

import sys
from collections import deque
import numpy as np
input = sys.stdin.readline
H, W = [int(x) for x in input().strip().split()]
S = np.zeros(H * W).reshape(H, W)
ans = np.zeros(H * W).reshape(H, W)

for h in range(H):
    s = [0 if i == '.' else -1 for i in input().strip()]
    S[h] = np.array(s)

for i, s in enumerate(S):
    c = 0
    q = deque([])
    for k, j in enumerate(s):
        if j == 0:
            c += 1
            q.append(k)
            continue
        for qq in q:
            ans[i, qq] = c
        q = deque([])
        c = 0
    else:
        for qq in q:
            ans[i, qq] = c
 
ans_max = 0
for w in range(W):
    c = 0
    q = []
    for i, s in enumerate(S):
        if s[w] == 0:
            c += 1
            q.append(i)
            continue
        for qq in q:
            ans[qq, w] += c
            ans_max = max(ans_max, ans[qq, w])
        q = []
        c = 0
    else:
        for qq in q:
            ans[qq, w] += c
            ans_max = max(ans_max, ans[qq, w])
        q = []
        c = 0

print(int(ans_max-1))

### FIXED CODE ###

import sys
from collections import deque
import numpy as np
input = sys.stdin.readline
H, W = [int(x) for x in input().strip().split()]
S = np.zeros((H + 2) * (W + 2)).reshape(H + 2, W + 2)
u = np.zeros((H + 2) * (W + 2)).reshape(H + 2, W + 2)
d = np.zeros((H + 2) * (W + 2)).reshape(H + 2, W + 2)
l = np.zeros((H + 2) * (W + 2)).reshape(H + 2, W + 2)
r = np.zeros((H + 2) * (W + 2)).reshape(H + 2, W + 2)

for h in range(H):
    s = [1 if i == '.' else 0 for i in input().strip()]
    S[h + 1] = np.array([0] + s + [0])

for h in range(1, H + 1):
    u[h] = (u[h-1] + 1) * S[h]
    d[H+1-h] = (d[H+2-h] + 1) * S[H+1-h]

for w in range(1, W + 1):
    l[:, w] = (l[:, w-1] + 1) * S[:, w]
    r[:, W+1-w] = (r[:, W+2-w] + 1) * S[:, W+1-w]

ans = u+d+l+r
print(int(ans.max()-3))
### BUGGY CODE ###

N = int(input())

def gcd(p, q):
  if p % q == 0:
    return q
  return gcd(q, p % q)

ans = 0
for x in range(1,N+1):
  for y in range(1,N+1):
    for z in range(1,N+1):
      ans += gcd(gcd(x, y), z)
print(ans)

### FIXED CODE ###

N = int(input())

def gcd(p, q):
  if p % q == 0:
    return q
  return gcd(q, p % q)

ans = 0
for x in range(1,N+1):
  for y in range(1,N+1):
    for z in range(1,N+1):
      ans += gcd(gcd(x, y), z)
print(ans)
### BUGGY CODE ###

# coding: utf-8


def solve(*args: str) -> str:
    t = int(args[0])
    ret = []
    for i in range(1, 3*t+1, 3):
        n = int(args[i])
        A = map(int, args[i+1].split())
        S = map(int, tuple(args[i+2]))

        A0 = []
        A1 = []
        for a, s in zip(A, S):
            if s == 1:
                A0.append(a)
            elif s == 0:
                A1.append(a)
        X = set([0])
        for a in A1:
            for x in X.copy():
                X.add(a ^ x)

        Y = set([0])
        for a in A0:
            for y in Y.copy():
                Y.add(a ^ y)

        ret.append(1*(1 == len(X & Y)))

    return '\n'.join(map(str, ret))


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))


### FIXED CODE ###

# coding: utf-8


def solve(*args: str) -> str:
    t = int(args[0])
    ret = []
    for i in range(1, 3*t+1, 3):
        n = int(args[i])
        A = tuple(map(int, args[i+1].split()))
        S = tuple(map(int, tuple(args[i+2])))

        ans = False
        dp = [0]*(max(A).bit_length()+1)
        for a, s in reversed(tuple(zip(A, S))):
            m = a.bit_length()
            if s == 0:
                while 0 < a and 0 < dp[m]:
                    a ^= dp[m]
                    m = a.bit_length()
                if 0 < a:
                    dp[m] = a
            elif s == 1:
                while 0 < a:
                    if 0 < dp[m]:
                        a ^= dp[m]
                        m = a.bit_length()
                    else:
                        ans = True
                        break

        ret.append(1*ans)

    return '\n'.join(map(str, ret))


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))
### BUGGY CODE ###

def solve(N, Q, S, L_R):
    answers = [None] * Q
    q = 0
    for l, r in L_R:
        pstr = S[l - 1:r]
        count = count_ac(pstr)
        answers[q] = count
        q += 1
    return answers


def count_ac(pstr):
    count = 0
    a_flag = False
    for i in range(len(pstr)):
        s = pstr[i]
        if s == "A":
            a_flag = True
            continue
        elif s == "C":
            if a_flag:
                count += 1
            a_flag = False
        else:
            a_flag = False
    return count

N, Q = map(int, input().split())
S = input()
L_R = [tuple(map(int, input().split())) for _ in range(Q)]
for ans in solve(N, Q, S, L_R):
    print(ans)

### FIXED CODE ###

def solve(N, Q, S, L_R):
    memo = [None] * N
    cumsum = 0
    for i in range(len(S) - 1):
        memo[i] = cumsum
        if S[i] == "A" and S[i + 1] == "C":
            cumsum += 1
    memo[N - 1] = cumsum
    for l, r in L_R:
        print(memo[r - 1] - memo[l - 1])


N, Q = map(int, input().split())
S = input()
L_R = [tuple(map(int, input().split())) for _ in range(Q)]
solve(N, Q, S, L_R)
### BUGGY CODE ###


n = int(input())
arr = list(map(int,input().split()))
arr.sort()

cnt = {}
kouho = []
erat = [True for i in range(10**6+1)]

for i in range(n):
    if arr[i] not in cnt:
        cnt[arr[i]] = 1
    else:
        cnt[arr[i]] += 1
    if erat[arr[i]]:
        kouho.append(arr[i])
    tp = arr[i]
    while True:
        erat[tp] = False
        tp += arr[i]
        if tp > 10**6:
            break
# print(kouho)
ans = 0
for k in kouho:
    if cnt[k] == 1:
        ans += 1


print(ans)

### FIXED CODE ###

n = int(input())
arr = list(map(int,input().split()))
arr.sort()

cnt = {}
kouho = []
erat = [True for i in range(10**6+1)]

for i in range(n):
    if arr[i] not in cnt:
        cnt[arr[i]] = 1
    else:
        cnt[arr[i]] += 1
    if erat[arr[i]]:
        kouho.append(arr[i])
        tp = arr[i]
        while True:
            erat[tp] = False
            tp += arr[i]
            if tp > 10**6:
                break
# print(kouho)
ans = 0
for k in kouho:
    if cnt[k] == 1:
        ans += 1


print(ans)
### BUGGY CODE ###

from collections import defaultdict
n, m = map(int, input().split())
d = defaultdict(list)
for i in range(n):
    a, b = map(int, input().split())
    d[a].append(b)
for i in range(m):
    d[i+1] = sorted(d[i+1])
cnt = 0
for i in range(m, 0, -1):
    max_n = 0
    index = 0
    for j in range(i, 0, -1):
        if d[j] and max_n < d[j][-1]:
            index = j
            max_n = d[j][-1]
    if d[index]:
        cnt += d[index].pop()
print(cnt)



### FIXED CODE ###

from collections import defaultdict
import heapq
n, m = map(int, input().split())
d = defaultdict(list)
for i in range(n):
    a, b = map(int, input().split())
    d[a-1].append(-b)
cnt = 0
a = []
heapq.heapify(a)
for i in range(m):
    for j in d[i]:
        heapq.heappush(a, j)
    if a:
        cnt += -heapq.heappop(a)
print(cnt)
### BUGGY CODE ###

import bisect
import copy

ans = 0
n = int(input())
l = [int(x) for x in input().split()]
l.sort()
for i in range(n-2):
  ln = copy.copy(l)
  del ln[:i+1]
  for j in range(i+1, n-1):
    a = l[i]
    b = l[j]
    del ln[0]
    k = bisect.bisect_right(ln, b - a)
    m = bisect.bisect_left(ln, a + b)
    ans += (m - k)
print(ans)

### FIXED CODE ###

import bisect
import copy

ans = 0
n = int(input())
l = [int(x) for x in input().split()]
l.sort()
for i in range(n-2):
  for j in range(i+1, n-1):
    a = l[i]
    b = l[j]
    m = bisect.bisect_left(l, a + b)
    ans += (m - j - 1)
print(ans)
### BUGGY CODE ###

A, B, C = [int(s) for s in input().split()]

poisonous = False
eaten_cookies = 0

while True:
  if not poisonous and C > 0:
    eaten_cookies += 1
    C -= 1
    poisonous = True
  elif poisonous and A > 0:
    A -= 1
    poisonous = False
  elif B > 0:
    eaten_cookies += 1
    B -= 1
    poisonous = False
  else:
    break

print(eaten_cookies)

### FIXED CODE ###

A, B, C = [int(s) for s in input().split()]
print(min([C, A + B + 1]) + B)
### BUGGY CODE ###

N, K = list(map(int, input().split()))
A = list(map(int, input().split()))

A = [a-1 for a in A]


now = 0
past = []
while not (now in past):
    past.append(now)
    now = A[now]

i_loop = past.index(now)
loop = past[i_loop:]
if K >= i_loop:
    print(loop[(K-i_loop) % len(loop)] +1)
else:
    print(past[K] +1)



### FIXED CODE ###

def func(x):
    return int(x)-1
N, K = list(map(int, input().split()))
A = list(map(func, input().split()))



now = 0
past = []
past_set = set()

for i in range(N):
    if now in past_set:
        break
    past.append(now)
    past_set.add(now)
    now = A[now]


i_loop = past.index(now)
loop = past[i_loop:]
if K >= i_loop:
    print(loop[(K-i_loop) % len(loop)] +1)
else:
    print(past[K] +1)
### BUGGY CODE ###

n, k = map(int,input().split())
h = sorted([int(input()) for _ in range(n)])

hh = [h[i+1] - h[i] for i in range(n-1)]

ans = float("inf")
for i in range(n-k+1):
    ans = min([ans, sum(hh[i:i+k-1])])

print(ans)

### FIXED CODE ###

n,k = map(int, input().split())
h = [int(input()) for i in range(n)]
h.sort()
print(min(h[i+k-1] - h[i] for i in range(n-k+1)))
### BUGGY CODE ###

from itertools import chain
n,m=map(int,input().split())
a=list(map(int,input().split()))
bc=[list(map(int,input().split())) for i in range(m)]
a.sort()
bc.sort(key=lambda x:x[1],reverse=True)
t=[]
for i in range(m):
    t.append([bc[i][1]]*bc[i][0])
t=list(chain.from_iterable(t))

ans=sum(a)
j=0
while j<len(t) and j<n and t[j]>a[j]:
    ans+=t[j]-a[j]
    j+=1

print(ans)


### FIXED CODE ###

n,m=map(int,input().split())
a=list(map(int,input().split()))
bc=[list(map(int,input().split())) for i in range(m)]
a.sort()
bc.sort(key=lambda x:x[1],reverse=True)
t=[]

for b,c in bc:
    a.extend([c]*b)
    if len(a)>2*n:
        break
a.sort(reverse=True)
print(sum(a[:n]))
### BUGGY CODE ###

import sys
n = int(input())
s = input()
q = int(input())
k = list(map(int, sys.stdin.readline().split()))
x = []
for i in s:
  if i == "D":
    x.append(1)
  elif i == "M":
    x.append(2)
  elif i == "C":
    x.append(3)
  else:
    x.append(0)
mrui = [0]* (n+1)
for i in range(1,n+1):
  mrui[i] = mrui[i-1]
  if x[i-1] == 2:
    mrui[i] += 1
for i in k:
  dp = [[0]*4 for _ in range(n)]
  dp[-1][0] = 1
  for j in range(n):
    dp[j][0] += dp[j-1][0]
    dp[j][1] += dp[j-1][1]
    dp[j][2] += dp[j-1][2]
    dp[j][3] += dp[j-1][3]
    if x[j] == 1:
      dp[j][1] += dp[j-1][0]
    elif x[j] == 2:
      dp[j][2] += dp[j-1][1]
    elif x[j] == 3:
      dp[j][3] += dp[j-1][2]
    if j >= i-1:
      if x[j-i+1] == 1:
        dp[j][1] -= 1
        dp[j][2] -= (mrui[j+1]-mrui[j-i+2])
  
  print(dp[n-1][3])

### FIXED CODE ###

import sys
n = int(input())
s = input()
q = int(input())
k = list(map(int, sys.stdin.readline().split()))
x = []
for i in s:
  if i == "D":
    x.append(1)
  elif i == "M":
    x.append(2)
  elif i == "C":
    x.append(3)
  else:
    x.append(0)
mrui = [0]* (n+1)
for i in range(1,n+1):
  mrui[i] = mrui[i-1]
  if x[i-1] == 2:
    mrui[i] += 1
dp = [0,0,0,0]
dp1 = [0,0,0,0]
for i in k:
  dp = [1,0,0,0]
  for j in range(n):
    dp1 = dp
    kon = x[j]
    if kon:
      dp1[kon] += dp[kon-1]
    dp = dp1
    if j >= i-1:
      if x[j-i+1] == 1:
        dp[1] -= 1
        dp[2] -= (mrui[j+1]-mrui[j-i+2])
  
  print(dp1[3])
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
INF = 10**18
AB = [A, B]

dp = [[INF] * 51 for _ in range(1 << N)]
dp[0][0] = 0

for state in range(1 << N):
    size = 0
    for i in range(N):
        if (state & (1 << i)) > 0:
            size += 1

    S = []
    now = size
    for i in range(N):
        if (state & (1 << i)) == 0:
            S.append((i, now))
            now += 1

    for s in range(51):
        for i, now in S:
            val = AB[(i - size) % 2][i]
            if val >= s:
                dp[state | (1 << i)][val] = min(dp[state | (1 << i)][val], dp[state][s] + abs(now - size))

ans = min(dp[(1 << N) - 1])
print(ans if ans < INF else -1)


### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
AB = (A, B)
INF = 10**18

ans = INF
for state in range(1 << N):
    even = []
    odd = []

    for i in range(N):
        isReverse = (state & (1 << i)) >> i
        val = AB[isReverse][i]

        if i % 2 == 0:
            (even, odd)[isReverse].append((val, i))
        else:
            (odd, even)[isReverse].append((val, i))

    if len(even) != -(-N // 2) or len(odd) != N // 2:
        continue

    even.sort()
    odd.sort()
    odd.append((-1, -1))
    V = []
    P = []
    for (l, i), (r, j) in zip(even, odd):
        V.append(l)
        P.append(i)
        if r >= 0:
            V.append(r)
            P.append(j)

    if not all(l <= r for l, r in zip(V, V[1:])):
        continue

    cnt = 0
    for i, p in enumerate(P):
        for q in P[:i]:
            if p < q:
                cnt += 1
    ans = min(ans, cnt)

print(ans if ans != INF else -1)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

N,M = list(map(int,input().split()))
A = list(map(int,input().split()))
Amin = min(A)
tmp = []
for _ in range(M):
    a,b= list(map(int,input().split()))
    if b>=Amin:
        tmp.append([a,b])

tmp = sorted(tmp,key = lambda x:-x[1])
cnt = 0
t = []
if tmp != []:
    for i in range(M):
        t=t+[tmp[i][1]]*tmp[i][0]
        cnt+= tmp[i][0]
        if cnt >=N:
            break
A = sorted(A+t,reverse = 1)

print(sum(A[:N]))


### FIXED CODE ###

import sys
input = sys.stdin.readline

def sol():
    N,M = list(map(int,input().split()))
    A = list(map(int,input().split()))
    tmp = sorted([list(map(int,input().split())) for _ in range(M)],key = lambda x:-x[1])

    t = []
    for a,b in tmp:
        t+=[b]*a
        
        if len(t) >=N:
            break

    A += t
    A.sort(reverse = 1)
    print(sum(A[:N]))

if __name__ == '__main__':
    sol()
### BUGGY CODE ###

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

field = []
for i in range(n + 2):
    row = [0 for j in range(m + 2)]
    field.append(row)
#print(field)

for i in range(1, n + 1):
    for j in range(1, m + 1):
        field[i][j] = 1
#print(field)

for i in range(1, n + 1):
    for j in range(1, m + 1):
        # 左上
        field[i - 1][j - 1] *= -1
        # 上
        field[i - 1][j] *= -1
        # 右上
        field[i - 1][j + 1] *= -1
        # 左
        field[i][j - 1] *= -1
        # 自分
        field[i][j] *= -1
        # 右
        field[i][j + 1] *= -1
        # 左下
        field[i + 1][j - 1] *= -1
        # 下
        field[i + 1][j] *= -1
        # 右下
        field[i + 1][j + 1] *= -1

count = 0
for i in range(1, n + 1):
    for j in range(1, m + 1):
        if field[i][j] == -1:
            count += 1

print(count)


### FIXED CODE ###

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

x = n - 2
if x < 0:
    x = 0

y = m - 2
if y < 0:
    y = 0

if n == 1 and m == 1:
    print(1)
elif n == 1 and m > 1:
    print(y)
elif n > 1 and m == 1:
    print(x)
else:
    print(x * y)
### BUGGY CODE ###

n = int(input())
c=180-n
k=1
while(1):
  if c*k==180*(k-2):
    print(k)
    break
  else:
    k+=1

### FIXED CODE ###

n = int(input())
import numpy as np
x=0
y=0
rad=0
k=1
while(1):
  y+=np.cos(rad*np.pi/180)
  x+=np.sin(rad*np.pi/180)
  if x<0.0001 and y<0.0001:
    print(k)
    break
  else:
    k+=1
    rad+=n
### BUGGY CODE ###

import sys
input = sys.stdin.readline
N,T = map(int,input().split())
data = [list(map(int,input().split())) for _ in range(N)]

dp1 = [[0]*(N+1) for t in range(T+1)] #dp1[t][n] := (data[:n]の中からtまでに食べ切る範囲で美味しく）
dp2 = [[0]*(N+1) for t in range(T+1)] #dp1[t][n] := (data[:n]の中からt-1までに注文する範囲で美味しく)


for t in range(1,T+1):
    for n in range(1,N+1):
        if t-data[n-1][0] >= 0:
            dp1[t][n] = max(dp1[t][n-1],dp1[t-data[n-1][0]][n-1]+data[n-1][1])
            dp2[t][n] = max(dp2[t][n-1],dp2[t-data[n-1][0]][n-1]+data[n-1][1],dp1[t-1][n-1]+data[n-1][1])
        else:
            dp1[t][n] = dp1[t][n-1]
            dp2[t][n] = max(dp2[t][n-1],dp1[t-1][n-1]+data[n-1][1])


print(dp2[T][N])

### FIXED CODE ###

n,t = map(int,input().split())
data = [list(map(int,input().split())) for _ in range(n)]

dp1 = [[0 for i in range(n+1)] for j in range(t+1)]
dp2 = [[0 for i in range(n+1)] for j in range(t+1)]

q = 0
for i in range(1,n+1):
    q = max(q,data[i-1][0])
    dp2[1][i] = q

for i in range(1,t+1):
    for j in range(1,n+1):
        if i-data[j-1][0] >= 0:
            dp1[i][j] = max(dp1[i][j-1],dp1[i-data[j-1][0]][j-1]+data[j-1][1])
            dp2[i][j] = max(dp2[i][j-1],dp2[i-data[j-1][0]][j-1]+data[j-1][1],dp1[i-1][j-1]+data[j-1][1])
        else:
            dp1[i][j] = dp1[i][j-1]
            dp2[i][j] = max(dp2[i][j-1],dp1[i-1][j-1]+data[j-1][1])


print(dp2[t][n])
### BUGGY CODE ###

import collections
n=int(input())
if n==1:
  print(0)
  exit()
b=int(n**0.5)
if all(n%aa!=0 for aa in range(2,b+1)):
  print(1)
  exit()
  
i=2
l=[]
cnt=0
while True:
  cnt+=1
  if n==1:
    break
  if n%i==0:
    l.append(i)
    n=n//i
  else:
    i+=1
c=collections.Counter(l)
v=list(c.values())
ans=0
for vv in v:
  wa=1
  s=1
  while True:
    if vv<wa:
      break
    s+=1
    wa+=s
  ans+=(s-1)
print(ans)

### FIXED CODE ###

import collections
n=int(input())
if n==1:
  print(0)
  exit()
b=int(n**0.5)
i=2
l=[]
while i<=b:
  if n%i==0:
    l.append(i)
    n=n//i
  else:
    i+=1
if n>b:
  l.append(n)
c=collections.Counter(l)
v=list(c.values())

ans=0
for vv in v:
  wa=1
  s=1
  while True:
    if vv<wa:
      break
    s+=1
    wa+=s
  ans+=(s-1)
print(ans)
### BUGGY CODE ###

from collections import deque

N, M, K = map(int, input().split())
A = deque(list(map(int, input().split())))
B = deque(list(map(int, input().split())))

if sum(A) + sum(B) < K:
    print(N + M)
    exit()

ans = 0

while K > 0:
    if len(A) != 0:
        # if len(B) == 0 or A[0] <= B[0]:
        if len(B) == 0 or sum(A) <= sum(B):
            if A[0] <= K:
                K -= A.popleft()
                ans += 1
                continue
    if len(B) != 0:
        # if len(A) == 0 or A[0] >= B[0]:
        if len(A) == 0 or sum(A) >= sum(B):
            if B[0] <= K:
                K -= B.popleft()
                ans += 1
                continue

print(ans)


### FIXED CODE ###

N, M, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

# 累積和の算出
A_sum, B_sum = [0], [0]
for i, a in enumerate(A):
    A_sum.append(A_sum[i] + a)
for i, b in enumerate(B):
    B_sum.append(B_sum[i] + b)

ans = 0
j = M

# 机Aの本を読む所要時間:A_sum[i] … iの値を0から増やしていく
# 机Bの本を読む所要時間:B_sum[j] … iの値を固定し、Mから減らしていく
# A_sum[i]+B_sum[j]がKに収まるiとjの値を見つけ出し、i+jの値を出す
# iの値を増やしながら上記を繰り返し、i+jの最大値が解となる
for i in range(N+1):
    if A_sum[i] > K:
        break
    while B_sum[j] > K - A_sum[i]:
        j -= 1
    ans = max(ans, i+j)

print(ans)