Harryxun/stf_run huggingface dataset:
A1 = list(map(int,input().split()))
A2 = list(map(int,input().split()))
A3 = list(map(int,input().split()))
N = int(input())
listb = [input() for i in range(N)]

for item in listb:
    for i in range(3):
        if A1[i] == item:
            A1[i] = 0
    for j in range(3):
        if A2[j] == item:
            A2[j] = 0
    for k in range(3):
        if A3[k] == item:
            A3[k] = 0
flg = false
if sum(A1) == 0 or sum(A2) == 0 or sum(A3) == 0:
    print('Yes')
    exit()
for i in range(3):
    if A1[i] == A2[i] and A2[i] == A3[i]:
        print('Yes')
        exit()
if A1[1] == A2[2] == A3[3] or A1[3] == A2[2] == A3[1]:
    print 'Yes'
    exit()
print('No')

### FIXED CODE ###

A1 = list(map(int,input().split()))
A2 = list(map(int,input().split()))
A3 = list(map(int,input().split()))
N = int(input())
listb = [int(input()) for i in range(N)]

for item in listb:
    for i in range(3):
        if A1[i] == item:
            A1[i] = 0
    for j in range(3):
        if A2[j] == item:
            A2[j] = 0
    for k in range(3):
        if A3[k] == item:
            A3[k] = 0
if sum(A1) == 0 or sum(A2) == 0 or sum(A3) == 0:
    print('Yes')
    exit()
for i in range(3):
    if A1[i] == A2[i] and A2[i] == A3[i]:
        print('Yes')
        exit()
if A1[0] == A2[1] == A3[2] or A1[2] == A2[1] == A3[0]:
    print('Yes')
    exit()
print('No')
N=int(input())
S=input()

lb=0
rb=N+1
while rb-lb>1:
    mid=(lb+rb)//2
    f=0
    x=0
    a=[]
    for i,s in enumerate(S[:mid]):
        x+=pow(26,i)*(ord(s)-ord('a'))
    a+=[x]
    m=pow(26,mid-1)
    se=set([])
    for i,s in enumerate(S[mid:]):
        x-=ord(S[i])
        x//=26
        x+=m*(ord(s)-ord('a'))
        if i>=mid-1:
            se.add(a[i-mid-1])
        if x in se:
            f=1
            break
        else:
            a+=[x]
    if f:
        lb=mid
    else:
        rb=mid
print(lb)


### FIXED CODE ###

import itertools
N = int(input())
S = input()
dp = [[0] * N for _ in range(N)]
ans = 0
for i, j in itertools.combinations(range(N), 2):
    if S[i] == S[j]:
        dp[i][j] = dp[i - 1][j - 1] + 1
    else:
        dp[i][j] = 0
    ans = max(ans, min(j - i, dp[i][j]))
print(ans)
i = 1
while True:
    x = int(input())
    if x == 0: break
    print("Case {}: {}".format(i, n))
    i += 1


### FIXED CODE ###

# -*- coding: utf-8 -*-
c = 1
while True:
    n = int(input())
    if n == 0:
        break
    print('Case {0}: {1}'.format(c, n))
    c += 1
a, b = map(int, input().split())
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a
n = gcd(a, b)

def cd(num):
    k = []
    for i in [1,2] + list(range(3,num+1,2)):
        if num%i == 0:
            if is_prime(i):
                k.append(i) 
    return k

def is_prime(num):
    for i in range(2, num):
        if num % i == 0:
            return False
    return True


gc = gcd(a,b)
c = cd(gc)

print(len(c))

### FIXED CODE ###

def f(n):
    res = set()
    for i in range(2, int(n ** 0.5)):
        if n % i: continue
        while not n % i: n //= i
        res.add(i)
    return res | {n}
 
a, b = map(int,input().split())
print(len(f(a) & f(b) | {1}))
n, m, k = map(int, input().split())

candidates = [0] * n
friends = [set() for _ in range(n)]
blocks = [set() for _ in range(n)]
parent = [i for i in range(n)]
sizes = [1 for _ in range(n)]

def root(x):
    global parent
    if parent[x] == x:
        return x
    else:
        parent[x] = root(parent[x])
        return parent[x]

def unite(x, y):
    global parent
    global sizes
    x = root(x)
    y = root(y)
    # print(x, y)
    if x == y:
        return
    parent[y] = x # ここがREの原因らしいが..
    sizes[x] += sizes[y]
    sizes[y] = sizes[x]

def same(x, y):
    return root(x) == root(y)

for _ in range(m):
    a, b = map(int, input().split())
    friends[a - 1].add(b - 1)
    friends[b - 1].add(a - 1)
    unite(a - 1, b - 1)

for _ in range(k):
    c, d = map(int, input().split())
    if same(c - 1, d - 1):
        blocks[c - 1].add(d - 1)
        blocks[d - 1].add(c - 1)

for i in range(n):
    candidates[i] = sizes[root(i)] - len(friends[i]) - len(blocks[i]) - 1

print(*candidates)


### FIXED CODE ###

class UnionFind:
    def __init__(self, n):
        self.parents = [i for i in range(n + 1)]
        self.sizes = [1] * (n + 1)

    def find(self, x):
        if self.parents[x] == x:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if y < x:
            x, y = y, x
        self.parents[y] = x
        self.sizes[x] += self.sizes[y]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def size(self, x):
        return self.sizes[self.find(x)]


n, m, k = map(int, input().split())
uf = UnionFind(n)
friends = [0] * n
blocks = [0] * n
for i in range(m):
    a, b = map(int, input().split())
    friends[a - 1] += 1
    friends[b - 1] += 1
    uf.unite(a - 1, b - 1)
for i in range(k):
    c, d = map(int, input().split())
    if uf.same(c - 1, d - 1):
        blocks[c - 1] += 1
        blocks[d - 1] += 1
ans = [0] * n
for i in range(n):
    ans[i] = uf.size(i) - friends[i] - blocks[i] - 1
print(*ans)
a,b,c,d= input().split()
N = int(d)
R= int(a)
G = int(b)
B = int(c)

max_r = N//R
max_g = N//G
max_b = N//B
count = 0
for i in range(max_r+1):
 rest_n_r= N - R*i
 max_g = rest_n_r // G
 for j in range(max_g+1):
  rest_n_r_g = rest_n_r - G*j
  mod = rest_n_r_g % B
  if(mod == 0):
   count += 1

print(count)

### FIXED CODE ###

a,b= input().split()
N = int(a)
K = int(b)
print(N-K+1)
# coding: utf-8
A, B, M = map(int, input().split())
# print("A:", A, "B:", B, "M:", M)
a = list(map(int, input().split()))
# print("a:", a)
b = list(map(int, input().split()))
# print("b:", b)
z = [list(map(int, input().split())) for _ in range(M)]
# print("z:", z)
min_ = [a[i] + b[i] for i in range(max(A, B))]
# print("min:", min_)
for i in range(M):
    x, y, c = z[i]
    # print("x:", x, "y:", y, "c:", c)
    num = a[x - 1] + b[y - 1] - c
    # print("num:", num)
    min_.append(num)
# print(min_)
print(min(min_))

### FIXED CODE ###

# coding: utf-8
A, B, M = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
a1 = sorted(a)
b1 = sorted(b)
z = [list(map(int, input().split())) for _ in range(M)]

num1 = a1[0] + b1[0]
# print("num1:", num1)
for i in range(M):
    x, y, c = z[i]
    num = a[x - 1] + b[y - 1] - c
    if num < num1:
        num1 = num
print(num1)
import re
from sys import stdin
N=(stdin.readline().rstrip())

for i in range(7):
    mae="keyence"[0:i+1]
    ato="keyence"[i+1:8]
    if re.match(".*keyence.*",N):
        print("YES")
        break
    if re.match("%s.*%s"%(mae, ato),N):
        print("YES")
        cnt+=1
        break
if i==6:
    print("NO")

### FIXED CODE ###

import re
from sys import stdin
N=(stdin.readline().rstrip())
for i in range(7):
    mae="keyence"[0:i+1]
    ato="keyence"[i+1:8]
    if re.search(".*keyencekeyence",N):
        if (re.sub('.*keyencekeyence', '', N)=="")==True:
            print("YES")
            break
    if re.search("keyencekeyence.*",N):
        if (re.sub('keyencekeyence.*', '', N)=="")==True:
            print("YES")
            break
    if (re.sub('.*keyence', '', N)=="")==True:
        print("YES")
        break
    if (re.sub('keyence.*', '', N)=="")==True:
        print("YES")
        break
    if re.match("%s.*%s"%(mae, ato),N):
        if (re.sub('%s.*%s'%(mae,ato) ,"", N)=="")==True:
            print("YES")
            break
if i==6:
    print("NO")
if __name__ == '__main__':
    import sys
    input = sys.stdin.readline

    n = int(input())
    s = input().rstrip()
    eng_list = 'abcdefghigklmnopqrstuvwxyz'
    eng_dict = {}
    for i in eng_list:
        eng_dict[i] = 1
    for i in s:
        eng_dict[i] += 1
    ans = 1
    size = 10**9+7
    for j in eng_dict.values():
        ans = (ans*j)%size
    print(ans-1)


### FIXED CODE ###

if __name__ == '__main__':
    import sys
    input = sys.stdin.readline

    n = int(input())
    s = input().rstrip()
    eng_list = 'abcdefghigklmnopqrstuvwxyz'
    eng_dict = {}
    for i in eng_list:
        eng_dict[i] = 1
    for i in s:
        try:
            eng_dict[i] += 1
        except KeyError:
            eng_dict[i] = 2
    ans = 1
    size = 10**9+7
    for i in eng_dict.values():
        ans = (ans*i)%size
    print((ans-1)%size)
n = int(input())
list = [0] * 100000

for i in range(n):
  num = int(input())
  if list[num - 1] == 0:
    list[num - 1] = 1
  else:
    list[num - 1] = 0

print(sum(list))

### FIXED CODE ###

n = int(input())
A = [0] * n
for i in range(n):
  A[i] = int(input())
from collections import Counter
C = Counter(A)
counter = 0
for val in C.values():
  counter += val % 2
print(counter)
#coding: utf-8
N, Q = map(int, input().split())
S = input()
S_l = []
for i in range(len(S)):
    if S[i] == "A" and S[i+1] == "C":
        S_l.append([i+1, i+2])
for i in range(Q):
    l, r = map(int, input().split())
    cnt = 0
    for j in range(len(S_l)):
        if l <= S_l[j][0] <=r and l <= S_l[j][1] <= r:
            cnt += 1
    print(cnt)

### FIXED CODE ###

#coding: utf-8
N, Q = map(int, input().split())
S = input()
T = [0]
for i in range(N-1):
    if S[i] == "A" and S[i+1] == "C":
        T.append(T[i] + 1)
    else:
        T.append(T[i])
for j in range(Q):
    l, r = map(int, input().split())
    print(T[r-1] - T[l-1])
def how(c):
    if float(c).is_integer() == True:
        return int(float(c)),0
    else:
        dot=0
        while c[dot]!=".":
            dot+=1
        c = list(c)
        del c[dot]
        c ="".join(c)
        return int(c),len(c)-dot

def lo2(n):
    count = 0
    while n%2==0:
        n=n//2
        count+=1
    return count

def lo5(n):
    count=0
    while n%5==0:
        n=n//5
        count+=1
    return count

N = int(input())

A = []

for i in range(N):
    A.append(how(input()))


ruiseki = [[0]*80 for i in range(80)]

motoseisuu=0
for i in range(N):
    ruiseki[A[i][1]-lo2(A[i][0])+60][A[i][1]-lo5(A[i][0])+60]+=1
    if A[i][1]==0:
        motoseisuu +=1

for i in range(1,80):
    for j in range(1,80):
        ruiseki[i][j]=ruiseki[i-1][j]+ruiseki[i][j-1]-ruiseki[i-1][j-1]+ruiseki[i][j]


ans = 0
for i in range(N):
    ans+=ruiseki[lo2(A[i][0])+60-A[i][1]][lo5(A[i][0])+60-A[i][1]]

print((ans-motoseisuu)//2)


### FIXED CODE ###

def how(c):
    if float(c).is_integer() == True:
        return int(float(c)),0
    else:
        dot=0
        while c[dot]!=".":
            dot+=1
        c = list(c)
        del c[dot]
        c ="".join(c)
        return int(c),len(c)-dot

def lo2(n):
    count = 0
    while n%2==0:
        n=n//2
        count+=1
    return count

def lo5(n):
    count=0
    while n%5==0:
        n=n//5
        count+=1
    return count

N = int(input())

A = []

for i in range(N):
    A.append(how(input()))


ruiseki = [[0]*120 for i in range(120)]

motoseisuu=0
for i in range(N):
    ruiseki[A[i][1]-lo2(A[i][0])+60][A[i][1]-lo5(A[i][0])+60]+=1
    if A[i][1]==0:
        motoseisuu +=1

for i in range(1,120):
    for j in range(1,120):
        ruiseki[i][j]=ruiseki[i-1][j]+ruiseki[i][j-1]-ruiseki[i-1][j-1]+ruiseki[i][j]


ans = 0
for i in range(N):
    ans+=ruiseki[lo2(A[i][0])+60-A[i][1]][lo5(A[i][0])+60-A[i][1]]

print((ans-motoseisuu)//2)
import math

x1,y1,x2,y2 = map(int,input().split())

x_dis = abs(x1-x2)
y_dis = abs(y1-y2)

hypo = math.sqrt(x_dis**2 + y_dis**2)
dis = round(hypo,8)

print(dis)


### FIXED CODE ###

import math

x1,y1,x2,y2 = map(float,input().split())

x_dis = abs(x1-x2)
y_dis = abs(y1-y2)

hypo = math.sqrt(x_dis**2 + y_dis**2)
dis = round(hypo,8)

print(dis)
import math

X, Y = [int(x) for x in input().split(" ")]

N = (X + Y) / 3
i = (2 * X - Y) / 3
if N < 0 or N != int(N):
    print(0)
if i < 0 or i != int(i):
    print(0)

N = int(N)
i = int(i)

ans = math.factorial(N) / (math.factorial(i) * math.factorial(N-i))
print(ans)


### FIXED CODE ###

MOD = 10**9+7
fact = [1, 1]
for i in range(2, 10**6+1):
    fact.append((fact[i-1] * i) % MOD)


def comb(n, k):
    return (fact[n] * pow(fact[k], MOD-2, MOD) * pow(fact[n-k], MOD-2, MOD)) % MOD


X, Y = [int(x) for x in input().split(" ")]

n = (2 * X - Y) / 3
m = (2 * Y - X) / 3

if n < 0 or n != int(n):
    print(0)
elif m < 0 or m != int(m):
    print(0)
else:
    n = int(n)
    m = int(m)
    ans = comb(n+m, n)
    print(ans)
from sys import stdin

N,D=[int(x) for x in stdin.readline().rstrip().split()]
data = [stdin.readline().rstrip().split() for _ in range(N)]

ret=0
for i in range(N-1):
    for j in range(i+1,N,1):
        a=[ int(x) for x in data[i]]
        b=[ int(x) for x in data[j]]
        u = np.array(b) - np.array(a)
        if np.linalg.norm(u).is_integer:
            ret+=1
            # print(a,end=" ")
            # print(b)

print(ret,flush=True)

### FIXED CODE ###

import numpy as np
from sys import stdin

N,D=[int(x) for x in stdin.readline().rstrip().split()]
data = [stdin.readline().rstrip().split() for _ in range(N)]

ret=0
for i in range(N-1):
    a=[ int(x) for x in data[i]]
    for j in range(i+1,N,1):
        b=[ int(x) for x in data[j]]
        u = np.array(b) - np.array(a)
        c = np.linalg.norm(u)
        de,inte=np.modf(c)
        if de == 0:
            ret+=1
            # print(a,end=" ")
            # print(b)

print(ret,flush=True)
cat ABC064C.py
l=[0]*13
input()
for i in input().split():;l[int(i)//400]+=1
r=sum([1 for a in l[:8] if a > 0])
print(max(1,r),r+sum(l[8:]))

### FIXED CODE ###

al=[0]*13
input()
for i in input().split():
    al[int(i)//400]+=1
tuyoi=sum(al[8:])
iru=sum([1 for a in al[:8] if a > 0])
print(max(1,iru),iru+tuyoi)
import sys
#import time
from collections import deque, Counter, defaultdict
#from fractions import gcd
import bisect
import heapq
#import math
import itertools
import numpy as np
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
inf = 10**18
MOD = 1000000007
ri = lambda : int(input())
rs = lambda : input().strip()
rl = lambda : list(map(int, input().split()))

s = ri()
dp = [1]*(s+1)
for i in range(3):
    dp[i]=0
#[0,0,1,1,1,2,3,]
for i in range(3,s+1):#3-7
    for j in range(3,i+1):#3-i-1
        if j==i-j:
            dp[i]+=dp[j]*dp[i-j]
        else:
            dp[i]+=dp[j]*dp[i-j]
print(dp[s]%MOD)
        
       

### FIXED CODE ###

import sys
#import time
from collections import deque, Counter, defaultdict
#from fractions import gcd
import bisect
import heapq
#import math
import itertools
import numpy as np
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
inf = 10**18
MOD = 1000000007
ri = lambda : int(input())
rs = lambda : input().strip()
rl = lambda : list(map(int, input().split()))

s = ri()
dp = [1]*max(4,(s+1))
for i in range(3):
    dp[i]=0
dp[3]=1
#[0,0,1,1,1,2,3,]
#a[i] = a[i-3]+...+a[0]
#     = a[i-3]+a[i-1]
for i in range(4,s+1):#3-7
    dp[i] = dp[i-3]+dp[i-1]

print(dp[s]%MOD)
a=int(input())
b,c = map(str,input().split())
s=input()
print({} {}.format(a+b+c,s))

### FIXED CODE ###

s=input()
t=input()
if t[:-1]==s:
  print("Yes")
else:
  print("No")
W, H, x, y = map(int,input().split())
buf_x = W-x
buf_y = H-y
if buf_x >= x:
  ver_area = H*x
else:
  ver_area = H*buf_x
if buf_y >= y:
  hori_area = W*y
else:
  hori_area = W*buf_y

if H/W == y/x:
  print(float(ver_area),1)
else:
  if ver_area <= hori_area:
    print(float(hori_area),0)
  else:
    print(float(ver_area),0)

### FIXED CODE ###

W, H, x, y = map(int,input().split())
buf_x = W-x
buf_y = H-y
if buf_x >= x:
  ver_area = H*x
else:
  ver_area = H*buf_x
if buf_y >= y:
  hori_area = W*y
else:
  hori_area = W*buf_y

if x*2 == W and y*2 ==H:
  print(float(W*H/2),1)
else:
  print(float(W*H/2),0)
r, D, x = map(int, ainput().split())
for i in range(1, 11):
    x = r * x - D
    print(x)


### FIXED CODE ###

r, D, x = map(int, input().split())
for i in range(1, 11):
    x = r * x - D
    print(x)
N,M=map(int,input().split())
S=[list(map(int,input().split())) for _ in range(M)]

ans=''

S_sorted=sorted(S)
#print(S_sorted)

for j in range(M-1):
    if S_sorted[j][0]==S_sorted[j+1][0] and S_sorted[j][1]!=S_sorted[j+1][1]:
        ans='-1'

if ans!='-1':
    if S_sorted[0][0]==1 and S_sorted[0][1]==0:
        if N==1:
            ans=0
        else:
            ans='-1'

R=[1]

if ans!='-1' and ans!=0:
    for _ in range(1,N):
        R.append(0)
    
    for k in range(M):
        R[S_sorted[k][0]-1]=S_sorted[k][1]
    
    for l in range(N):
        ans+=str(R[l])
        int(ans)

#print(R)


print(ans)

### FIXED CODE ###

N,M=map(int,input().split())
S=[list(map(int,input().split())) for _ in range(M)]



if N>=2:
    for i in range(10**(N-1),10**N):
        letter=str(i)
        for j in range(M):
            if letter[S[j][0]-1]!=str(S[j][1]):
                break
        else:
            print(i)
            break
    else:
        print('-1')
else:
    for k in range(0,10):
        letter=str(k)
        for l in range(M):
            if letter[S[l][0]-1]!=str(S[l][1]):
                break
        else:
            print(k)
            break
    else:
        print('-1')
input = sys.stdin.readline


class SegmentTree:
    # 初期化処理
    # f : SegmentTreeにのせるモノイド
    # default : fに対する単位元
    def __init__(self, size, f=lambda x, y: x+y, default=0):
        self.size = 2**(size-1).bit_length()  # 簡単のため要素数Nを2冪にする
        self.default = default
        self.dat = [default]*(self.size*2)  # 要素を単位元で初期化
        self.f = f

    def update(self, i, x):
        i += self.size
        self.dat[i] = x
        while i > 0:
            i >>= 1
            self.dat[i] = self.f(self.dat[i*2], self.dat[i*2+1])

    def query(self, l, r):
        l += self.size
        r += self.size
        lres, rres = self.default, self.default
        while l < r:
            if l & 1:
                lres = self.f(lres, self.dat[l])
                l += 1

            if r & 1:
                r -= 1
                # モノイドでは可換律は保証されていないので演算の方向に注意
                rres = self.f(self.dat[r], rres)
            l >>= 1
            r >>= 1
        res = self.f(lres, rres)
        return res


def acinput():
    return list(map(int, input()[:-1].split(" ")))


N, K = acinput()

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

st = SegmentTree(N+10, f=max)

res = 0
for sa in A:
    L = max(sa-K, 0)
    R = min(sa+K, N+2)

    tmp = st.query(L, R+1)+1
    st.update(sa, tmp)
    res = max(tmp, res)

print(res)


### FIXED CODE ###



class SegmentTree:
    # 初期化処理
    # f : SegmentTreeにのせるモノイド
    # default : fに対する単位元
    def __init__(self, size, f=lambda x, y: x+y, default=0):
        self.size = 2**(size-1).bit_length()  # 簡単のため要素数Nを2冪にする
        self.default = default
        self.dat = [default]*(self.size*2)  # 要素を単位元で初期化
        self.f = f

    def update(self, i, x):
        i += self.size
        self.dat[i] = x
        while i > 0:
            i >>= 1
            self.dat[i] = self.f(self.dat[i*2], self.dat[i*2+1])

    def query(self, l, r):
        l += self.size
        r += self.size
        lres, rres = self.default, self.default
        while l < r:
            if l & 1:
                lres = self.f(lres, self.dat[l])
                l += 1

            if r & 1:
                r -= 1
                # モノイドでは可換律は保証されていないので演算の方向に注意
                rres = self.f(self.dat[r], rres)
            l >>= 1
            r >>= 1
        res = self.f(lres, rres)
        return res


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

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

st = SegmentTree(300000+10, f=max)

res = 0
for sa in A:
    L = max(sa-K, 0)
    R = min(sa+K, 300001)

    tmp = st.query(L, R+1)+1
    st.update(sa, tmp)
    res = max(tmp, res)

print(res)
c_11, c_12, c_13 = [int(a) for a in input().split()]
c_21, c_22, c_23 = [int(b) for b in input().split()]
c_31, c_32, c_33 = [int(c) for c in input().split()]
print(str(c_11) + str(c_22) + str(c_33))

### FIXED CODE ###

c_1 = input()
c_2 = input()
c_3 = input()
print(c_1[0] + c_2[1] + c_3[2])
import numpy as np


def DP(i, X, w, v):
    global memo
    if (X < 0):
        return -10 ** 9
#    if (memo[i, X] != -10 ** 9):
#        return memo[i, X]
#       print('you used memo!')
    result = max(DP(i + 1, X, w, v),
                 DP(i + 1, X - w[i], w, v) + v[i])
    memo[i, X] = result
    return result


N, W = map(int, input().split())
w = [0] * N
v = [0] * N
for i in range(N):
    w[i], v[i] = map(int, input().split())
MINUS_INF = -10 ** 9
memo = np.full((N + 1, W + 1), MINUS_INF, dtype=np.int64)
memo[N, :] = 0
answer = DP(0, W, w, v)
print(answer)


### FIXED CODE ###

import numpy as np
import sys


def main():
    input = sys.stdin.readline
    n, W = map(int, input().split())
    w, v = [0] * n, [0] * n
    for i in range(n):
        w[i], v[i] = map(int, input().split())
    ndp = np.zeros(W + 1, dtype=np.int64)
    for w, v in zip(w, v):
        np.maximum(ndp[:-w] + v, ndp[w:], out=ndp[w:])
    print(ndp[-1])


if __name__ == "__main__":
    main()
N,W=map(int,input().split())
Wlist=[]
Vlist=[]
for i in range(N):
  w,v=map(int,input().split())
  Wlist+=[w]
  Vlist+=[v]
dp=[[0 for p in range(V+1)] for i in range(N)]
for i in range(V+1):
  if i<=Vlist[0]:
    dp[0][i]=Wlist[0]
for i in range(1,N):
  vi=Vlist[i]
  for j in range(V+1):
    if j-vi>=0:
      dp[i][j]=min(dp[i-1][j-vi]+Wlist[i],dp[i-1][j])
    else:
      dp[i][j]=min(dp[i-1][j],dp[i][j])
dpn=dp[N-1]
ans=0
for i in range(V+1):
  if dpn[i]<=W:
    ans=i
print(ans)

### FIXED CODE ###

def main():
  N,W=map(int,input().split())
  Wlist=[]
  Vlist=[]
  for i in range(N):
    w,v=map(int,input().split())
    Wlist+=[w]
    Vlist+=[v]
  Vmax=max(Vlist)
  V=Vmax*N
  dp=[[float('inf') for p in range(V+1)] for i in range(N)]
  for i in range(V+1):
    if i<=Vlist[0]:
      dp[0][i]=Wlist[0]
  dp[0][0]=0
  for i in range(1,N):
    vi=Vlist[i]
    wi=Wlist[i]
    for j in range(V+1):
      if j-vi>=0:
        dp[i][j]=min(dp[i-1][j-vi]+wi,dp[i-1][j])
      else:
        dp[i][j]=min(dp[i-1][j],dp[i][j])
  dpn=dp[N-1]
  ans=0
  for i in range(V+1):
    if dpn[i]<=W:
      ans=i
  print(ans)
if __name__ == '__main__':
  main()
# coding: utf-8
# Your code here!
from collections import deque
import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline #文字列入力のときは注意

n,m = [int(i) for i in readline().split()]

if m%2: print(-1); exit()

L = [0]*n

g = [set() for _ in range(n)]
for i in range(m):
    a,b = [int(i) for i in readline().split()]
    g[a-1].add(b-1)
    g[b-1].add(a-1)
    L[a-1] += 1
    L[b-1] += 1


used = [0]*m
def dfs(v):
    res = 0
    for (c,i) in g[v]:
#        if used[i] == 1: continue
        g[v-1].remove(c-1)
        g[c-1].remove(v-1)
        p =  dfs(c)
        if p%2 == 1:
            print(v+1,c+1)
        else:    
            print(c+1,v+1)
        res += p
    return res+1


for i in range(n):
    dfs(i)
#print(q)












### FIXED CODE ###

# coding: utf-8
# Your code here!
from collections import deque
import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline #文字列入力のときは注意

n,m = [int(i) for i in readline().split()]

if m%2: print(-1); exit()

#L = [0]*n

g = [[] for _ in range(n)]
for i in range(m):
    a,b = [int(i) for i in readline().split()]
    g[a-1].append((b-1,i))
    g[b-1].append((a-1,i))
#    L[a-1] += 1
#    L[b-1] += 1



used = [0]*m
usedp = [0]*n
def dfs(v):
    res = 0
    for (c,i) in g[v]:
        if used[i] == 1: continue
        used[i] = 1
        if usedp[c] == 1:
            res += 1
            print(v+1,c+1)
            continue
        usedp[c] = 1
        p =  dfs(c)
        if p%2 == 1:
            print(v+1,c+1)
        else:    
            print(c+1,v+1)
        res += p
    return res+1


for i in range(n):
    dfs(i)
#print(q)
import math
a, b, c, d = map(int, input().split())

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

def main():
    left = (b -int(b/c) -int(b/d) +int(b/lcm(c,d)))
    right = ((a-1) -int((a-1)/c) -int((a-1)/d) +int((a-1)/lcm(c,d)))
    print(left - right)
main()

### FIXED CODE ###

from fractions import gcd

A, B, C, D = map(int, input().split())
l = C * D // gcd(C, D)
x = (A - 1) - (A - 1) // C - (A - 1) // D + (A - 1) // l
y = B - B // C - B // D + B // l
print(y - x)