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

import sys
readline=sys.stdin.readline

N,K=map(int,readline().split())
DIV = 998244353
steps = []
for i in range(K):
  l,r = map(int,readline().split())
  for j in range(l, r + 1):
    steps.append(j)
    
steps = sorted(steps)

dp = [0] * (N)
dp[0] = 1
for i in range(len(dp)):
  for s in steps:
    if i + s >= len(dp):
      break
    dp[i + s] += dp[i]
    dp[i + s] %= DIV
    
print(dp[-1])


### FIXED CODE ###

import sys
readline = sys.stdin.readline

N,K = map(int,readline().split())
DIV = 998244353

L = [None] * K
R = [None] * K
for i in range(K):
  L[i],R[i] = map(int,readline().split())

dp = [0] * (N + 1)
sdp = [0] * (N + 1)
dp[1] = 1
sdp[1] = 1
  
for i in range(2, len(dp)):
  for j in range(K):
    li = max(i - R[j], 0)
    ri = i - L[j]
    if ri < 0:
      continue
    dp[i] += (sdp[ri] - sdp[li - 1])
    dp[i] %= DIV
  sdp[i] = sdp[i - 1] + dp[i]
  sdp[i] %= DIV
  
print(dp[N])
### BUGGY CODE ###

x,y,z,k = map(int,input().split())
lisa = list(map(int,input().split()))
lisb = list(map(int,input().split()))
lisc = list(map(int,input().split()))
an = []
ans = []
for num in lisb:
    for nu in lisa:an.append(num+nu)
an.sort(reverse=True)
an = an[:min(3001,x*y*z+1)]
for num in lisc:
    for nu in an:ans.append(num+nu)
ans.sort(reverse=True)
for i in range(k):print(ans[i])


### FIXED CODE ###

x,y,z,k = map(int,input().split())
lisa = list(map(int,input().split()))
lisb = list(map(int,input().split()))
lisc = list(map(int,input().split()))
lisa.sort(reverse=True)
lisb.sort(reverse=True)
lisc.sort(reverse=True)
an = []
ans = []
for num in lisb:
    for nu in lisa:
        an.append(num+nu)
an.sort(reverse=True)
an = an[:min(3001,x*y*z+1)]
for num in lisc:
    for nu in an:
        ans.append(num+nu)
ans.sort(reverse=True)
for i in range(k):
    print(ans[i])
### BUGGY CODE ###

N,W = list(map(int,input().split()))
w = [0]
v = [0]

for i in range(N):
  a,b = list(map(int,input().split()))
  w.append(a)
  v.append(b)
  
# dp[i][w] = v
dp = [[0]*(W+1) for i in range(N+1)]

for i in range(1,N+1):
  for j in range(1,W+1):
    if j < w[i]:
      dp[i][j] = dp[i-1][j]
    else:
      dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]]+v[i])  # max(iの品を使わない時, iの品を使う時)

print(dp[N][W])

### FIXED CODE ###

N,W = list(map(int,input().split()))
w = [0]
v = [0]

for i in range(N):
  a,b = list(map(int,input().split()))
  w.append(a)
  v.append(b)
  
# dp[i][w] = v
dp = [[0]*(W+1) for i in range(N+1)]

for i in range(1,N+1):
  for j in range(1,W+1):
    if j < w[i]:
      dp[i][j] = dp[i-1][j]
    else:
      dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]]+v[i])  # max(iの品を使わない時, iの品を使う時)

print(dp[N][W])
### BUGGY CODE ###

k = int(input())

m = 7%k
ans = 1
i = 1
jud = True
p = 70%k
while m != 0:
    m = (m + p)%k
    ans += 1
    i += 1
    p = p*10%k
    if p == 0:
        jud = False
        break
if jud:
    print(ans)
else:
    print(-1)


### FIXED CODE ###

k = int(input())

m = 0
for i in range(k):
    m = (m*10 + 7)%k
    if m == 0:
        ans = i + 1
        break

if m == 0:
    print(ans)
else:
    print(-1)
### BUGGY CODE ###


N = int(input())
S = input()

ans = 0
r = range(N)
kumis = []

for i in r:
    for j in r:
        if j < i: continue
        dji = 2*j -i
        for k in r:
            if k < j: continue
            if dji == k: continue
            kumis.append(tuple([i, j, k]))

for kumi in kumis:
    i, j, k = kumi
    if S[i] != S[j] and S[i] != S[k] and S[j] != S[k]:
        ans += 1

# for i in r:
#     for j in r:
#         if j < i: continue
#         for k in r:
#             if k < j: continue
#             if S[i] != S[j] and S[i] != S[k] and S[j] != S[k]:
#                 kumis.append(tuple([i,j,k]))

# for kumi in kumis:
#     i,j,k = kumi
#     if j-i != k-j:
#         ans+=1

print(ans)

### FIXED CODE ###


N = int(input())
S = input()

r = S.count("R")
g = S.count("G")
b = S.count("B")

all_case = r*g*b

excluded_case = 0
for i in range(N):
    for j in range(i+1, N):
        if S[i] == S[j]: continue
        k = j*2-i
        if k>= N or S[k] == S[i] or S[k] == S[j]: continue
        excluded_case += 1

print(all_case-excluded_case)
### BUGGY CODE ###

import sys
def input(): return sys.stdin.readline().rstrip()
def main():
    n=int(input())
    s=input()
    for ans in ("SS","SW","WS","WW"):
        for c in s[1:]:
            if ans[-1]=="S":
                ans+="W" if (ans[-2]=="W")^(c=="x") else "S"
            else:
                ans+="S" if (ans[-2]=="W")^(c=="x") else "W"
        if ans[0]==ans[-1] and (((ans[0]=="W")^(s[0]=="x"))^(ans[-2]==ans[1])):
            print(ans[:-1])
            sys.exit()
    print(-1)


if __name__=='__main__':
    main()

### FIXED CODE ###

import sys
def input(): return sys.stdin.readline().rstrip()
def main():
    n=int(input())
    s=input()
    for ans in ("SS","SW","WS","WW"):
        for c in s[1:]:
            if ans[-1]=="S":
                ans+="W" if (ans[-2]=="W")^(c=="x") else "S"
            else:
                ans+="S" if (ans[-2]=="W")^(c=="x") else "W"
        if ans[0]==ans[-1] and (((ans[0]=="W")^(s[0]=="x"))^(ans[-2]==ans[1])):
            print(ans[:-1])
            sys.exit()
    print(-1)


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

N, K = map(int, input().split())
P = list(map(int, input().split()))
P = [p - 1 for p in P]
C = list(map(int, input().split()))

vis = [False] * N
ans = [-float('inf')] * N

for root in range(N):
    if vis[root]:
        continue

    cycle = [root]
    costs = [C[root]]
    u = P[root]
    while u != root:
        cycle.append(u)
        costs.append(C[u])
        u = P[u]
    
    for u in cycle:
        vis[u] = True

    L = len(cycle)
    S = sum(costs)
    for i, v in enumerate(cycle):
        # Rewrite [1, K] as form q * L + r, :
        # 0L + 1, 0L + 2, ..., 0L + L
        # 1L + 1, 1L + 2, ..., 1L + L
        # ⋮ 
        # tL + 1, tL + 2, ... (t = floor((K - r) / L))

        # We can ignore 1L + r, 2L + r, ..., (t - 1) * L + r
        # since the total cost of loop is either positive or negative
        # When positive, 0L + r < 1L + r < 2L + r < tL + r
        # When negative, the answer should be 0L + r

        cnt = 0
        for rem in range(1, min(L, K) + 1):
            cnt += costs[(i + rem) % L]
            val1 = cnt
            val2 = cnt + (K - rem) // L * S
            ans[v] = max(ans[v], val1, val2)

print(max(ans))



### FIXED CODE ###

N, K = map(int, input().split())
P = list(map(int, input().split()))
P = [p - 1 for p in P]
C = list(map(int, input().split()))

vis = [False] * N
ans = [-float('inf')] * N

for root in range(N):
    if vis[root]:
        continue
    vis[root] = True

    cycle = [root]
    costs = [C[root]]
    u = P[root]
    vis[u] = True
    while u != root:
        cycle.append(u)
        costs.append(C[u])
        u = P[u]
        vis[u] = True

    # print('-' * 10)
    # print(cycle)
    # print(costs)

    L = len(cycle)
    S = sum(costs)
    for i, v in enumerate(cycle):
        cnt = 0
        for step in range(1, min(L, K) + 1):
            cnt += costs[(i + step) % L]
            val1 = cnt
            val2 = cnt + (K - step) // L * S
            ans[v] = max(ans[v], val1, val2)

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

import numpy as np
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

N = int(input())
S = input()
r_cnt = S.count('R')
g_cnt = S.count('G')
b_cnt = N - (r_cnt + g_cnt)

ans = r_cnt * g_cnt * b_cnt

for i in range(1,(N//2)+1):
	for j in range(N):
		if j + 2*i >= N:
			break
		tmp = [S[j],S[j+i],S[j+2*i]]
		tmp = list(set(tmp))
		if len(tmp) == 3:
			ans -= 1

print(ans)


### FIXED CODE ###

N = int(input())
S = input()
r_cnt = S.count('R')
g_cnt = S.count('G')
b_cnt = N - (r_cnt + g_cnt)

ans = r_cnt * g_cnt * b_cnt

for i in range(1,(N//2)+1):
	for j in range(N):
		if j + 2*i >= N:
			break
		tmp = [S[j],S[j+i],S[j+2*i]]
		tmp = list(set(tmp))
		if len(tmp) == 3:
			ans -= 1

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

from collections import defaultdict
import sys
input = sys.stdin.readline
N = int(input())

tree_dict = defaultdict(list)
for i in range(N-1):
    u, v, w = list(map(int, input().split()))
    tree_dict[u].append((v, w))
    tree_dict[v].append((u, w))
# print(tree_dict)


# 探索
for key, value in tree_dict.items():
    if len(value) == 1:
        break
# print(key)
paint_dict = dict()

q = [key]
paint_dict[key] = 0

idx = 0
while idx < N:
    k = q[idx]
    #print("k", k, paint_dict[k])
    for to, w in tree_dict[k]:
        if to not in q[:idx]:
            if (w + paint_dict[k]) % 2 == 0:
                paint_dict[to] = 0
            else:
                paint_dict[to] = 1
            #print(paint_dict[to], to, w)
            q.append(to)
    idx += 1
for i in range(N):
    print(paint_dict[i+1])


### FIXED CODE ###

from collections import defaultdict
import sys
input = sys.stdin.readline
N = int(input())

tree_dict = defaultdict(list)
for i in range(N-1):
    u, v, w = list(map(int, input().split()))
    tree_dict[u].append((v, w))
    tree_dict[v].append((u, w))


# 任意の1点を選んで周辺を判定していく
FROM, TO = 0, 1
q = [(TO, FROM)]

paint_dict = defaultdict(int)
# 明示的な代入
paint_dict[TO] = 0

idx = 0
while idx < N:
    # 現在のノード(now)から隣接ノード(to)の白黒を定め，そのノードを探索のqに回す
    now_node, prev_node = q[idx]
    for to_node, w in tree_dict[now_node]:
        if to_node != prev_node:
            if (w + paint_dict[now_node]) % 2 == 0:
                paint_dict[to_node] = 0
            else:
                paint_dict[to_node] = 1
            q.append((to_node, now_node))
    idx += 1
for i in range(N):
    print(paint_dict[i+1])
### BUGGY CODE ###

n = int(input())
c = input()
ans = 0

while c.find('WR') != -1:
    c = c[c.find('W')+1:c.rfind('R')]
    ans += 1
print(ans)

### FIXED CODE ###

n = int(input())
c = input()

w = 0
r = c.count('R')
i = 0
ans = max(w, r)
while i <= n - 1:
    if c[i] == 'W':
        w += 1
    else:
        r -= 1
    ans = min(ans, max(w, r))
    i += 1
print(ans)
### BUGGY CODE ###

from collections import Counter, defaultdict
import sys
sys.setrecursionlimit(10 ** 5 + 10)
# input = sys.stdin.readline
from math import factorial
import heapq, bisect
import math
import itertools


import queue
from collections import deque




def main():
    num = int(input())
    data = list(map(int, input().split()))

    for i in range(num):
        data[i] = (data[i], i + 1)
    data.sort(key=lambda x: -x[0])

    ind_list = [0, 0, num + 1, num + 1]
    ans = 0
    for i in range(num):
        ori_num, ori_ind = data[i]
        bisect.insort_left(ind_list, ori_ind)
        add_ind = bisect.bisect_left(ind_list, ori_ind)
        l2, l1 = ind_list[add_ind - 2], ind_list[add_ind - 1]
        r2, r1 = ind_list[add_ind + 2], ind_list[add_ind + 1]
        ans += ((l1 - l2) * (r1 - ori_ind) + (ori_ind - l1) * (r2 - r1)) * ori_num

    print(ans)


if __name__ == '__main__':
    main()



### FIXED CODE ###

from collections import Counter, defaultdict
import sys
sys.setrecursionlimit(10 ** 5 + 10)
input = sys.stdin.readline
from math import factorial
import heapq, bisect
import math
import itertools


import queue
from collections import deque




def main():
    num = int(input())
    data = list(map(int, input().split()))

    for i in range(num):
        data[i] = (data[i], i + 1)
    data.sort(key=lambda x: x[0])

    left = [0, 0] + [i + 1 for i in range(num)]
    right = [i + 1 for i in range(num)] + [num + 1, num + 1]
    ans = 0
    for i in range(num):
        ori_num, ori_ind = data[i]
        l1 = left[ori_ind]
        l2 = left[l1]
        r1 = right[ori_ind]
        r2 = right[r1]

        ans += ((l1 - l2) * (r1 - ori_ind) + (ori_ind - l1) * (r2 - r1)) * ori_num

        right[l1] = r1
        left[r1] = l1

    print(ans)


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

from scipy.misc import*;M=10**9+7;n,m,k=map(int,input().split());s=lambda x,y:sum(y*y*i*(x-i)for i in range(x));print((s(n,m)+s(m,n))%M*comb(n*m-2,k-2,1)%M)

### FIXED CODE ###

class Factorial:
    def __init__(self,n,mod):
        self.f=[1]
        for i in range(1,n+1):
            self.f.append(self.f[-1]*i%mod)
        self.i=[pow(self.f[-1],mod-2,mod)]
        for i in range(1,n+1)[::-1]:
            self.i.append(self.i[-1]*i%mod)
        self.i.reverse()
    def factorial(self,i):
        return self.f[i]
    def ifactorial(self,i):
        return self.i[i]
    def comb(self,n,k):
        return self.f[n]*self.i[n-k]*self.i[k]
n,m,k=map(int,input().split())
M=10**9+7
print((sum(m*m*i*(n-i)for i in range(n))+sum(n*n*i*(m-i)for i in range(m)))*Factorial(n*m,M).comb(n*m-2,k-2)%M)
### BUGGY CODE ###

#!/usr/bin/env python

def factorization(n):
    ret = []
    tmp = n
    for i in range(2, int(n ** 0.5 + 1)):
        cnt = 0
        if tmp % i == 0:
            while tmp % i == 0:
                cnt += 1
                tmp //= i
            ret.append([i, cnt])

    if tmp != 1:
        ret.append([tmp, 1])
    if ret == []:
        ret.append[n, 1]

    return ret


def main():
    n = int(input())
    ret = 1
    for i in range(2, n+1):
        fact = factorization(i)
        add = 1
        for f in fact:
            add *= f[1] + 1
        ret += i * add

    print(ret)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python

def main():
    n = int(input())
    ret = 0
    for i in range(1, n+1):
        x = n // i
        ret += i * x * (x+1) // 2

    print(ret)

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

import sys
sys.setrecursionlimit(10000000)
n=int(input())
graph=[[] for i in range(n)]
node=[[-1]*n for i in range(n)]
color=[0]*n
visited=[False]*n
for i in range(n-1):
    a,b,c=map(int,input().split())
    graph[a-1].append(b-1);node[a-1][b-1]=c%2
    graph[b-1].append(a-1);node[b-1][a-1]=c%2
search=[[0,i] for i in graph[0]]
while search!=[]:
  a=search.pop(0)
  if visited[a[1]]==True:continue
  search=search+[[a[1],i] for i in graph[a[1]]]
  color[a[1]]=color[a[0]]^node[a[0]][a[1]]
  visited[a[1]]=True
for i in color:
  print(i)


### FIXED CODE ###

import sys
sys.setrecursionlimit(1000000)
n=int(input())
graph=[[] for i in range(n)]
color=[-1]*n
for i in range(n-1):
    a,b,c=map(int,input().split())
    graph[a-1].append([b-1,c%2])
    graph[b-1].append([a-1,c%2])
def coloring(pre,c):
  color[pre]=c
  for i,j in graph[pre]:
    if color[i]<0:
      coloring(i,color[pre]^j)
coloring(0,1)
for i in color:
  print(i)
### BUGGY CODE ###

import collections
def bfs(sy, sx, gy, gx):
    q = collections.deque()
    q.append((sy, sx))
    q2 = collections.deque()
    q2.append((sy, sx))
    dist = [[-1] * W for _ in range(H)]
    dist[sy][sx] = 0
    dx = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    dx2 = [(-2, -2), (-2, -1), (-2, 0), (-2, 1), (-2, 2), (-1, -2), (-1, -1),(-1, 1), (-1, 2), (0, -2), (0, 2), (1, -2), (1, -1), (1, 1), (1, 2), (2, -2), (2, -1), (2, 0), (2, 1), (2, 2)]
    while len(q) != 0 and len(q2) != 0:
        h, w = q.popleft()
        d = dist[h][w]
        for x, y in dx:
            h2 = h + y
            w2 = w + x
            if h2 >= 0 and h2 < H and w2 >= 0 and w2 < W:
                if grid[h2][w2] == ".":
                    if dist[h2][w2] == -1:
                        dist[h2][w2] = d
                        q.append((h2, w2))
                        q2.append((h2, w2))
                    elif d < dist[h2][w2]:
                        dist[h2][w2] = d
                        q.append((h2, w2))
                        q2.append((h2, w2))
        h, w = q2.popleft()
        d = dist[h][w]
        for x, y in dx2:
            h2 = h + y
            w2 = w + x
            if h2 >= 0 and h2 < H and w2 >= 0 and w2 < W:
                if grid[h2][w2] == "." and (dist[h2][w2] == -1 or d + 1 < dist[h2][w2]):
                    dist[h2][w2] = d + 1
                    q.append((h2, w2))
                    q2.append((h2, w2))
    return dist[gy][gx]

H, W = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
grid = [input() for _ in range(H)]
print(bfs(Ch-1, Cw-1, Dh-1, Dw-1))


### FIXED CODE ###

import sys
input = sys.stdin.readline
import collections
def bfs(sy, sx, gy, gx):
    q = collections.deque()
    q.append((sy, sx))
    dist = [[-1] * W for _ in range(H)]
    dist[sy][sx] = 0
    dx = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    dx2 = [(-2, -2), (-2, -1), (-2, 0), (-2, 1), (-2, 2), (-1, -2), (-1, -1),(-1, 1), (-1, 2), (0, -2), (0, 2), (1, -2), (1, -1), (1, 1), (1, 2), (2, -2), (2, -1), (2, 0), (2, 1), (2, 2)]
    while len(q) != 0:
        h, w = q.popleft()
        d = dist[h][w]
        for x, y in dx:
            h2 = h + y
            w2 = w + x
            if h2 >= 0 and h2 < H and w2 >= 0 and w2 < W:
                if grid[h2][w2] == ".":
                    if dist[h2][w2] == -1:
                        dist[h2][w2] = d
                        q.appendleft((h2, w2))
                    elif d < dist[h2][w2]:
                        dist[h2][w2] = d
                        q.appendleft((h2, w2))
        for x, y in dx2:
            h2 = h + y
            w2 = w + x
            if h2 >= 0 and h2 < H and w2 >= 0 and w2 < W:
                if grid[h2][w2] == "." and (dist[h2][w2] == -1 or d + 1 < dist[h2][w2]):
                    dist[h2][w2] = d + 1
                    q.append((h2, w2))
    return dist[gy][gx]

H, W = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
grid = [input() for _ in range(H)]
print(bfs(Ch-1, Cw-1, Dh-1, Dw-1))
### BUGGY CODE ###

def Replacing():

    Num = int(input())

    value_A = list(map(int,input().split()))

    NumB = int(input())

    for i in range(NumB):
        value_B = list(map(int,input().split()))

        vb_0 = value_B[0]
        vb_1 = value_B[1]

        value_A = [vb_1 if j == vb_0 else j for j in value_A]

        print(sum(value_A))

if __name__ == '__main__':
    Replacing()


### FIXED CODE ###

from collections import Counter

def Replacing():

    Num = int(input())

    value_A = list(map(int,input().split()))

    Sum = sum(value_A)
    Counter_value = Counter(value_A)

    NumB = int(input())

    for i in range(NumB):
        value_B = list(map(int,input().split()))

        Sum += (value_B[1] - value_B[0])*Counter_value[value_B[0]]
        Counter_value[value_B[1]] += Counter_value[value_B[0]]
        Counter_value[value_B[0]] = 0

        print(Sum)

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

def gcd(a, b):
	while b != 0:
		a, b = b, a % b
	return a

N = int(input())
A = list(map(int, input().split()))
L = [0]
R = [0]
ans = 0
for i in range(N):
	L.append(gcd(L[i],A[i]))
	R.insert(0,gcd(R[0],A[N-1-i]))
L.append(0)
R.insert(0,0)
for i in range(N):
	ans = max(ans,(gcd(L[i], R[i+2])))
print(ans)

### FIXED CODE ###

def gcd(a, b):
	while b != 0:
		a, b = b, a % b
	return a

N = int(input())
A = list(map(int, input().split()))
L = [0]*(N+2)
R = [0]*(N+2)
ans = 0
for i in range(N):
	L[i+1] = (gcd(L[i],A[i]))
	R[N-i] = (gcd(R[N-i+1],A[N-1-i]))
for i in range(N):
	ans = max(ans,(gcd(L[i], R[i+2])))
print(ans)
### BUGGY CODE ###

'''
N Q
s
t_1 d_1
\vdots
t_{Q} d_Q
'''
N, Q = map(int, input().split(' '))
s = input()
tile, dir = [], []
for _ in range(Q):
  pre, suff = input().split(' ')
  tile.append(pre)
  dir.append(suff)

S = {}
  
def move(golem, i, d):
  if golem[i] == 0:  # No golem
    return golem
  elif golem[i] > 0:
    if d == 'L':
      if i > 0:
        golem[i-1], golem[i] = golem[i-1] + golem[i], 0
      elif i == 0:
        golem[i] = 0
    elif d == 'R':
      if i < N-1:
        golem[i], golem[i+1] = 0, golem[i] + golem[i+1]
      elif i == N-1:
        golem[i] = 0
  return golem

def move_golem(golem, s, t, d):
  if t not in S.keys():
    S[t] = [i for i, x in enumerate(s) if x == t]
  for i in S[t]:
    golem = move(golem, i, d)
  return golem
  
golem = [1]*N
for t, d in zip(tile, dir):
  golem = move_golem(golem, s, t, d)
print(sum(golem))

### FIXED CODE ###

N, Q = map(int, input().split(' '))
S = '0' + input() + '0'
A = [list(input().split(' ')) for _ in range(Q)]
l = 0
r = N+1
for i in range(Q-1, -1, -1):
  t, d = A[i]
  if t == S[l] and d == 'R':
    l -= 1
  elif t == S[l+1] and d == 'L':
    l += 1
    
  if t == S[r] and d == 'L':
    r += 1
  elif t == S[r-1] and d == 'R':
    r -= 1
print(max(0, r-l-1))
### BUGGY CODE ###

from sys import stdin

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

a = list(map(int, input().split()))
b = list(map(int, input().split()))

A = [0]
B = [0]

for i in range(0, n):
    A.append(A[i]+a[i])
for i in range(0, m):
    B.append(B[i]+b[i])


ans= 0
for i in range(n + 1):
    j = m
    if A[i] > k:
        break
    while A[i] + B[j] > k:
        j -= 1
    ans = max(ans, i + j)

print(ans)

### FIXED CODE ###

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

a=list(map(int,input().split()))
b=list(map(int,input().split()))


a_pre,b_pre=[0],[0]

for i in range(n):
	a_pre.append(a_pre[i]+a[i])

for i in range(m):
	b_pre.append(b_pre[i]+b[i])

ans,j=0,m
for i in range(n+1):
	if a_pre[i]>k:
		break
	while b_pre[j]>k-a_pre[i]:
		j-=1

	ans=max(ans,i+j)

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

import sys
readline = sys.stdin.buffer.readline
from collections import deque
INF = float('inf')


H, W, K = map(int, readline().split())
sy, sx, gy, gx = map(int, readline().split())
sy -= 1
sx -= 1
gx -= 1
gy -=1
lake = [list(readline().decode('utf-8').strip()) for _ in range(H)]
dist = [[INF] * (W+2) for _ in range(H+2)]
dxy = ((1, 0), (0, 1), (-1, 0), (0, -1))
Q = deque()
Q.append((sy, sx, 0))
dist[sy][sx] = 0
while Q:
    y,x,d = Q.popleft()
    if (y,x) == (gy, gx):
        print(d)
        sys.exit()
    for dx,dy in dxy:
        n_y = y
        n_x = x
        for _ in range(K):
            n_y +=dy
            n_x +=dx

            if 0<=n_x<W and 0<=n_y<H and lake[n_y][n_x] != '@':
                if dist[n_y][n_x]<d:
                    break
                elif dist[n_y][n_x] == INF:
                    dist[n_y][n_x] = d + 1
                    Q.append((n_y,n_x,d+1))
                else:
                    continue

            else:
                break
print('-1')

### FIXED CODE ###

import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
from collections import deque
 
H, W, K = map(int,readline().split())
x1, y1, x2, y2 = map(int,readline().split())
x1 -= 1; y1 -= 1; x2 -= 1; y2 -= 1
C = read().split()

dist = [[-1]*W for i in range(H)]
dist[x1][y1] = 0
d = deque([[x1, y1]])
dxy= [[1, 0], [0, 1], [-1, 0], [0, -1]]
while d:
  x, y = d.popleft()
  if (x, y) == (x2, y2):
    print(dist[x][y])
    quit()
  for dx, dy in dxy:
    xx = x; yy = y
    for i in range(K):
      xx += dx; yy += dy
      if 0<=xx<H and 0<=yy<W and C[xx][yy]!='@':
        if 0 <= dist[xx][yy] <= dist[x][y]:
          break
        if dist[xx][yy] == -1:
           d.append([xx, yy])
        dist[xx][yy] = dist[x][y] + 1
      else:
        break

print(-1)
### BUGGY CODE ###

n, m = map(int, input().split())
AB = [tuple(map(int, input().split())) for _ in range(n)]
AB.sort(key=lambda ab: -ab[1])
counts = [0] * m
cands = [0] * m
total = 0
for j in range(n):
    if AB[j][0] > m:
        continue
    for i in range(AB[j][0] - 1 + counts[AB[j][0] - 1], m):
        if cands[i] > 0:
            continue
        cands[i] = AB[j][1]
        counts[AB[j][0] - 1] += 1
        total += 1
        break
    if total == m:
        break
print(sum(cands))


### FIXED CODE ###

import heapq

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

cands = [[] for _ in range(m)]
for _ in range(n):
    a, b = map(int, input().split())
    if a <= m:
        cands[a - 1].append(-b)

heapq.heapify(cands[0])
total = 0
for i in range(m):
    if len(cands[0]) > 0:
        total -= heapq.heappop(cands[0])
    if i < m - 1:
        for c in cands[i + 1]:
            heapq.heappush(cands[0], c)

print(total)