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

#import math
#import itertools
import numpy as np
#from collections import deque
# sys.setrecursionlimit(10 ** 6)
MOD = 998244353
#INF = 10 ** 9
#PI = 3.14159265358979323846

INT = lambda: int(input())
INTM = lambda: map(int,input().split())
STRM = lambda: map(str,input().split())
STR = lambda: str(input())
LIST = lambda: list(map(int,input().split()))
LISTS = lambda: list(map(str,input().split()))

def do():
    n,k=INTM()
    lrs=[]
    for i in range(k):
        lrs.append(LIST())
    pt=np.array([0]*((2*n)+1))
    pt[0]=1
    for i in range(n):
        for l,r in lrs:
            pt[i+l:i+r+1]+=pt[i]
            pt[i+l:i+r+1]=pt[i+l:i+r+1]%MOD
    
    print(pt[n-1]%MOD)


if __name__=='__main__':
    do()

### FIXED CODE ###

#import math
#import itertools
import numpy as np
#from collections import deque
# sys.setrecursionlimit(10 ** 6)
MOD = 998244353
#INF = 10 ** 9
#PI = 3.14159265358979323846

INT = lambda: int(input())
INTM = lambda: map(int,input().split())
STRM = lambda: map(str,input().split())
STR = lambda: str(input())
LIST = lambda: list(map(int,input().split()))
LISTS = lambda: list(map(str,input().split()))

def do():
    n,k=INTM()
    lrs=[]
    for i in range(k):
        lrs.append(LIST())
    pt=np.array([0]*((2*n)+1))
    rui=np.array([0]*((2*n)+1))
    pt[n-1]=1
    rui[n-1]=1
    for i in range(n):
        nt=n-1+i
        for l,r in lrs:
            pt[nt]=(pt[nt]-rui[nt-r-1]+rui[nt-l])%MOD
        rui[nt]=(rui[nt-1]+pt[nt])%MOD
    print(pt[2*n-2]%MOD)
    #print(pt)
    #print(rui)

    
    #print(pt[n-1]%MOD)


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

x = int(input())

a = int(x**(1/5))
b = -150

flag = 0
if flag == 0:
    for i in range(a,a+2000):
        for j in range(b,b+2000):
            if i**5 - j**5 == x:
                print(i,j)
                flag = 1
                break

if flag == 0:
    b = 0
    for i in range(a,a-2000):
        for j in range(b,b-2000):
            if i**5 - j**5 == x:
                print(i,j)
                break

### FIXED CODE ###

x = int(input())

for a in range(-200,200):
    for b in range(-200,200):
        if a**5 - b**5 == x:
            print(a,b)
            break
    else:
        continue
    break
### BUGGY CODE ###

import fractions
import functools

MOD = 10**9+7

def lcm(x, y):
    return (x * y) // fractions.gcd(x, y)

n = int(input())
a = [int(_) for _ in input().split()]
LCM = functools.reduce(lambda x, y : lcm(x, y), a)

ans_arr = [0] * n
for i in range(len(a)):
    ans_arr[i] = LCM // a[i]
print(sum(ans_arr) % MOD)

### FIXED CODE ###

from fractions import gcd
from functools import reduce

MOD = 1000000007

def lcm(x, y):
    return (x * y) // gcd(x, y)

n = int(input())
a = [int(_) for _ in input().split()]
LCM = reduce(lcm, a)

arr = [LCM // _ for _ in a]
print(sum(arr) % MOD)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
A = [0]
for i in range(n):
  A.append(A[-1]+a[i])
ans = 0
for i in range(n):
  x = [j for j in A[i+1:] if j==A[i]]
  if len(x) > 0: ans += len(x)
print(ans)

### FIXED CODE ###

from collections import Counter
n = int(input())
a = list(map(int, input().split()))
A = [0]
for i in range(n):
  A.append(A[-1]+a[i])
A = Counter(A)
ans = 0
for x,y in A.items():
  if y >= 2: ans += (y-1)*y//2
print(ans)
### BUGGY CODE ###

n = int(input())
list_A = input().split()
q = int(input())
for i in range(q):
  SUM = 0
  b, c = input().split()
  if b in list_A:
    list_A = [c if x == b else x for x in list_A]
  else:
    pass
  SUM += sum(map(int, list_A))
  print(SUM)

### FIXED CODE ###

import sys
from collections import Counter
n = int(sys.stdin.readline().rstrip())
A = list(map(int, sys.stdin.readline().rstrip().split()))
q = int(sys.stdin.readline().rstrip())
count_dic = Counter(A)
SUM = sum(A)
for i in range(q):
  b, c = map(int, input().split())
  SUM += count_dic[b]*(c - b)
  count_dic[c] += count_dic[b]
  count_dic[b] = 0
  print(SUM)
### BUGGY CODE ###

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

r = 0
g = 0
b = 0
ans = 0
for s in S:
    if s == "R":
        r += 1
    elif s == "G":
        g += 1
    else:
        b += 1

# print(r, g, b)

for i in range(len(S)-2):
    if S[i] == "R":
        # if not (S[i + 1] == "G" and S[i + 2] == "B") or (S[i + 1] == "B" and S[i + 2] == "G"):
            # ans -= 1
        ans += g * b
        r -= 1
    elif S[i] == "G":
        # if not(S[i+1] == "R" and S[i+2] == "B") or (S[i+1] == "B" and S[i+2] == "R"):
            # ans -= 1
        ans += r * b
        g -= 1
    else:
        # if not(S[i+1] == "G" and S[i+2] == "R") or (S[i+1] == "R" and S[i+2] == "G"):
        #     ans -= 1
        ans += r * g
        b -= 1

for i in range(len(S)):
    for j in range(len(S)):
        j += 1
        if i + j >= len(S) or i + j + j >= len(S):
            break
        if S[i] == "R":
            if S[i + j] == "G" and S[i + j + j] == "B" or S[i + j] == "B" and S[i + j + j] == "G":
                ans -= 1
        if S[i] == "G":
            if S[i + j] == "R" and S[i + j + j] == "B" or S[i + j] == "B" and S[i + j + j] == "R":
                ans -= 1
        if S[i] == "B":
            if S[i + j] == "G" and S[i + j + j] == "R" or S[i + j] == "R" and S[i + j + j] == "G":
                ans -= 1
print(ans)


### FIXED CODE ###

from collections import Counter
N = int(input())
S = input()
tmp = Counter(S)
# print(tmp)
r = tmp["R"]
g = tmp["G"]
b = tmp["B"]
ans = 0
# for s in S:
#     if s == "R":
#         r += 1
#     elif s == "G":
#         g += 1
#     else:
#         b += 1

for i in range(len(S) - 2):
    j = 1
    if S[i] == "R":
        ans += g * b
        r -= 1
    elif S[i] == "G":
        ans += r * b
        g -= 1
    else:
        ans += r * g
        b -= 1
    
    while not (i + j + j >= len(S)):
        if S[i] == "R":
            if S[i + j] == "R":
                j += 1
                continue
            if S[i + j] == "G" and S[i + j + j] == "B" or S[i + j] == "B" and S[i + j + j] == "G":
                ans -= 1
        if S[i] == "G":
            if S[i + j] == "G":
                j += 1
                continue
            if S[i + j] == "R" and S[i + j + j] == "B" or S[i + j] == "B" and S[i + j + j] == "R":
                ans -= 1
        if S[i] == "B":
            if S[i + j] == "B":
                j += 1
                continue
            if S[i + j] == "G" and S[i + j + j] == "R" or S[i + j] == "R" and S[i + j + j] == "G":
                ans -= 1
        j += 1
print(ans)
### BUGGY CODE ###

def main():
    n = int(input())
    a = [int(x) for x in input().split()]

    array = []
    for i in range(n):
        array.append(str(a.index(i+1)+1))
    print(' '.join(array))


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    n = int(input())
    a = [int(x) for x in input().split()]

    array = ['']*n
    for i in range(n):
        array[a[i]-1] = str(i+1)
    print(' '.join(array))


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

N = int(input())
A = input().split()
Q = int(input())
b_c = [input().split() for i in range(Q)]

for i in range(Q):
    sum = 0
    A = [j.replace(b_c[i][0], b_c[i][1]) for j in A]
    for j in range(len(A)):
        sum += int(A[j])
    print(sum)

### FIXED CODE ###

from collections import Counter

N = int(input())
A = list(map(int, input().split()))
Q = int(input())
b_c = [list(map(int, input().split())) for i in range(Q)]

ans = sum(A)
l = Counter(A)
for i in range(Q):
    ans += l[b_c[i][0]] * (b_c[i][1] - b_c[i][0])
    l[b_c[i][1]] += l[b_c[i][0]]
    l[b_c[i][0]] = 0
    print(ans)
### BUGGY CODE ###

N = int(raw_input())
L = map(int, raw_input().split())

L.sort(reverse=True)

sum = 0

for i in range(N):
    a = L[i]

    for j in range(i+1,N):
        b = L[j]
        if 2*b < a:
            break

        c = 0
        start = j
        end = N
        while start != end-1:
            k = (end + start)/2
            c = L[k]
            if  c > a-b:
                start = k
            else:
                end = k

        if start == end-1:
            sum = sum + (start-j)

print sum


### FIXED CODE ###

import bisect

def main():
    N = int(input())
    L = list(map(int, input().split()))

    ans = 0
    L = sorted(L)

    for i in range(N):
        a = L[i]
        for j in range(i+1, N):
            b = L[j]
            target = a+b

            c = bisect.bisect_left(L, target)
            ans = ans + (c-j-1)

    print (ans)
if __name__ == "__main__":
    main()
### BUGGY CODE ###

# E - Crested Ibis vs Monster
def main():
    INF = 1 << 30
    
    H, N, *AB = map(int, open(0).read().split())
    dp = [INF] * (H + 1)  # dp[i] := min magic points to decrease monster's health by i
    dp[0] = 0
    for i in range(H):
        if dp[i] == INF:
            continue
        for a, b in zip(*[iter(AB)] * 2):
            if i + a < H:
                dp[i + a] = min(dp[i + a], dp[i] + b)
            else:
                dp[H] = min(dp[H], dp[i] + b)
    print(dp[H])


if __name__ == "__main__":
    main()


### FIXED CODE ###

# E - Crested Ibis vs Monster
from collections import defaultdict


def main():
    H, N, *AB = map(int, open(0).read().split())
    dp = defaultdict(lambda: 1 << 30)  # dp[i] := min magic points to decrease monster's health by i
    dp[0] = 0
    for a, b in zip(*[iter(AB)] * 2):
        for i in range(H):
            if i not in dp:
                continue
            dp[i + a] = min(dp[i + a], dp[i] + b)
    ans = min(magic for health, magic in dp.items() if health >= H)
    print(ans)


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


N = int(input())
numbers = [int(input()) for i in range(N)]
ans = []

def check_prime(n):
    for i in range(2, n):
        if n % i == 0:
            return 0
    else:
        return 1
    
for n in numbers:
    ans.append(check_prime(n))

print(sum(ans))

### FIXED CODE ###

N = int(input())
numbers = [int(input()) for i in range(N)]
ans = []

def check_prime(n):
    for i in range(2, int(n**0.5)+1):
        if n % i == 0:
            return 0
    else:
        return 1
    
for n in numbers:
    ans.append(check_prime(n))

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

def resolve():
    N, K, Q = map(int, input().split())
    A = []
    for _ in range(Q):
        a = int(input())
        A.append(a)
    for i in range(1, N+1):
        if K-Q+A.count(i)>0:
            print("Yes")
        else:
            print("No")
resolve()

### FIXED CODE ###

def resolve():
    N, K, Q = map(int, input().split())
    A = [K-Q]*N
    for _ in range(Q):
        a = int(input())
        A[a-1] += 1
    for i in range(N):
        if A[i] > 0:
            print("Yes")
        else:
            print("No")
resolve()
### BUGGY CODE ###

from sys import stdin
import itertools

l,r = [int(x) for x in stdin.readline().rstrip().split()]


li = [x%2019 for x in range(l,r+1)]
m = 2020
for i in range(len(li)-1):
    for j in range(i+1,len(li)):
        if li[i]*li[j]%2019 == 0:
            print(0)
            exit()
        else:
            m = min(m,li[i]*li[j]%2019)
print(m)

### FIXED CODE ###

from sys import stdin

l,r = [int(x) for x in stdin.readline().rstrip().split()]
m = 2020
if r - l > 2018:
    print(0)
    exit()
for i in range(l,r):
    for j in range(i+1,r+1):
        if i*j%2019 == 0:
            print(0)
            exit()
        else:
            m = min(m,i*j%2019)
print(m)
### BUGGY CODE ###

import sys
from math import factorial

def comb(a, b):
  return factorial(a) / (factorial(b) * factorial(a-b))


def f(A, a):
  if len(A) == 1:
    return A[0]
  
  if len(A) == 2:
    b1, b2 = A[0], A[1]
    if comb(a, b1) >= comb(a, b2):
      return b1
    else:
      return b2
  
  m = len(A) // 2
  b1, b2, b3 = A[m-1], A[m], A[m+1]
  c1, c2, c3 = comb(a, b1), comb(a, b2), comb(a, b3)
  c = max(c1, c2, c3)  
  
  if c2 == c:
    return b2
  elif c1 == c:
    return f(A[:m], a)
  else:
    return f(A[m+1:], a)


def main():
  input = sys.stdin.readline
  N = int(input())
  A = list(map(int, input().split()))
  A = sorted(A)
  ai = A[-1]
  A = A[:-1]
  aj = f(A, ai)
  print(ai, aj)


if __name__ == '__main__':
  main()

### FIXED CODE ###

import sys
from math import factorial

def comb(a, b):
  return factorial(a) / (factorial(b) * factorial(a-b))


def f(A, a):
  if len(A) == 1:
    return A[0]
  
  if len(A) == 2:
    b1, b2 = A[0], A[1]
    if min(b1, a-b1) >= min(b2, a-b2):
      return b1
    else:
      return b2
  
  m = len(A) // 2
  b1, b2, b3 = A[m-1], A[m], A[m+1]
  c1, c2, c3 = min(b1, a-b1), min(b2, a-b2), min(b3, a-b3)
  c = max(c1, c2, c3)  
  
  if c2 == c:
    return b2
  elif c1 == c:
    return f(A[:m], a)
  else:
    return f(A[m+1:], a)


def main():
  input = sys.stdin.readline
  N = int(input())
  A = list(map(int, input().split()))
  A = sorted(A)
  ai = A[-1]
  A = A[:-1]
  aj = f(A, ai)
  print(ai, aj)


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

a, loop = input().split()
string = input()

import re
for i in range(int(loop)):
  j, k = input().split()
  #print(string[int(j)-1:int(k)].count('AC'))  # TLE
  print(len(re.findall('AC', string[int(j)-1:int(k)])))


### FIXED CODE ###

N, Q = map(int, input().split())
S = input()
t = [0] * (N + 1)
for i in range(N):
  t[i + 1] = t[i] + (1 if S[i : i + 2] == 'AC' else 0)
for i in range(Q):
  l, r = map(int, input().split())
  print(t[r-1] - t[l-1])
### BUGGY CODE ###

import math
n = int(input())
for i in range(int(math.sqrt(n)),n+1,1):
    if n%i==0:
        i=str(i)
#        print(i)
        print(len(i))
        break

### FIXED CODE ###

import math
n = int(input())
for i in range(int(math.sqrt(n)),0,-1):
    if n%i==0:
        a=n//i
#        print(i)
        print(max(len(str(i)),len(str(a))))
        break
### BUGGY CODE ###

N = int(input())
S = input()
MOD = 10**9 + 7

# dp[j] (i番目のiteration時点): 
#   左から(i+1)番目まで並べ終えたときに、最も右の数が、
#   そのときに残っている(N-i)個の数の中で(j+1)番目に小さい数である場合の数
dp = [1] * N
cum = [[i for i in range(1, N+1)], [0]*N]

for i in range(1, N):
  idx = i%2
  if S[i-1] == '<':
    for j in range(N-i):
      dp[j] = cum[idx-1][j]
      if j == 0:
        cum[idx][0] = dp[j]
      else:
        cum[idx][j] = (cum[idx][j-1] + dp[j]) % MOD
  
  else:
    for j in range(N-i):
      dp[j] = (cum[idx-1][N-i] - cum[idx-1][j]) % MOD
      if j == 0:
        cum[idx][0] = dp[j]
      else:
        cum[idx][j] = (cum[idx][j-1] + dp[j]) % MOD

print(dp[0])

### FIXED CODE ###

N = int(input())
S = input()
MOD = 10**9 + 7

# dp[j] (i番目のiteration時点): 
#   左から(i+1)番目まで並べ終えたときに、最も右の数が、
#   そのときに残っている(N-i)個の数の中で(j+1)番目に小さい数である場合の数
dp = [1] * N
cum = [[i for i in range(1, N+1)], [0]*N]

for i in range(1, N):
  idx = i%2
  if S[i-1] == '<':
    for j in range(N-i):
      dp[j] = cum[idx-1][j]
      if j == 0:
        cum[idx][0] = dp[j]
      else:
        cum[idx][j] = (cum[idx][j-1] + dp[j]) % MOD
  
  else:
    for j in range(N-i):
      dp[j] = (cum[idx-1][N-i] - cum[idx-1][j]) % MOD
      if j == 0:
        cum[idx][0] = dp[j]
      else:
        cum[idx][j] = (cum[idx][j-1] + dp[j]) % MOD

print(dp[0])
### BUGGY CODE ###

from collections import defaultdict

N = int(input())
A = [int(input()) for _ in range(N)]
S = sum(A)

DP = [[0]*(S+1) for _ in range(2)]
DP[0][0] = 2
DP[0][A[0]] = 1

# R=G=S/2, B=0
DP2 = [[0]*(S+1) for _ in range(2)]
DP2[0][0] = 1
DP2[0][A[0]] = 1


max_A = A[0]
for i in range(1, N):
    a = A[i]
    max_A += a
    curr_dp = DP[i % 2]
    prev_dp = DP[(i+1) % 2]
    curr_dp2 = DP2[i % 2]
    prev_dp2 = DP2[(i+1) % 2]
    for r in range(max_A+1):
        if r >= a:
            curr_dp[r] = prev_dp[r]*2 + prev_dp[r-a]
            curr_dp2[r] = prev_dp2[r] + prev_dp2[r-a]
        else:
            curr_dp[r] = prev_dp[r]*2
            curr_dp2[r] = prev_dp2[r]
#print(DP)
#print(DP2)

half_S = (S+1)//2
ans = (3**N) - 3*sum(DP[(N-1) % 2][half_S:])
if S % 2 == 0:
    ans += 3*DP2[(N-1) % 2][S//2]

print(ans % 998244353)


### FIXED CODE ###

from collections import defaultdict

N = int(input())
A = [int(input()) for _ in range(N)]
S = sum(A)

DP = [[0]*(S+1) for _ in range(2)]
DP[0][0] = 2
DP[0][A[0]] = 1

# R=G=S/2, B=0
DP2 = [[0]*(S+1) for _ in range(2)]
DP2[0][0] = 1
DP2[0][A[0]] = 1


max_A = A[0]
for i in range(1, N):
    a = A[i]
    max_A += a
    curr_dp = DP[i % 2]
    prev_dp = DP[(i+1) % 2]
    curr_dp2 = DP2[i % 2]
    prev_dp2 = DP2[(i+1) % 2]
    for r in range(max_A+1):
        if r >= a:
            curr_dp[r] = prev_dp[r]*2 + prev_dp[r-a]
            curr_dp2[r] = prev_dp2[r] + prev_dp2[r-a]
        else:
            curr_dp[r] = prev_dp[r]*2
            curr_dp2[r] = prev_dp2[r]
        curr_dp[r] %= 998244353
        curr_dp2[r] %= 998244353
# print(DP)
# print(DP2)

half_S = (S+1)//2
ans = pow(3, N, 998244353)
ans -= 3*sum(DP[(N-1) % 2][half_S:])
if S % 2 == 0:
    ans += 3*DP2[(N-1) % 2][S//2]

print(ans % 998244353)
### BUGGY CODE ###

n, t = [int(i) for i in input().split()]
dishes = []
for _ in range(n):
    a, b = map(int, input().split())
    dishes.append((a, b))

dishes = sorted(dishes, key=lambda x: x[0])

dp = [[0] * t for _ in range(n+1)]

ans = 0

for i in range(n):
    for j in range(t):
        if j < dishes[i][0] :
            dp[i+1][j] = dp[i][j]
        else:
            if dp[i][j] > dp[i][j-dishes[i][0]]+dishes[i][1]:
                dp[i+1][j] = dp[i][j]
            else:
                dp[i+1][j] = dp[i][j-dishes[i][0]]+dishes[i][1]
    ans_i = dp[i][t-1] + max( dishes[i:], key=lambda x: x[1])[1]
    ans = max(ans, ans_i)

print(ans)

### FIXED CODE ###

n, t = [int(i) for i in input().split()]
dishes = []
for _ in range(n):
    a, b = map(int, input().split())
    dishes.append((a, b))

dishes = sorted(dishes, key=lambda x: x[0])

dp = [[0] * t for _ in range(n+1)]

ans = 0

for i in range(n):
    for j in range(t):
        if j < dishes[i][0] :
            dp[i+1][j] = dp[i][j]
        else:
            if dp[i][j] > dp[i][j-dishes[i][0]]+dishes[i][1]:
                dp[i+1][j] = dp[i][j]
            else:
                dp[i+1][j] = dp[i][j-dishes[i][0]]+dishes[i][1]
    ans_i = dp[i][t-1] + max( dishes[i:], key=lambda x: x[1])[1]
    ans = max(ans, ans_i)

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

MOD = 1000000007

s = [-1 if x == '?' else int(x) for x in input()]
n = len(s) + 1

dp = [[0 for x in range(13)] for c in range(n)]
dp[0][0] = 1

for i, x in enumerate(s):
    for j in range(10):
        if (x == -1) or (x == j):
            for ki in range(13):
                dp[i+1][(ki * 10 + j) % 13] += dp[i][ki]
    dp[i+1] = [k % MOD for k in dp[i+1]]

print(dp[len(s)][5])

### FIXED CODE ###

MOD = 1000000007

s = [-1 if x == '?' else int(x) for x in input()]
n = len(s) + 1

dp = [0] * 13
dp[0] = 1

r = [[(j-i)*4%13 for i in range(10)]for j in range(13)]

for i, x in enumerate(s):
    next_dp = [0] * 13
    if x == -1:
        next_dp = [sum(dp[i] for i in j) for j in r]
    else:
        next_dp = [dp[j[x]] for j in r]
    dp = [k % MOD for k in next_dp]

print(dp[5])
### BUGGY CODE ###

import sys


stdin = sys.stdin
def ns(): return stdin.readline().rstrip()
def ni(): return int(stdin.readline().rstrip())
def nm(): return map(int, stdin.readline().split())
def nl(): return list(map(int, stdin.readline().split()))


def main():
    n = ni()
    A = nl()
    for i in range(n):
        S = A[:i] + A[i + 1:]
        D = [abs(S[i + 1] - S[i]) for i in range(n - 2)]
        print(sum(D) + abs(S[0]) + abs(S[-1]))


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys


stdin = sys.stdin
def ns(): return stdin.readline().rstrip()
def ni(): return int(stdin.readline().rstrip())
def nm(): return map(int, stdin.readline().split())
def nl(): return list(map(int, stdin.readline().split()))


def main():
    n = ni()
    A = nl()
    total = sum([abs(A[i + 1] - A[i]) for i in range(n - 1)])
    for i in range(n):
        if i == 0:
            start = abs(A[1])
            end = abs(A[-1])
            print(total - abs(A[1] - A[0]) + start + end)
        elif i == n - 1:
            start = abs(A[0])
            end = abs(A[-2])
            print(total - abs(A[-2] - A[-1]) + start + end)
        else:
            start = abs(A[0])
            end = abs(A[-1])
            print(total - abs(A[i - 1] - A[i]) -
                  abs(A[i] - A[i + 1]) + abs(A[i + 1] - A[i - 1])
                  + start + end)


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

N, W = map(int, input().split())
w = []
v = []
for i in range(N):
	wi, vi = map(int, input().split())
	w.append(wi)
	v.append(vi)

dp = [0] * (W + 1)
dp[w[0]] = v[0]

for i in range(1, N):
	for j in range(W, -1, -1):
		if j - w[i] >= 0 and dp[j - w[i]] + v[i] > dp[j]:
			dp[j] = max(dp[j], dp[j - w[i]] + v[i])
print(max(dp))

### FIXED CODE ###

N,W=map(int,input().split())
wv=[[0,0]]+[list(map(int,input().split())) for _ in range(N)]

dp=[[0 for i in range(W+1)] for j in range(N+1)]

for i in range(1,N+1):
    for j in range(W+1):
        dp[i][j]=dp[i-1][j]
        if j - wv[i][0] >= 0:
            dp[i][j]=max(dp[i][j],dp[i-1][j-wv[i][0]]+wv[i][1])

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

# ABC 84, C - sunuke festival
n = int(input())
A = [int(el) for el in input().split(' ')]
B = [int(el) for el in input().split(' ')]
C = [int(el) for el in input().split(' ')]

total = 0
for b in B:
    total += sum(i < b for i in A) * sum(j > b for j in C)
print(total)


### FIXED CODE ###

# ABC 84, C - sunuke festival
import bisect

n = int(input())
A = sorted([int(el) for el in input().split(' ')])
B = [int(el) for el in input().split(' ')]
C = sorted([int(el) for el in input().split(' ')])

total = 0
for b in B:
    total += bisect.bisect_left(A, b) * (len(C) - bisect.bisect_right(C, b))
print(total)
### BUGGY CODE ###

def main():
    from bisect import bisect_right as br
    n = int(input())
    a = sorted(list(map(int, input().split())))
    b = sorted(list(map(int, input().split())), reverse=True)
    m = n % 2
    xor = 0
    for i in b:
        xor ^= i
    for i in range(n):
        b[i] = 2**28 - b[i]
    ans = 0
    for loop in range(28, -1, -1):
        j = pow(2, loop)
        k = (xor & j) // j
        temp = br(b, j-1)
        for i in range(temp, n):
            b[i] -= j
        b.sort()
        temp = br(a, j-1)
        for i in a[:temp]:
            k += (i & j) // j
        for i in range(temp, n):
            k += (a[i] & j) // j
            a[i] -= j
        x = (k+br(b, 0))*m % 2
        a.sort()
        l = 0
        for i in a:
            while l < n:
                if i >= b[l]:
                    l += 1
                else:
                    break
            x += l % 2
        ans += (x % 2)*j
    print(ans)


main()


### FIXED CODE ###

def main():
    from bisect import bisect_right as br
    n = int(input())
    a = sorted(list(map(int, input().split())))
    b = sorted(list(map(int, input().split())), reverse=True)
    m = n % 2
    xor = 0
    for i in b:
        xor ^= i
    for i in range(n):
        b[i] = 2**28 - b[i]
    ans = 0
    for loop in range(28, -1, -1):
        j = pow(2, loop)
        k = (xor & j) // j
        temp = br(b, j-1)
        for i in range(temp, n):
            b[i] -= j
        b.sort()
        temp = br(a, j-1)
        for i in a[:temp]:
            k += (i & j) // j
        for i in range(temp, n):
            k += (a[i] & j) // j
            a[i] -= j
        x = (k+br(b, 0))*m % 2
        a.sort()
        l = 0
        for i in a:
            while l < n:
                if i >= b[l]:
                    l += 1
                else:
                    break
            x += l % 2
        ans += (x % 2)*j
    print(ans)


main()