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

n,m,k=map(int,input().split())
a=[int(x) for x in input().split()]
b=[int(x) for x in input().split()]

c=[0]
for i in range(n):
  if c[i]+a[i]<=k:
    c.append(c[i]+a[i])
  else:
    break

d=[0]
for i in range(m):
  if d[i]+b[i]<=k:
    d.append(d[i]+b[i])
  else:
    break

e=0
f=len(d)-1
for i in range(len(c)):
  for j in range(f,-1,-1):
    if c[i]+d[j]<=k and i+j>e:
      e=i+j
      f=j
      break
print(e)

### FIXED CODE ###

n,m,k=map(int,input().split())
a=[int(x) for x in input().split()]
b=[int(x) for x in input().split()]

c=[0]
for i in range(n):
  if c[i]+a[i]<=k:
    c.append(c[i]+a[i])
  else:
    break

d=[0]
for i in range(m):
  if d[i]+b[i]<=k:
    d.append(d[i]+b[i])
  else:
    break

e=0
f=len(d)-1
for i in range(len(c)):
  for j in range(f,-1,-1):
    if c[i]+d[j]<=k:
      if i+j>e:
        e=i+j
      f=j
      break
print(e)
### BUGGY CODE ###

k, s = input().split()
k, s = int(k), int(s)
ans = 0
for i1 in range(k+1):
  for i2 in range(k+1):
    for i3 in range(k+1):
      if i1 + i2 + i3 == s:
        ans += 1
print(ans)

### FIXED CODE ###

k, s = input().split()
k, s = int(k), int(s)
ans = 0
for i1 in range(k+1):
  for i2 in range(k+1):
      if i1 + i2 <= s <= i1 + i2 + k:
        ans += 1
print(ans)
### BUGGY CODE ###

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

flag = True

if N % 2 != 0:
    for i in range(0,N,2):
        if i == 0:
            if A.count(0) != 1:
                flag = False
        else:
            if A.count(i) != 2:
                flag = False
else:
    for i in range(1,N,2):
        if A.count(i) != 2:
            flag = False
            
if flag == False:
    print(0)
else:
    print(pow(2,N//2,10**9+7))

### FIXED CODE ###

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

from collections import Counter
MOD = 10**9 + 7
c = Counter(a)

ans = 0

if n % 2 == 1:
    for i in range(2, n, 2):
        if c[i] != 2:
            print(0)
            exit()
    if c[0] == 1:
        ans = pow(2, n // 2, MOD)
else:
    for i in range(1, n, 2):
        if c[i] != 2:
            print(0)
            exit()
    ans = pow(2, n // 2, MOD)
print(ans)
### BUGGY CODE ###

s = list(input())
# s = list('ABCABC')
# s = list('ABCACCBABCBCAABCB')

# count = 0
#
# if len(s) < 3:
# 	print(0)
ccc = 0
# while :

i = 0
if len(s) >= 3:
    while i + 2 < len(s):
        if s[i] == 'A':
            if s[i + 1] == 'B' and s[i + 2] == 'C':
                s[i: i + 3] = ['B', 'C', 'A']
                ccc += 1
                if i - 1 >= 0 and s[i - 1] == 'A':
                    i -= 1
                else:
                    i = 0
            else:
                i += 1
        else:
            i += 1
        # print(s)
        # print(i)

        # print(i)
        # print(s)
# print(s)
print(ccc)



### FIXED CODE ###

def test(s):

	res = 0
	aAdd = 0
	last = ''
	tmp = ''
	for i in xrange(len(s)):
		if tmp and tmp > i:
			continue
		if s[i] == 'A':
			aAdd += 1
		elif s[i:i+2] == 'BC':
			# print aAdd
			res = res + aAdd
			tmp = i + 2
		else:
			aAdd = 0
			last = s[i]


	return res
s=raw_input()
print test(s)
### BUGGY CODE ###

A,B,N = map(int,input().split())
max = 0
for i in range(1,N+1):
  num = int((A * i)/B) - A * int(i/B)
  if num > max:
    max = num
    
print(max)

### FIXED CODE ###

A,B,N = map(int,input().split())
num = min(B-1,N)

print((A*num//B)-A*(num//B))
### BUGGY CODE ###

temp1 = input()
n = int(temp1)

temp2 = input().split(" ")

nums = [int(a) for a in temp2]


temp = nums[0]

limit = pow(10, 18)

for i in range(1, n):
    temp = temp * nums[i]

if temp <= limit:
    print(temp)
else:
    print(-1)


### FIXED CODE ###

temp1 = input()
n = int(temp1)

temp2 = input().split(" ")

nums = [int(a) for a in temp2]


temp = nums[0]

limit = pow(10, 18)

for i in range(1, n):
    temp = temp * nums[i]
    if temp > limit:
        break;

if temp <= limit:
    print(temp)
else:
    if 0 in nums:
        print(0)
    else:
        print(-1)
### BUGGY CODE ###


n = int(input())
A = list(map(int,input().split()))
q = int(input())

from collections import Counter
co = list(Counter(A).items())
co = [list(_) for _ in co]
#print(co)
num = len(co)

total = sum(A)
for i in range(q):
    b, c = map(int,input().split())
    for j in range(num):
        if co[j][0] == b:
            total -= (co[j][0] * co[j][1])
            co[j][0] = c
            total += (co[j][0] * co[j][1])
    print(total)


### FIXED CODE ###


n = int(input())
A = list(map(int,input().split()))
q = int(input())
total = sum(A)

l = [[i, 0] for i in range(10**5+1)]
for _ in range(n):
    l[A[_]][1] += 1
#print(l)

for i in range(q):
    b, c = map(int,input().split())
    total -= (l[b][0] * l[b][1])
    tmp = (l[c][0] * (l[c][1] + l[b][1]))
    total -= (l[c][0] * l[c][1])
    total += tmp
    print(total)
    l[c][1] += l[b][1]
    l[b][1] = 0
#    print(l)
### BUGGY CODE ###

N = int(input())
A = [0] + list(map(int, input().split())) + [0]
cost = [abs(A[i] - A[i + 1]) for i in range(N + 1)]
for n in range(N):
    print(sum(cost[:n]) + abs(A[n] - A[n + 2]) + sum(cost[n + 2:]))


### FIXED CODE ###

N = int(input())
A = [0] + list(map(int, input().split())) + [0]
cost = [abs(A[i] - A[i + 1]) for i in range(N + 1)]
start = 0
end = sum(cost[2:])
for n in range(N):
    print(start + abs(A[n] - A[n + 2]) + end)
    if n != N - 1:
        start += cost[n]
        end -= cost[n + 2]
### BUGGY CODE ###

import sys
input = sys.stdin.readline
H, W = map(int, input().split())
A, B = [None] * H, [None] * H
for i in range(H):
    A[i] = list(map(int, input().split()))
for i in range(H):
    B[i] = list(map(int, input().split()))
C = [[abs(A[i][j] - B[i][j]) for j in range(W)] for i in range(H)]
M = 80*(80+80)
#M = 100
dp = [[[False for _ in range(M)] for j in range(W)] for i in range(H)]
dp[0][0][C[0][0]] = True
for i in range(H):
    for j in range(W):
        d = C[i][j]
        for k in range(M-80):
            if i != 0:
                if dp[i-1][j][abs(k-d)]:
                    dp[i][j][k] = True
                elif dp[i-1][j][k+d]:
                    dp[i][j][k] = True
            if j != 0:
                if dp[i][j-1][abs(k-d)]:
                    dp[i][j][k] = True
                elif dp[i][j-1][k+d]:
                    dp[i][j][k] = True

for i, v in enumerate(dp[H-1][W-1]):
    if v:
        print(i)
        break


### FIXED CODE ###

import sys
input = sys.stdin.readline
H, W = map(int, input().split())
A, B = [None] * H, [None] * H
for i in range(H):
    A[i] = list(map(int, input().split()))
for i in range(H):
    B[i] = list(map(int, input().split()))
C = [[abs(A[i][j] - B[i][j]) for j in range(W)] for i in range(H)]
M = 80*(80+80)
dp = [[0 for j in range(W+1)] for i in range(H+1)]
dp[0][1] = 1
dp[1][0] = 1
for i in range(1, H+1):
    for j in range(1, W+1):
        d = C[i-1][j-1]
        if d != 0:
            x = int(bin((dp[i-1][j]&(2**d-1))+2**d)[::-1][:d], 2)<<1
            y = int(bin((dp[i][j-1]&(2**d-1))+2**d)[::-1][:d], 2)<<1
        else:
            x=y=0
        #print(bin(dp[i-1][j]), bin(dp[i-1][j]+(2**10)))
        dp[i][j] = (dp[i-1][j] >> d) | (dp[i-1][j] << d) | (dp[i][j-1] >> d) | (dp[i][j-1] << d) | x | y
        #print(i, j, d, bin(dp[i][j]))

for i, v in enumerate(bin(dp[H][W])[::-1]):
    if v == '1':
        print(i)
        break
### BUGGY CODE ###

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


input()
a_list = [int(s) for s in input().split()]
N = len(a_list)

min_last_hp = 10 ** 9

for start in range(N):
    for c in range(start+1, N):
        last_hp = gcd(a_list[start], a_list[c])
        # if min_last_hp == None:
        #     min_last_hp = last_hp
        if last_hp < min_last_hp:
            min_last_hp = last_hp

print(min_last_hp)


### FIXED CODE ###

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

input()
a_list = [int(s) for s in input().split()]

N = len(a_list)
min_last_hp = 10**10

f = min(a_list)
a_list.remove(f)

for i in a_list:
    last_hp = gcd(f, i)
    if last_hp < min_last_hp:
        min_last_hp = last_hp

s = min(a_list)
kouho=gcd(f,s)
if kouho < min_last_hp:
    print(kouho)
else:
    print(min_last_hp)
### BUGGY CODE ###

H, W = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(H)]
B = [list(map(int, input().split())) for _ in range(H)]

AB = [list(map(lambda x, y: abs(x - y), a, b)) for a, b in zip(A, B)]
dp = [[[0] * 15001 for _ in range(W + 1)] for _ in range(H + 1)]
dp[0][0][0] = 1

for h in range(H):
    for w in range(W):
        ab = AB[h][w]
        for i in range(12800):
            if dp[h][w][i] == 1:
                dp[h+1][w][i+ab] = 1
                dp[h+1][w][abs(i-ab)] = 1
                dp[h][w+1][i+ab] = 1
                dp[h][w+1][abs(i-ab)] = 1

for i in range(1000):
    if dp[H][W-1][i] == 1:
        print(i)
        break


### FIXED CODE ###

H, W = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(H)]
B = [list(map(int, input().split())) for _ in range(H)]

AB = [list(map(lambda x, y: abs(x - y), a, b)) for a, b in zip(A, B)]
dp = [[[0] * 12801 for _ in range(W + 1)] for _ in range(H + 1)]
dp[0][0][0] = 1

for h in range(H):
    for w in range(W):
        ab = AB[h][w]
        for i in range(10000):
            if dp[h][w][i] == 1:
                dp[h+1][w][i+ab] = 1
                dp[h+1][w][abs(i-ab)] = 1
                dp[h][w+1][i+ab] = 1
                dp[h][w+1][abs(i-ab)] = 1

for i in range(1000):
    if dp[H][W-1][i] == 1:
        print(i)
        break
### BUGGY CODE ###

H, W = map(int, input().split())

status = [10000]*H*W
targets = set()
for i in range(H):
    s = input()
    for j, s_j in enumerate(s):
        if s_j == "#":
            targets.add((i, j))
            status[i*W+j] = 0

#c = 0
while True:
    #print("---")
    #for s_i in range(H):
    #    print(status[s_i*W:(s_i+1)*W])
    #print(targets)
    try:
        i, j = targets.pop()
    except KeyError:
        break
    
    d = status[i*W+j] + 1
    
    if j != 0 and status[i*W+j-1] > d:
        status[i*W+j-1] = min(status[i*W+j-1], d) # left
        targets.add((i, j-1))

    if j != W-1 and status[i*W+j+1] > d:
        status[i*W+j+1] = min(status[i*W+j+1], d) # right
        targets.add((i, j+1))

    if i != 0 and status[(i-1)*W+j] > d:
        status[(i-1)*W+j] = min(status[(i-1)*W+j], d) # up
        targets.add((i-1, j))

    if i != H-1 and status[(i+1)*W+j] > d:
        status[(i+1)*W+j] = min(status[(i+1)*W+j], d) # down
        targets.add((i+1, j))
    
 #   c += 1

#print("count", c)
print(max(status))


### FIXED CODE ###

import numpy as np

H, W = map(int, input().split())

status = np.full((H, W), H*W, dtype=int)
for i in range(H):
    s = input()
    for j in range(W):
        if s[j] == "#":
            status[i,j] = 0

for h in range(1, H):
    status[h, :] = np.minimum(status[h, :], status[h-1, :] + 1)
for h in range(0, H-1)[::-1]:
    status[h, :] = np.minimum(status[h, :], status[h+1, :] + 1)
for w in range(1, W):
    status[:, w] = np.minimum(status[:, w], status[:, w-1] + 1)
for w in range(0, W-1)[::-1]:
    status[:, w] = np.minimum(status[:, w], status[:, w+1] + 1)

print(np.max(status))
### BUGGY CODE ###

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

a = [i for i in a if i <k]
n = len(a)

DP1 = [[False]*(k+1) for i in range(n+1)]
DP1[0][0] = True
DP2 = [[False]*(k+1) for i in range(n+1)]
DP2[0][0] = True
b = a[::-1]

for i in range(n):
    for j in range(k+1):
        if DP1[i][j]:
            DP1[i+1][j] = True
            if a[i]+j <= k:
                DP1[i+1][a[i]+j] = True
        if DP2[i][j]:
            DP2[i+1][j] = True
            if b[i]+j <= k:
                DP2[i+1][b[i]+j] = True

from itertools import accumulate
for i in range(n+1):
    DP1[i] = [j for j in range(k+1) if DP1[i][j]]
    DP2[i] = [0] + list(accumulate(DP2[i]))

ans = 0
for i in range(n):
    use = False
    for j in DP1[i]:
        left = max(0, k-a[i]-j)
        right = k-j
        if DP2[n-i-1][right] - DP2[n-i-1][left]:
            use = True
            break
    if not use:
        ans += 1

print(ans)


### FIXED CODE ###

import numpy as np

def main():
    def check(m):
        DP = np.full(k+1, False)
        DP[0] = True
        for i in range(n):
            if i == m:
                continue
            DP[a[i]:] = np.logical_or(DP[a[i]:], DP[:k+1-a[i]])
        return any(DP[i] for i in range(k-a[m], k))

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

    a = [i for i in a if i <k]
    a.sort()
    n = len(a)

    left = -1
    right = n

    while right-left > 1:
        mid = (right+left)//2
        if check(mid):
            right = mid
        else:
            left = mid

    print(right)

main()
### BUGGY CODE ###

import sys

def main():
  input = sys.stdin.readline
  n, k = map(int, input().split())
  a = [int(x) for x in input().split()]
  f = [int(x) for x in input().split()]
  a.sort(reverse=True)
  f.sort()
  
  l, r = -1, pow(10, 12)+1
  while r-l > 1:
    judge = (r+l)//2
    sub = 0
    for i in range(n):
      if a[i]*f[i] <= judge:
        continue
      sub += a[i]-judge//f[i]
    if sub <= k:
      r = judge
    else:
      l = judge
  
  print(r)
  

if __name__ == "__main__":
  main()

### FIXED CODE ###

import sys

def main():
  input = sys.stdin.readline
  n, k = map(int, input().split())
  a = [int(x) for x in input().split()]
  f = [int(x) for x in input().split()]
  a.sort(reverse=True)
  f.sort()
  
  l, r = -1, pow(10, 12)+1
  while r-l > 1:
    judge = (r+l)//2
    sub = 0
    for i in range(n):
      if a[i]*f[i] <= judge:
        continue
      sub += a[i]-judge//f[i]
    if sub <= k:
      r = judge
    else:
      l = judge
  
  print(r)
  
if __name__ == "__main__":
  main()
### BUGGY CODE ###

n,p = map(int,input().split())
ans = 1
x = 2
while x**n<=p:
  if p%(x**n)==0:
    p /= x**n
    ans *= x
  else:
    x+= 1
print(ans)

### FIXED CODE ###

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

n,p=map(int,input().split())
prime_list = factorization(p)
ans = 1
for x in prime_list:
  ans *= x[0]**(x[1]//n)
print(ans)
### BUGGY CODE ###

import sys
from collections import deque
sys.setrecursionlimit(10**7)
input=sys.stdin.readline
h,w=map(int,input().split())
c=[int(i)-1 for i in input().split()]
d=[int(i)-1 for i in input().split()]
s=[input() for i in range(h)]
inf=100000000
dp=[[-1 if s[i][j]=="#" else inf for j in range(w)] for i in range(h)]
dp[c[0]][c[1]]=0
now=deque([[c[0],c[1]]])
#グリッド上のbfsはfor文で
def bfs():
    global h,w,s,dp,now
    while len(now):
        i,j=now.popleft()
        for k,l in [[i-1,j],[i+1,j],[i,j-1],[i,j+1]]:
            if 0<=k<h and 0<=l<w:
                if dp[k][l]!=-1:
                    if dp[k][l]>dp[i][j]:
                        dp[k][l]=dp[i][j]
                        now.appendleft([k,l])
        for k in range(i-2,i+3):
            for l in range(j-2,j+3):
                if 0<=k<h and 0<=l<w:
                    if dp[k][l]!=-1:
                        if dp[k][l]>dp[i][j]+1:
                            dp[k][l]=dp[i][j]+1
                            now.append([k,l])
bfs()
print(dp[d[0]][d[1]] if dp[d[0]][d[1]]!=inf else -1)

### FIXED CODE ###

from collections import deque


def main():
    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Dh, Dw = map(int, input().split())
    S = [input() for _ in range(H)]

    Q = deque([[Ch - 1, Cw - 1, 0]])  # 座標とワープ回数

    cost = [[-1 for _ in range(W)] for _ in range(H)]  # ワープ回数を記録

    while Q:
        r, c, cnt = Q.popleft()

        if cost[r][c] != -1:  # 訪れたことがある
            continue

        cost[r][c] = cnt

        for dr in range(-2, 3):
            for dc in range(-2, 3):
                nr = r + dr
                nc = c + dc

                if 0 <= nr < H and 0 <= nc < W and S[nr][nc] == ".":
                    if abs(dr) + abs(dc) == 1:  # 上下左右
                        Q.appendleft([nr, nc, cnt])
                    elif abs(dr) + abs(dc) >= 2:  # ワープ
                        Q.append([nr, nc, cnt + 1])

    print(cost[Dh - 1][Dw - 1])


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

S = list(input())
S = S[::-1]

ans = 0
bc_score = 0
flag = 1

if len(S) <= 1:
    print(0)
    exit()

while len(S) != 0:
    if S[0]=="C" and S[1] == "B":
        bc_score = 0
        bc_score += 1
        S.pop(0)
        S.pop(0)
        flag = 1
        if len(S) == 1:
            if S[0] == "A":
                ans += 1
            S.pop(0)
        while flag == 1 and len(S) != 0:
            flag = 0
            if S[0]=="C" and S[1] == "B":
                bc_score += 1
                S.pop(0)
                S.pop(0)
                flag = 1
            if len(S) != 0:
                if S[0] == "A":
                    ans += bc_score
                    S.pop(0)
                    flag = 1
    else:
        S.pop(0)

print(ans)

### FIXED CODE ###

S = list(input())
S = S[::-1]

t = 0
ans = 0
bc_score = 0
flag = 1

if len(S) <= 2:
    print(0)
    exit()

while t <= len(S)-2:
    if S[t]=="C" and S[t+1] == "B":
        bc_score = 0
        bc_score += 1
        t += 2
        flag = 1
        if t == len(S)-1:
            if S[t] == "A":
                ans += 1
            t += 1
        while flag == 1 and t <= len(S) - 1:
            flag = 0
            if S[t]=="C" and S[t+1] == "B":
                bc_score += 1
                t += 2
                flag = 1
            if t <= len(S) - 1:
                if S[t] == "A":
                    ans += bc_score
                    t += 1
                    flag = 1
    else:
        t += 1

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

# coding: utf-8
# Your code here!
r , g , b , n = map(int,input().split())
ans = 0
R = -(-n//r)
G = -(-n//g)
for i in range(R+1):
    for j in range(G+1):
        
        if n-r*i-g*j < 0:
            break
        else:
            if ((n-r*i-g*j)/b).is_integer():
                ans += 1
print(ans)

### FIXED CODE ###

# coding: utf-8
# Your code here!
r , g , b , n = map(int,input().split())
ans = 0
R = -(-n//r)
G = -(-n//g)
for i in range(R+1):
    for j in range(G+1):
        su = n-r*i-g*j
        if n-r*i-g*j < 0:
            break
        else:
            if (su/b).is_integer():
                ans += 1
print(ans)
### BUGGY CODE ###

S=input()
ans,n=0,len(S)
dp=[0]*(n+1)
s=0
for i in range(1,n+1):
  s+=int(S[-i])*(10**(i-1))
  dp[n-i]=s%2019
for i in range(n-3):
  for j in range(i+3,n+1):
    if dp[i]==dp[j]:
      ans+=1
print(ans)

### FIXED CODE ###

S=input()
ans,n=0,len(S)
dp=[0]*(2019)
s,dp[0],k=0,1,1
for i in range(1,n+1):
  s=(s+int(S[-i])*k)%2019
  k=(k*10)%2019
  ans+=dp[s]
  dp[s]+=1
print(ans)
### BUGGY CODE ###

import re
N = int(input())
S = input()
for i in range(N//2,0,-1):
    for j in range(N-2*i+1):
        if re.search(S[j:j+i],S[j+i:]):
            print(i)
            exit()
print(0)

### FIXED CODE ###

N = int(input())
S = input()
DP = [[0]*(N+1)for i in range(N+1)]
ans = 0
for i in range(N):
    for j in range(N):
        if S[i] == S[j] :
            DP[i+1][j+1] = DP[i][j]+1
            if j-DP[i+1][j+1]-i < 0:
                DP[i+1][j+1] = 0
print(max([max(i) for i in DP]))
### BUGGY CODE ###

from sys import stdin

def fun():
    n = (int(i) for i in input().split())

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

    l.sort()

    while 1 < len(l):
        for i in range(1, len(l)):
            if l[i]%l[0] == 0:
                l[i] = l[i] - l[0]
            elif l[i] - l[i-1] == 1:
                print(1)
                return
            else:
                l[i] = l[i]%l[0]
        l = [e for e in l if e != 0]
        l.sort()

    print(l[0])
    return

if __name__ == '__main__':
    fun()



### FIXED CODE ###

from sys import stdin

def fun():
    n = (int(i) for i in input().split())

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

    l = list(set(l))
    l.sort()

    while 1 < len(l):
        k = len(l)
        for i in range(1, k):
            if l[k-i]%l[0] == 0:
                l.pop(k-i)
            elif l[k-i] - l[k-i-1] == 1:
                print(1)
                return
            else:
                l[k-i] = l[k-i]%l[0]
        #l = [e for e in l if e != 0]
        l = list(set(l))
        l.sort()

        if l[0]==1:
            print(1)
            return

    print(l[0])
    return

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

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
edge1 = []
edgeN = []
for _ in range(M):
    s, n = map(int, input().split())
    if s == 1:
        edge1.append(n)
    elif n == N:
        edgeN.append(s)
for e1 in edge1:
    if e1 in edgeN:
        print('POSSIBLE')
        quit()
print('IMPOSSIBLE')

### FIXED CODE ###

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
edge1 = []
edgeN = []
for _ in range(M):
    s, n = map(int, input().split())
    if s == 1:
        edge1.append(n)
    elif n == N:
        edgeN.append(s)
if len(set(edge1) & set(edgeN)) > 0:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')
### BUGGY CODE ###

n = int(input())
l = [list(map(int,input().split())) for _ in range(n-1)]

dp = [[0 for _ in range(n)] for _ in range(n)]
INF = 10**18
for i in range(n):
    for j in range(n):
        if i!=j:
            dp[i][j] = INF
for a,b,c in l:
    dp[a-1][b-1] = c
    dp[b-1][a-1] = c
#print(dp)

#最短リスト
for c in range(n):
    for f in range(n):
        for la in range(n):
            dp[f][la] = min(dp[f][la] , dp[f][c] +  dp[c][la])

q,k = map(int,input().split())
for _ in range(q):
    x,y = map(int,input().split())
    k1 = dp[x-1][k-1] + dp[k-1][y-1]
    k2 = dp[y-1][k-1] + dp[k-1][x-1]
    print(min(k1,k2))


### FIXED CODE ###

import sys

sys.setrecursionlimit(200000)

n = int(input())
l = [list(map(int,input().split())) for _ in range(n-1)]
q,k = map(int,input().split())
k -= 1
#kからの距離
tree = [[] for _ in range(n)]
for a,b,c in l:
    a -= 1
    b -= 1
    tree[a].append([b,c])
    tree[b].append([a,c])

bit = [0 for _ in range(n)]
depth = [0 for _ in range(n)]
def dfs(v,d=0):
    bit[v] = 1
    depth[v] = d
    for j,k in tree[v]:
        if bit[j]==0:
            dfs(j,d+k)
dfs(k)

for _ in range(q):
    x,y = map(int,input().split())
    x-= 1
    y-= 1
    print(depth[x] + depth[y])
### BUGGY CODE ###

S = input()

index = 0
ans = 0
for i in range(len(S)):
    for j in range(i+1, len(S)):
        index = int(S[i:j+1])
        if index % 2019 == 0: ans+=1
print(ans)


### FIXED CODE ###

#!/usr/bin/env python3
S = input()[::-1]

mod = [0]*2019
mod[0] = 1
ten = 1
index = 0
for s in S:
    index += ten*int(s)
    index %= 2019
    mod[index] += 1
    ten *= 10
    ten %= 2019

ans = 0
for m in mod:
    ans += m * (m-1) // 2

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

import sys
input=sys.stdin.readline
n,t=map(int,input().split())
AB=[]
for i in range(n):
  a,b=map(int,input().split())
  AB.append((a,b))

def f(m):
  dp=[[0]*(t) for _ in range(n+1)]
  for i in range(n):
    if i==m:
      a,b=AB[i]
      add=b
      for j in range(t):
        dp[i+1][j]=dp[i][j]
    else:
      a,b=AB[i]
      for j in range(t):
        if j>=a:
          dp[i+1][j]=max(dp[i][j-a]+b,dp[i][j],dp[i+1][j-1])
        else:
          dp[i+1][j]=max(dp[i][j],dp[i+1][j-1])
  return dp[n][t-1]+add
ans=0
for i in range(n):
  ans=max(ans,f(i))
print(ans)


### FIXED CODE ###

import sys
input=sys.stdin.readline
n,t=map(int,input().split())
AB=[]
for i in range(n):
  a,b=map(int,input().split())
  AB.append((a,b))
AB.sort(key=lambda x:x[0])
ans=0
dp=[[0]*(t) for _ in range(n+1)]
for i in range(n-1):
  a,b=AB[i]
  for j in range(t):
    if j>=a:
      dp[i+1][j]=max(dp[i][j-a]+b,dp[i][j],dp[i+1][j-1])
    else:
      dp[i+1][j]=max(dp[i][j],dp[i+1][j-1])
  ans=max(ans,dp[i+1][t-1]+AB[i+1][1])

print(ans)