Harryxun/stf_run huggingface dataset:
a, b, k = map(int, input().split())

s = []

for i in range(1, max(a, b)):
    if a % i == 0 and b % i == 0:
        s.append(i)

sorted(s)

s = s[::-1]

print(s[k-1])


### FIXED CODE ###

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

s = []

for i in range(1, max(a, b)+1):
    if a % i == 0 and b % i == 0:
        s.append(i)

sorted(s)

s = s[::-1]

print(s[k-1])
N = int(input())
for n in range(1, 3501):
    for w in range(i, 3501):
        t = N*n*w % (4*n*w - N*w - N*w)
        if t == 0:
            print(t, i, j)
            exit()


### FIXED CODE ###

N = int(input())
for n in range(1, 3501):
    for w in range(n, 3501):

        try:
            t = (N*n*w) % (4*n*w - N*w - N*n)
        except:
            continue

        if t == 0 and 4*n*w - N*w - N*n>=0:
            print((N*n*w) // (4*n*w - N*w - N*n), n, w)
            exit()
s = input()
k = int(input())
n = 0
j = s[0]
l = 1
p = 0
for i in range(1,len(s)):
  if s[i] == j:
    l += 1
  else:
    n += l//2
    l = 1
    j = s[i]
n += l//2
if s[0] == s[-1] and s[0] != s[1] and s[0] != s[-2]:
  p = k-1
print(n*k+p)

### FIXED CODE ###

s = input()
k = int(input())
n = 0
j = s[0]
l = 1
p = 0
fi,la = 0,0
c = 1
if len(set(list(s))) == 1:
  print(len(s)*k//2)
else:
  for i in range(1,len(s)):
    if s[i] == j:
      l += 1
    else:
      n += l//2
      if s[i-1] == s[0] and c == 1:
        fi = l
        c = 0
      l = 1
      j = s[i]
  n += l//2
  la = l
  if s[0] == s[-1] and fi%2 == 1 and la%2 == 1:
    p = k-1
  print(n*k+p)
k = int(input())
s = input()
if len(s) =< k:
    print(s)
else:
    s1 = s[0:k]
    s1 = s1 + '...'
    print(s1)

### FIXED CODE ###

k = int(input())
s = input()
if len(s) <= k:
    print(s)
else:
    s1 = s[0:k]
    s1 = s1 + '...'
    print(s1)
import math
a = list(map(int, input().split()))
print(int(a[0]*a[1]/math.gcd(a[0],a[1])))

### FIXED CODE ###

#n = int(input())
#L = list(map(int, input().split()))
import math
import sys
import fractions
a = list(map(int, input().split()))

print(a[0]*a[1]//fractions.gcd(a[0], a[1]))
import numpy as np
N,K=map(int,input().split())
A=list(map(int,input().split()))
A=sorted(A)
#B=list(reversed(A))
A=np.array(A)
Aneg=A[A<0]
Azero=A[A==0]
Apos=A[A>0]

n_neg=len(Aneg)*len(Apos)
n_zero=len(Azero)*(len(Azero)-1)//2+len(Azero)*(len(Aneg)+len(Apos))
n_pos=(len(Apos)*(len(Apos)-1)+len(Aneg)*(len(Aneg)-1))//2

if K <=n_neg:
    n=K-n_neg
    B=sorted(Aneg)[:n+1]
    C=sorted(Apos)[:n+1]
    ans=[]
    for i in range(min(len(B),n-1)):
        for j in range(min(len(C),n-1)):
            ans.append(B[i]*C[j])
    ans=sorted(ans)
    print(ans[n-1])
    
elif K>n_neg+n_zero:
    n=K-(n_neg+n_zero)
    B=sorted(Aneg)
    B=list(reversed(B))
    C=sorted(Apos)
    ans=[]
    if len(B)>2:
        for i in range(len(B)-1):
            for j in range(i+1,len(B)):
                ans.append(B[i]*B[j])
    if len(C)>2:
#         k=min(len(C),n-1)
        for i in range(len(C)-1):
            for j in range(i+1,len(C)):
                ans.append(C[i]*C[j])
    ans=sorted(ans)
    print(ans[n-1])
    
else:
    print(0)

### FIXED CODE ###

import numpy as np
N,K=map(int,input().split())
A=list(map(int,input().split()))

A=np.array(A)

A_pos=np.sort(A[A>0])
A_neg=np.sort(A[A<0])
A_neg2=-A_neg[::-1]
n_pos=len(A_pos)
n_neg=len(A_neg)
n_zero=N-n_pos-n_neg

def position_in_neg(x):
    y=n_pos-np.searchsorted(A_pos,x//A_neg,side='right')
    return y.sum()

def position_in_pos(x):
    z=np.searchsorted(A_pos,-(-x//A_pos),side='left')
    w=np.searchsorted(A_neg2,-(-x//A_neg2),side='left')
    tmp=len(A_pos[A_pos**2<x])+len(A_neg2[A_neg2**2<x])
    return (z.sum()+w.sum()-tmp)//2

def position(x):
    if x<0:
        return position_in_neg(x)
    elif x==0:
        return n_pos*n_neg
    else:
        return position_in_pos(x)+n_pos*n_neg+(n_pos+n_neg)*n_zero+n_zero*(n_zero-1)//2

l=-pow(10,18)
r=pow(10,18)
while(r-l>1):
    mid=(l+r)//2
    if position(mid)<K:
        l=mid
    else:
        r=mid
print(l)
import sys

sys.setrecursionlimit(10**7)
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり
def LI2(): return list(map(int,sys.stdin.readline().rstrip()))  #空白なし
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())  #空白あり
def LS2(): return list(sys.stdin.readline().rstrip())  #空白なし

K = I()
if K % 2 == 0:
    print(-1)
    exit()
if K % 7 == 0:
    K //= 7

A = [1]
for i in range(K):
    A.append((A[-1]*10) % K)

a = 1
i = 1
while True:
    if a % K == 0:
        print(i)
        break
    else:
        a += A[i]
        a %= K
        i += 1


### FIXED CODE ###

import sys

sys.setrecursionlimit(10**7)
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり
def LI2(): return list(map(int,sys.stdin.readline().rstrip()))  #空白なし
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())  #空白あり
def LS2(): return list(sys.stdin.readline().rstrip())  #空白なし

K = I()
if K % 2 == 0 or K % 5 == 0:
    print(-1)
    exit()
if K % 7 == 0:
    K //= 7

A = [1]
for i in range(K+2):
    A.append((A[-1]*10) % K)

a = 1
i = 1
while True:
    if a % K == 0:
        print(i)
        break
    else:
        a += A[i]
        a %= K
        i += 1
import numpy as np

def getBoundary(p, k, k2):
    if p - k + 1 >= 0:
        return [(p - k + 1, p + 1)]
    else:
        return [(0, p + 1), ((p - k + 1) % k2, k2)]

n, k = map(int, input().strip().split())
k2 = k * 2
b = [[0 for i in range(k2 + 1)] for j in range(k2 + 1)]

for i in range(n):
    x_str, y_str, c_str = input().strip().split()
    x = int(x_str) % k2
    y = (int(y_str) + (c_str == 'B') * k) % k2
    for xb, xe in getBoundary(x % k2, k, k2):
        for yb, ye in getBoundary(y % k2, k, k2):
            b[xb][yb] += 1
            b[xb][ye] -= 1
            b[xe][yb] -= 1
            b[xe][ye] += 1
    for xb, xe in getBoundary((x + k) % k2, k, k2):
        for yb, ye in getBoundary((y + k) % k2, k, k2):
            b[xb][yb] += 1
            b[xb][ye] -= 1
            b[xe][yb] -= 1
            b[xe][ye] += 1

arr_b = np.array(b)
for i in range(k2):
    arr_b[i + 1] += arr_b[i]
for j in range(k2):
    arr_b[:, j + 1] += arr_b[:, j]
print(arr_b.max())


### FIXED CODE ###

ab = [int(x) for x in raw_input().strip().split()]

c = (ab[0] * ab[1]) % 2
if c == 1:
    print 'Odd'
else:
    print 'Even'
def solve():
    a, b, c, d = map(int, input().split())
    a -= 1
    b -= 1
    c -= 1
    d -= 1
    if a > c:
        a, b, c, d = c, d, a, b
    for k in range(30, -1, -1):
        if a // 3 ** k == c // 3 ** k and a // 3 ** k % 3 == 1 \
                and min(b, d) // 3 ** k % 3 == 0 and max(b, d) // 3 ** k % 3 == 2:
            print(min(a % 3 ** k + 1 + c % 3 ** k + 1 + abs(b - d),
                3 ** k - a % 3 ** k + 3 ** k - c % 3 ** k + abs(b - d)))
            return
        if b // 3 ** k == d // 3 ** k and b // 3 ** k % 3 == 1:
                and min(a, c) // 3 ** k % 3 == 0 and max(a, c) // 3 ** k % 3 == 2:
            print(min(b % 3 ** k + 1 + d % 3 ** k + 1 + abs(a - c),
                3 ** k - b % 3 ** k + 3 ** k - d % 3 ** k + abs(a - c)))
            return
    print(abs(a - c) + abs(b - d))

q = int(input())
for _ in range(q):
    solve()

### FIXED CODE ###

def solve():
    a, b, c, d = map(int, input().split())
    a -= 1
    b -= 1
    c -= 1
    d -= 1
    if a > c:
        a, b, c, d = c, d, a, b
    for k in range(30, -1, -1):
        def check(a, b, c, d):
            if a // 3 ** k == c // 3 ** k and a // 3 ** k % 3 == 1 \
                    and (min(b, d) // 3 ** k % 3 == 0 and max(b, d) // 3 ** k % 3 == 2
                            or max(b, d) // 3 ** k - min(b, d) // 3 ** k >= 3):
                print(min(a % 3 ** k + 1 + c % 3 ** k + 1 + abs(b - d),
                    3 ** k - a % 3 ** k + 3 ** k - c % 3 ** k + abs(b - d)))
                return True
        if check(a, b, c, d) or check(b, a, d, c):
            return
    print(abs(a - c) + abs(b - d))

q = int(input())
for _ in range(q):
    solve()
x = int(input())
y = !x
print(y)

### FIXED CODE ###

x = int(input())
print(1-x)
X,Y = map(int,input().split())

dp =[[0]*(X+1) for i in range(Y+1)]
dp[0][0] = 1
mod = 10**9 +7
for x in range(X+1):
    for y in range(Y+1):
        if (x>1 and y>0) or (x>0 and y>1):

            dp[x][y] = (dp[x-1][y-2]+dp[x-2][y-1])%mod

print(dp[X][Y])

### FIXED CODE ###

X, Y = map(int,input().split())

total = (X+Y)/3
k = (2*X-Y)//3

if (total == int(total)) and (k>=0):
    total = (X+Y)//3

    mod = 10 ** 9 + 7

    modinv_table = [-1] * (k + 1)
    for i in range(1, k + 1):
        modinv_table[i] = pow(i, -1, mod)


    def binomial_coefficients(n, k):
        ans = 1
        for i in range(k):
            ans *= n - i
            ans *= modinv_table[i + 1]
            ans %= mod
        return ans

    print(binomial_coefficients(total,k))
else:
    print(0)
x = int(input())

# エラトステネスの篩
def Eratosthenes(n):
    if n < 2:
        return None
    prime = [2]
    limit = math.ceil(n**0.5)
    data = list(range(3, n+1, 2))
    p = -1
    while p < limit:
        p = data[0]
        prime.append(p)
        data = [d for d in data if d%p != 0]
    return prime + data


prime = Eratosthenes(10**5+3)
if x in prime:
    print(x)
else:
    import bisect
    min_prime_index = bisect.bisect_right(prime, x)
    print(prime[min_prime_index])

### FIXED CODE ###

import math

x = int(input())

# エラトステネスの篩
def Eratosthenes(n):
    if n < 2:
        return None
    prime = [2]
    limit = math.ceil(n**0.5)
    data = list(range(3, n+1, 2))
    p = -1
    while p < limit:
        p = data[0]
        prime.append(p)
        data = [d for d in data if d%p != 0]
    return prime + data


prime = Eratosthenes(10**5+3)
if x in prime:
    print(x)
else:
    import bisect
    min_prime_index = bisect.bisect_right(prime, x)
    print(prime[min_prime_index])
def get_ints():
    return map(int, input().split())

n, m = get_ints()
penalty = 0
oks = 0
ac = []
for i in range(n):
    ac.append(False)
for i in range(m):
    p, s = input().split()
    p = int(p)
    p -= 1
    if ac[p]:
        continue
    if s == 'AC':
        ac[p] = True
        oks += 1
    else:
        penalty += 1

print(f'{oks} {penalty}')


### FIXED CODE ###

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

n, m = get_ints()
penalty = 0
oks = 0
ac = []
penalty = []
for i in range(n):
    ac.append(False)
    penalty.append(0)
for i in range(m):
    p, s = input().split()
    p = int(p)
    p -= 1
    if ac[p]:
        continue
    if s == 'AC':
        ac[p] = True
        oks += 1
    else:
        penalty[p] += 1

ans = 0
for i in range(n):
    if ac[i]:
        ans += penalty[i]

print(str(oks) + ' ' + str(ans))
import fraction
N, M = (int(i) for i in input().split())  
S = input()
T = input()

L = fraction.gcd(N, M)
lcm = (N * M) // L

flag = True
for i in range(L):
    if (S[N//L * i] != T[M//L * i]):
        flag = False

if flag:
    print(lcm)
else:
    print("-1")


### FIXED CODE ###

import fractions

N, M = (int(i) for i in input().split())  
S = input()
T = input()

L = fractions.gcd(N, M)
lcm = (N * M) // fractions.gcd(N, M)

flag = True
for i in range(L):
    if (S[N//L * i] != T[M//L * i]):
        flag = False

if flag:
    print(lcm)
else:
    print("-1")
S = list(input())
i = 0
cnt = 0

while True:
    if i == len(S) - 2:
        break
    if S[i] != S[i+1]:
        cnt += 2
        S.pop(i)
        S.pop(i)
        if i > 0:
            i -= 1
    else:
        i += 1
print(cnt)
    

### FIXED CODE ###

import sys

S = list(input())
i = 0
cnt = 0

if len(S) == 1:
    print(0)
    sys.exit()

while True:
    if i == len(S) - 2:
        if S[i] != S[i+1]:
            cnt += 2
        break
    if S[i] != S[i+1]:
        cnt += 2
        S.pop(i)
        S.pop(i)
        if i > 0:
            i -= 1
    else:
        i += 1
print(cnt)
def dfs(u):
    for v in G[u]:
        if dist[v] > dist[u] + 1:
            dist[v] = dist[u] + 1
            dfs(v)

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

G = [[] for _ in range(3*N)]
for _ in range(M):
    u, v = map(int,input().split())
    u, v = u-1, v-1

    G[u].append(v+N)
    G[u+N].append(v+2*N)
    G[u+2*N].append(v)

s, t = map(int,input().split())
s, t = s-1, t-1

dist = [10**9] * (3*N)
dist[s] = 0

dfs(s)

if dist[t] == 10**9:
    print(-1)
else: 
    print(dist[t] // 3)



### FIXED CODE ###

from collections import deque
INF = 10**9

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

G = [[] for _ in range(3*N)]
for _ in range(M):
    u, v = map(int,input().split())
    u, v = u-1, v-1

    G[u].append(v+N)
    G[u+N].append(v+2*N)
    G[u+2*N].append(v)

s, t = map(int,input().split())
s, t = s-1, t-1

dist = [INF] * (3*N)
dist[s] = 0

Q = deque([s])
while len(Q) > 0:
    u = Q.popleft()
    for v in G[u]:
        if dist[v] == INF:
            dist[v] = dist[u] + 1
            Q.append(v)

if dist[t] == INF:
    print(-1)
else: 
    print(dist[t] // 3)
import sys
sys.setrecursionlimit(10**6)
n,m = map(int,input().split())
e = [[] for i in range(n+1)]
for i in range(m):
    a,b = map(int,input().split())
    e[a].append(b)
    e[b].append(a)
qv = int(input())
Q = [list(map(int,input().split())) for i in range(qv)]
Q = Q[::-1]
l = [[0]*(11) for i in range(n+1)]
for v,d,c in Q:
    if l[v][d] > 0:
        continue
    l[v][d] = c
dic = {}
color = [0]*(n+1)

left = [i for i in range(1,n+1)]
num = 0
while num < qv and left:
    v,d,c = Q[num]
    if v not in dic:
        for i in range(10,0,-1):
            if l[v][i] > 0:
                M = i
                break
        dic[v] = [set() for i in range(n+1)]
        s = set()
        s.add(v)
        dist = [float("INF")]*(n+1)
        dist[v] = 0
        q = [v]
        for i in range(1,m+1):
            nq = []
            for now in q:
                for nex in e[now]:
                    if dist[nex]<= i:
                        continue
                    nq.append(nex)
                    dist[nex] = i
                    s.add(nex)
            dic[v][i] |= s
            q = nq
    nl = []
    
    for i in left:
        if i in dic[v][d]:
            color[i] = c
        else:
            nl.append(i) 
    num += 1
    
    left = nl
    
for i in color[1:]:
    print(i)

### FIXED CODE ###

from collections import deque
import sys
sys.setrecursionlimit(10**6)
n,m = map(int,input().split())
e = [[] for i in range(n+1)]
for i in range(m):
    a,b = map(int,input().split())
    e[a].append(b)
    e[b].append(a)
qv = int(input())
Q = [list(map(int,input().split())) for i in range(qv)]

color = [0]*(n+1)
used = [-1]*(n+1)

for v,d,c in Q[::-1]:
    if used[v] > d:
        continue
    
    q = deque([[v,d]])
    while q:
        now, dis = q.popleft()
        if dis < 0:
            continue
        if color[now] == 0:
            color[now] = c
        for nex in e[now]:
            if used[nex] < dis-1:
                used[nex] = dis-1
                q.append([nex,dis-1])
    
for i in color[1:]:
    print(i)
x =int(input())

y=x//2

if (y%2==0):
    print (y**2)
elif print ((y**2)+1)

### FIXED CODE ###

k = int(input())
x = [i for i in range(1, k+1) if i & 1 == 0]
y = [i for i in range(1, k+1) if i & 1 == 1]
print(len(x)*len(y))
import sys
import math
import itertools
import bisect
from copy import copy,deepcopy
from collections import deque,Counter
from decimal import Decimal
def s(): return input()
def i(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def L(): return list(map(int,input().split()))
def l(): return list(map(int,input().split()))
def lcm(a,b): return a*b//math.gcd(a,b)
sys.setrecursionlimit(10 ** 9)
INF = 10**9
mod = 10**9+7

N,M = I()
keta = [-1]*(N)
for i in range(M):
    s,c = I()
    if keta[s-1] == -1 or keta[s-1] == c:
        keta[s-1] = c
    else:
        print(-1)
        exit()
if keta[i] == -1:
    keta[i] = 1
for i in range(N):
    if keta[i] == -1:
        keta[i] = '0'
    else:
        keta[i] = str(keta[i])
if ''.join(keta) != str(int(''.join(keta))):
    print(-1)
else:
    print(''.join(keta))

### FIXED CODE ###

N,M = list(map(int,input().split()))
A = ['a']*N
for i in range(M):
  s,c = list(map(int,input().split()))
  if A[s-1] != 'a' and A[s-1] != str(c):
    print('-1')
    exit()
  else:
    A[s-1] = str(c)
if A[0] == '0' and len(A) != 1:
  print('-1')
  exit()
elif A[0] == 'a' and len(A) != 1:
  A[0] = '1'
for i in range(N):
      if A[i] == 'a':
        A[i] = '0'
print(''.join(A))
N=int(input())
for n in range(1,N+1):
    ans = 0
    for i in range(1,int((n**0.5)):
        for j in range(i,int((n**0.5)):
            for k in range(j,int((n**0.5)):
                if i**2+j**2+k**2+i*j+j*k+k*i==n:
                    if i == j and j == k:
                        ans += 1
                    else:
                        ans += 3

    print(ans)


### FIXED CODE ###

N=int(input())
ans = [0]*10000000
for i in range(1,100):
    for j in range(1,100):
        for k in range(1,100):
            ans[i**2+j**2+k**2+i*j+j*k+i*k] += 1
for i in range(1,N+1):
    print(ans[i])
# coding: utf-8
from functools import lru_cache
import sys
input = sys.stdin.readline
sys.setrecursionlimit(100000)

@lru_cache(maxsize = None)
def f(v):
    if len(arc[v]) == 0:
        return(0)
    return(max(f(nv) for nv in arc[v]) + 1)

n, m = map(int, input().split()) # 2 <= n <= 10^5, 1 <= m <= 10^5
arc = [[] for _ in range(n + 1)]
for i in range(m):
    x, y = map(int, input().split())
    arc[x].append(y)
print(max(f(v + 1) for v in range(n)))


### FIXED CODE ###

# coding: utf-8
from functools import lru_cache

import sys
input = sys.stdin.readline
sys.setrecursionlimit(1000000)

@lru_cache(maxsize = None)
def f(v):
    if not arc[v]:
        return(0)
    return(max(f(nv) for nv in arc[v]) + 1)

n, m = map(int, input().split()) # 2 <= n <= 10^5, 1 <= m <= 10^5
arc = [[] for _ in range(n)]
for _ in range(m):
    x, y = map(int, input().split())
    arc[x - 1].append(y - 1)
print(max(f(v) for v in range(n)))
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repi(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
using namespace std;
typedef long long ll;

int N, M;
ll K;
vector<ll> A;
vector<ll> B;

bool is_ok(vector<ll> B, int cnt_a, int mid){
  return A[cnt_a] + B[mid] <= K;
}

int binary_search(vector<ll> B, int cnt_a) {
    int left = -1; // 配列の左端
    int right = B.size(); // 配列の右端
    // 両端の差が1になるまで続ける
    while (right - left > 1){
        int mid = (right + left) / 2; // 区間の真ん中
        if (is_ok(B, cnt_a, mid)) left = mid;  // もし調べている対象が「is_okの条件」に当てはまればleftをmidまで移動
        else right = mid;  // 当てはまらなければrightをmid-1に移動
    }
    return left;
}

int main(){
  cin >> N >> M >> K;
  // 0インデックスには何も読まない0という初期値をそのまま入れておく
  A.push_back(0);
  B.push_back(0);

  rep(i, N){
    ll a;
    cin >> a;
    A.push_back(a);
  }
  rep(i, M){
    ll b;
    cin >> b;
    B.push_back(b);
  }

  rep(i, N) A[i+1] += A[i];
  rep(i, M) B[i+1] += B[i];

  int ans = 0;
  int cnt_b;
  rep(cnt_a, N+1){
    if (A[cnt_a] > K) continue;
    cnt_b = binary_search(B, cnt_a);
    ans = max(ans, cnt_a + cnt_b);
  }
  cout << ans << endl;
}

### FIXED CODE ###

from itertools import accumulate

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

a_acc = [0] + list(accumulate(a))  # aを0冊読む=1冊も読まない場合があるので
b_acc = [0] + list(accumulate(b))  # 今度は[0]が必要です

ans = 0
for an in range(n + 1):
    rem = k - a_acc[an]
    if rem < 0:
        break

    # 最初は 0 <= x < m + 1 の範囲で、この範囲を狭めていきます
    ok = 0
    ng = m + 1   
    # ng = ok + 1のとき、ok <= x < ng は ok <= x < ok + 1で、x = okに確定します
    while abs(ng - ok) > 1:
        mid = (ok + ng) // 2
        # bをmid冊読めるか？
        if b_acc[mid] <= rem:
        # 読めるならok
            ok = mid
        else:
        # 読めないならng
            ng = mid

    bn = ok
    ans = max(ans, an + bn)

print(ans)
#ABC131 C
import math

A, B, C, D = map(int, input().split())
def ad(X):
    XmodC = X // C
    XmodD = X // D
    CD_lcm = C * D / math.gcd(C, D)
    XmodCD = X // CD_lcm
    return X - int(XmodC + XmodD - XmodCD)
print(ad(B) - ad(A - 1))

### FIXED CODE ###

#ABC131 C
import fractions

A, B, C, D = map(int, input().split())
def ad(X):
    XmodC = int(X // C)
    XmodD = int(X // D)
    CD_lcm = int(C * D / fractions.gcd(C, D))
    XmodCD = int(X // CD_lcm)
    return X - (XmodC + XmodD - XmodCD)
ans = ad(B) - ad(A - 1)
print(ans)
n = int(input())
w = input().split()
s1 = w[0]
s2 = w[n-1]
for i in range(1, n-2):
    if s1 < s2:
        s1 += w[i]
    else:
        s2 += w[-i-1]
print(abs(s1 - s2))


### FIXED CODE ###

n = int(input())
w = list(map(int, input().split()))
ans = float('inf')
for i in range(n):
    s1 = sum(w[:i])
    s2 = sum(w[i:])
    z = abs(s1 - s2)
    ans = min(ans, z)
print(ans)
from code import InteractiveConsole as C

n = int(C.raw_input())
q = []
bottom = 0
for i in range(n):
    cmd = C.raw_input()
    if cmd[0] == 'i':
        q.append(cmd[7:])
    elif cmd[6] == ' ':
        try:
            q.pop(~q[::-1].index(cmd[7:]))
        except:
            pass
    elif cmd[6] == 'F':
        q.pop()
    else:
        bottom += 1

print(' '.join(q[bottom:][::-1]))

### FIXED CODE ###

import sys
from collections import deque

n = int(sys.stdin.readline())
q = deque()
for i in range(n):
    cmd = sys.stdin.readline()[:-1]
    if cmd[0] == 'i':
        q.appendleft(cmd[7:])
    elif cmd[6] == ' ':
        try:
            q.remove(cmd[7:])
        except:
            pass
    elif cmd[6] == 'F':
        q.popleft()
    else:
        q.pop()

print(' '.join(q))
from collections import deque

n = int(input())

distance = [-1] * n

length = [[0] * n for _ in range(n)]
edge = [[] for _ in range(n)]


for _ in range(n-1):
    u, v, w = map(int, input().split())
    u, v = u-1, v-1
    edge[u].append(v)
    edge[v].append(u)
    length[u][v] = w
    length[v][u] = w

D = deque([0])
distance[0] = 0

while D:
    now = D.popleft()
    for i in edge[now]:
        if distance[i] == -1:
            distance[i] = (distance[now] + length[now][i]) % 2
            D.append(i)

for i in distance:
    print(i)

### FIXED CODE ###

from collections import deque

n = int(input())

distance = [-1] * n

edge = [dict() for _ in range(n)]

for _ in range(n-1):
    u, v, w = map(int, input().split())
    u, v = u-1, v-1
    edge[u][v] = w
    edge[v][u] = w

D = deque([0])
distance[0] = 0

while D:
    now = D.popleft()
    for i in edge[now]:
        if distance[i] == -1:
            distance[i] = (distance[now] + edge[now][i]) % 2
            D.append(i)

for i in distance:
    print(i)
import fractions

a,b,c,d=map(int,input().split())

gcd = int(fractions.gcd(c,d))

cc = (c//gcd * d)


mm1 = b//c
mm2 = b//d
mmc = b//cc
A1 = b - (mm2 + mm1 - mmc)
# print(A1, b, mm2, mm1, mmc)

a-=1
mm1 = a//c
mm2 = a//d
mmc = a//cc
A2 = a - (mm2 + mm1 - mmc)
# print(A2, a, mm2, mm1, mmc)


print(A1 - A2)
~

### FIXED CODE ###

import math

a,b,c,d=map(int,input().split())

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

gcd_ = int(gcd(c,d))

cc = (c//gcd_ * d)


mm1 = b//c
mm2 = b//d
mmc = b//cc
A1 = b - (mm2 + mm1 - mmc)
# print(A1, b, mm2, mm1, mmc)

a-=1
mm1 = a//c
mm2 = a//d
mmc = a//cc
A2 = a - (mm2 + mm1 - mmc)
# print(A2, a, mm2, mm1, mmc)


print(A1 - A2)
s = list(map(int, input().split()))
n=s[0]
w=s[1]
dp=[[0]*(w+1) for i in range(n+1)]
weight=[]
value=[]
for i in range(n):
    s = list(map(int, input().split()))
    weight.append(s[0])
    value.append(s[1])

for i in range(n):
    for j in range(w+1):
        if weight[i]<=w and weight[i]<=j:
            dp[i+1][j]=max(dp[i][j-weight[i]]+value[i],dp[i][j])
        else:
            dp[i+1][j]=dp[i][j]
print(dp[3][8])

### FIXED CODE ###

import numpy as np

n,W=list(map(int,input().split()))

dp=np.zeros([n+1,W+1],dtype=int)

for i in range(1,n+1):
    w,v=list(map(int,input().split()))
    dp[i]=dp[i-1]
    dp[i][w:]=np.maximum(dp[i-1][:W-w+1]+v,dp[i-1][w:])
print(np.max(dp))