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

n,m=map(int,input().split())
h=list(map(int,input().split()))
ab=[list(map(int,input().split())) for i in range(m)]

good=[i for i in range(1,n+1)]

for i in ab:
  a,b=h[i[0]-1],h[i[1]-1]
  if a<b:
    try:
      good.remove(i[0])
    except ValueError:
      pass
  elif a>b:
    try:
      good.remove(i[1])
    except ValueError:
      pass
  else:
    try:
      good.remove(i[0])
    except ValueError:
      pass
    try:
      good.remove(i[1])
    except ValueError:
      pass
print(len(good))

### FIXED CODE ###

n,m=map(int,input().split())
h=list(map(int,input().split()))
ab=[list(map(int,input().split())) for i in range(m)]

bad=[]
for i in ab:
  a,b=h[i[0]-1],h[i[1]-1]
  if a<b:
    bad+=[i[0]]
  elif a>b:
    bad+=[i[1]]
  else:
    bad+=[i[0],i[1]]
print(n-len(set(bad)))
### BUGGY CODE ###

import numpy as np
s = input()
t = input()
dp = np.zeros((len(s)+1, len(t)+1))

for i in range(len(s)):
    for j in range(len(t)):
        if s[i] == t[j]:
            dp[i][j] = dp[i-1][j-1]+1
        else :
            dp[i][j] = max(dp[i-1][j], dp[i][j-1])

l = int(dp[len(s)-1][len(t)-1])
i = len(s)-1
j = len(t)-1
ans = []

while i>=0 and j>=0:
    if s[i] == t[j]:
        ans.append(s[i])
        i -= 1
        j -= 1
    elif dp[i][j] == dp[i-1][j]:
        i -= 1
    else :
        j -= 1
print(''.join(ans[::-1]))


### FIXED CODE ###

import numpy as np
s = np.array(list(input()))
t = np.array(list(input()))
dp = np.zeros((len(s)+1, len(t)+1), dtype=int)

equal = s[:, None] == t[None, :]

for i in range(len(s)):
    dp[i+1, 1:] = np.maximum(dp[i, :-1]+equal[i], dp[i, 1:])
    dp[i+1] = np.maximum.accumulate(dp[i+1])

i = len(s)
j = len(t)
ans = []

while i>0 and j>0:
    if s[i-1] == t[j-1]:
        ans.append(s[i-1])
        i -= 1
        j -= 1
    elif dp[i][j] == dp[i-1][j]:
        i -= 1
    else :
        j -= 1

print(''.join(ans[::-1]))
### BUGGY CODE ###

S = input()
N = len(S)

dp = [[0]*2019 for _ in [0]*(N+1)]
ans = 0
for i,s in enumerate(S,1):
    s = int(s)
    dpi = dp[i]
    dpi1 = dp[i-1]
    dpi[s] += 1
    for j in range(2019):
        dpi[(j*10+s)%2019] += dpi1[j]
    ans += dpi[0]

print(ans)

### FIXED CODE ###

S = input()
N = len(S)

dp = [[0]*2019 for _ in [0]*2]
ans = 0
for i,s in enumerate(S,1):
    s = int(s)
    i %= 2
    dpi = [0]*2019
    dpi1 = dp[1-i]
    dpi[s] += 1
    for j in range(2019):
        dpi[(j*10+s)%2019] += dpi1[j]
    dp[i] = dpi
    ans += dpi[0]

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

def xgcd(a, b):
    x0, y0, x1, y1 = 1, 0, 0, 1
    while b != 0:
        q, a, b = a // b, b, a % b
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
    return a

#targetまでの素数の数
import math
def sieve_of_eratosthenes2(target):
    dest = math.ceil(math.sqrt(target))
    target_list = [i for i in range(2, target//2+1) if target%i==0]
    prime_num = 0
 
    while True:
        num_min = target_list[0]
        if num_min > dest:
            prime_num += len(target_list)
            break
        prime_num += 1        
        target_list = [i for i in target_list if i%num_min!=0]
        if target_list==[]:
            break
 
    return prime_num

import random
def is_prime(q, k=50):
    q = abs(q)
    if q == 2:
        return True
    if q < 2 or q % 2 == 0:
        return False

    d = (q - 1) >> 1
    while d & 1 == 0:
        d >>= 1
    for i in range(k):
        a = random.randint(1, q - 1)
        t = d
        y = pow(a, t, q)
        while t != q - 1 and y != 1 and y != q - 1:
            y = pow(y, 2, q)
            t <<= 1
        if y != q - 1 and t & 1 == 0:
            return False
    return True

a, b = map(int, input().split())
gcd = xgcd(a, b)
if gcd == 1:
    print(1)
elif is_prime(gcd):
    print(2)
else:
    ans = sieve_of_eratosthenes2(gcd)    
    print(ans+1)



### FIXED CODE ###

def xgcd(a, b):
    x0, y0, x1, y1 = 1, 0, 0, 1
    while b != 0:
        q, a, b = a // b, b, a % b
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
    return a


import random
def is_prime(q, k=50):
    q = abs(q)
    if q == 2:
        return True
    if q < 2 or q % 2 == 0:
        return False

    d = (q - 1) >> 1
    while d & 1 == 0:
        d >>= 1
    for i in range(k):
        a = random.randint(1, q - 1)
        t = d
        y = pow(a, t, q)
        while t != q - 1 and y != 1 and y != q - 1:
            y = pow(y, 2, q)
            t <<= 1
        if y != q - 1 and t & 1 == 0:
            return False
    return True

def prime_num(target):
    ra = 2
    prime = 0
    while target>1:
        if target%ra == 0:
            prime += 1
            while target%ra==0:
                target = target//ra
            if is_prime(target):
                prime += 1
                break
        if ra == 2:
            ra += 1
        else:
            ra += 2
    return prime   
        
a, b = map(int, input().split())
gcd = xgcd(a, b)
if gcd == 1:
    print(1)
elif is_prime(gcd):
    print(2)
else:
    ans = prime_num(gcd)    
    print(ans+1)
### BUGGY CODE ###

r,g,b,n= map(int,input().split())
R = n//r
G = n // g
B = n // b
ans =0
for i in range(R+2):
    for j in range(G+2):
        if n - (i*r+j*g)< 0:
            continue
        if (n - (i*r+j*g) )%b ==0 and n - (i*r+j*g)>=0:
            ans +=1
print(ans)

### FIXED CODE ###

r,g,b,n= map(int,input().split())
R = n//r
G = n // g
B = n // b
ans =0
for i in range(R+2):
    for j in range(G+2):
        if n - (i*r+j*g)< 0:
            continue
        if (n - (i*r+j*g) )%b ==0 and n - (i*r+j*g)>=0:
            ans +=1
print(ans)
### BUGGY CODE ###

L,R = map(int,input().split())
m = float("inf")
for i in range(L,R+1):
    for j in range(i+1,R+1):
        m = min(m,(i*j)%2019)
        if m == 0:
            break
print(m)

### FIXED CODE ###

L,R = map(int,input().split())
k = 0
m = float("inf")
for i in range(L,R+1):
    k += 1
    if k >= 2019**2 + 1:
        break
    for j in range(i+1,R+1):
        m = min(m,(i*j)%2019)
        if m == 0:
            break
print(m)
### BUGGY CODE ###

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

for i in range(a,b+1):
    if i<a+k or i>b-k:
        print(i)

### FIXED CODE ###

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

for i in range(a,min(b+1,a+k)):
    li.append(i)

for j in range(b,max(a-1,b-k),-1):
    li.append(j)

li=list(set(li))
li.sort()

for i in li:
    print(i)
### BUGGY CODE ###

N,M=map(int,input().split())
AB=sorted([list(map(int,input().split())) for i in range(N)],key=lambda x: (-x[1],x[0]))
r=0
on=[-1]*M
import sys
sys.setrecursionlimit(10**5)
def put(i):
    r=0
    if i<0:
        return -1
    if on[i]<0:
        if i==0:
            if on[i]==-1:
                on[i]=-2
            else:
                r=-1
        elif on[i-1]==-1:
            on[i]=i-1
        else:
            on[i]=on[i-1]
    else:
        r=put(on[i])
    return r
for a,b in AB:
    x=put(M-a)
    if x!=-1:
        r+=b
print(r)

### FIXED CODE ###

N,M=map(int,input().split())
AB=[list(map(int,input().split())) for i in range(N)]
r=0
from heapq import heappop,heappush
q=[]
l=[[] for i in range(10**5)]
for a,b in AB:
    l[a-1].append(b)
for i in range(M):
    for e in l[i]:
        heappush(q,-e)
    if len(q)>0:
        r+=-heappop(q)
print(r)
### BUGGY CODE ###

loops = int(input())
paper = []

# 1 <= loops <= 10^6
for _ in range(loops):
    num = int(input())
    if num in paper:
        paper.remove(num)
    else:
        paper.append(num)
print(len(paper))


### FIXED CODE ###

loops = int(input())
d = {}

# 10^6
for _ in range(loops):
    key = input()
    if key not in d: # ?
        d[key] = 1
    else:
        d[key] += 1

# 10^6
ans = 0
for k,v in d.items():
    if v % 2 != 0:
        ans += 1
print(ans)
### BUGGY CODE ###

s = input()[::-1]
s += "0"
n = len(s)
dp = [[10**7 for _ in range(2)] for _ in range(n+1)]
dp[0][0] = 0
for i in range(n):
	for j in range(2):
		x = int(s[i]) + j
		for a in range(10):
			kurisagaru = False
			if a >= x:
				b = 0
			else:
				b = 10 + a - x
				kurisagaru = True
			dp[i+1][kurisagaru] = min(dp[i+1][kurisagaru], dp[i][j]+a+b)
print(dp[n][0])

### FIXED CODE ###

s = list(input())
s.reverse()
s += ["0"]
n = len(s)
dp = [[10**7 for _ in range(2)] for _ in range(n+1)]
dp[0][0] = 0
for i in range(n):
	for j in range(2):
		x = int(s[i]) + j
		for a in range(10):
			kurisagaru = False
			if a >= x:
				b = 0
			else:
				b = 10 + a - x
				kurisagaru = True
			dp[i+1][kurisagaru] = min(dp[i+1][kurisagaru], dp[i][j]+a+b)
print(dp[n][0])
### BUGGY CODE ###

N,M,K=map(int,input().split())
a=input().split()
A=[int(c) for c in a]
b=input().split()
B=[int(c) for c in b]
answers=[0]
As=[0]
Bs=[0]
wholeA=0
wholeB=0
for a in range(N):
    wholeA+=A[a]
    As.append(wholeA)
for b in range(M):
    wholeB+=B[b]
    Bs.append(wholeB)

for a in range(N+1):
    for b in range(M+1):
        whole = As[a]
        whole+=Bs[b]
        if whole>K:
            break
        else:
            answers.append(a+b)

print(max(answers))


### FIXED CODE ###

N,M,K=map(int,input().split())
a=input().split()
A=[int(c) for c in a]
b=input().split()
B=[int(c) for c in b]
answers=[0]
As=[0]
Bs=[0]
wholeA=0
wholeB=0
bs = [M]
for a in range(N):
    wholeA+=A[a]
    As.append(wholeA)
for b in range(M):
    wholeB+=B[b]
    Bs.append(wholeB)
for a in range(N+1):
    for b in range(bs[-1],-1,-1):
        whole = As[a]
        whole+=Bs[b]
        if whole<=K:
            answers.append(a+b)
            bs.append(b)
            break
print(max(answers))
### BUGGY CODE ###

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

s = 1
for i in range(k):
    s *= li[i]

for i in range(k, n):
    t = s * li[i]
    t //= li[i-k]

    if s < t:
        print('Yes')
    else:
        print('No')
        
    s = t


### FIXED CODE ###

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

for i in range(k, n):

    if li[i-k] < li[i]:
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

import heapq
import math

n,m = map(int,input().split())
lst = list(map(int,input().split()))
lst = list(map(lambda x:x*(-1),lst))
heapq.heapify(lst)
for i in range(m):
    num = heapq.heappop(lst) * (-1)
    nxt_num = math.floor(num / 2)
    heapq.heappush(lst,nxt_num * -1)
    if sum(lst) == 0:
        break
print(sum(lst) * (-1))

### FIXED CODE ###

import heapq
import math
n,m = map(int,input().split())
lst = [int(x) * (-1) for x in input().split()]
heapq.heapify(lst)
for use_cnt in range(m):
    num = heapq.heappop(lst) * -1
    nxt_num = math.floor(num / 2)
    heapq.heappush(lst,nxt_num * -1)
print(sum(lst) * (-1))
### BUGGY CODE ###

MAX = 26

def has_same_chr(s):
    for i in range(0, len(s)):
        for j in range(i+1, len(s)):
            if s[i] == s[j]:
                #print("{}, {}:{}".format(i,j,s[i]))
                return False
    return True

# 長さlengthの部分文字列をsから取得してs_retに付与してs_listに追加して返す
def get_partial_strings(length, s_ret, s_list, s):
    if length == 0:
        #print("s_ret:{}".format(s_ret))
        return s_ret
    
    for i in range(0, len(s)):
        new_ret = s_ret + s[i]
        #print("new:{}, s:{}".format(new_ret, s[i+1:]))
        s_list.append(get_partial_strings(length-1, new_ret, s_list, s[i+1:]))
    
    return s_list
    

l=int(input())
s=input()

ret = 0
max = MAX
if l < MAX:
    max = l
for i in range(1,l+1):
    strs = []
    for string in get_partial_strings(i, "", strs, s):
        if has_same_chr(string):
            #print(string)
            ret += 1

print(ret)


### FIXED CODE ###

KIND = 26
l=int(input())
s=input()

alpha_list = []
for i in range(0, KIND):
    alpha_list.append(0)

for i in s:
    alpha_list[ord(i)-ord('a')] += 1

ret = 1
for num in alpha_list:
    ret *= (num + 1)
print((ret-1)%(1000000000+7))
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
a.sort()
cnt = [0 for _ in range(10**6+5)]
ans = 0
for x in a:
    for i in range(x, 10**6+5, x):
        cnt[i] += 1
for x in a:
    if cnt[x] == 1:
        ans += 1
print(ans)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
a.sort()
cnt = [0 for _ in range(10**6+5)]
ans = 0
if n == 1:
    print(1)
    exit()
if a[0] == 1:
    if a[1] != 1:
        print(1)
    else:
        print(0)
    exit()
for x in a:
    for i in range(x, 10**6+5, x):
        cnt[i] += 1
for x in a:
    if cnt[x] == 1:
        ans += 1
print(ans)
### BUGGY CODE ###

n,k = map(int,input().split())
h = list(map(int, input().split()))
v = [0 for _ in range(n)]
for i in range(n):
	if i-1 >= 0:
		v[i] = min([v[i-j-1] + abs(h[i] - h[i-j-1]) for j in range(min([k, i]))])
print(v[n-1])

### FIXED CODE ###

n,k=map(int,input().split())
h=list(map(int, input().split()))
v=[0]*n
for i in range(1,n):
	u = h[i]
	v[i] = min([v[j] + abs(h[j]-u) for j in range(max(0, i-k), i)])
print(v[n-1])
### BUGGY CODE ###

import sys

def isEmpty(S):
  if len(S) == 0:
    return True

def isFull(S):
  if len(S) >= 100000:
    return True

def enqueue(x):
  if isFull(x_list_list):
    print 'Error'
  x_list_list.append(x)

def dequeue(x_list_list):
  if isEmpty(x_list_list):
    print 'Error'
  del_list = x_list_list[0]
  x_list_list.pop(0)
  return(del_list)

y = sys.stdin.readline()
a, b = y.split(" ")
a = int(a)
b = int(b)

S = []
x_list_list = []

for i in range(a):
  text = raw_input()
  x_list = text.split()
  x_list[1] = int(x_list[1])
  x_list.append(0)
  x_list_list.append(x_list)

flag = a
while flag != 0:
  if int(x_list_list[0][1]) > b:
    x_list_list[0][1] -= int(b)
    for j in range(flag):
      x_list_list[j][2] += b
    del_list = dequeue(x_list_list)
    enqueue(del_list)
  elif int(x_list_list[0][1]) <= b:
    for j in range(flag):
      x_list_list[j][2] += x_list_list[0][1]
    x_list_list[0][1] = 0
    flag -= 1
    print x_list_list[0][0],x_list_list[0][2]
    dequeue(x_list_list)
    

### FIXED CODE ###

import sys

def isEmpty(S):
  if len(S) == 0:
    return True

def isFull(S):
  if len(S) >= 100000:
    return True

def enqueue(x):
  if isFull(x_list_list):
    print 'Error'
  x_list_list.append(x)

def dequeue(x_list_list):
  if isEmpty(x_list_list):
    print 'Error'
  del_list = x_list_list[0]
  x_list_list.pop(0)
  return(del_list)

y = sys.stdin.readline()
a, b = y.split(" ")
a = int(a)
b = int(b)

S = []
x_list_list = []
run_time = 0

for i in range(a):
  text = raw_input()
  x_list = text.split()
  x_list[1] = int(x_list[1])
  x_list.append(0)
  x_list_list.append(x_list)

flag = a
while flag != 0:
  if x_list_list[0][1] > b:
    x_list_list[0][1] -= int(b)
    run_time += b
    del_list = dequeue(x_list_list)
    enqueue(del_list)
  else:
    run_time += x_list_list[0][1]
    x_list_list[0][2] = run_time
    x_list_list[0][1] = 0
    flag -= 1
    print x_list_list[0][0],x_list_list[0][2]
    dequeue(x_list_list)
### BUGGY CODE ###

N=int(input())
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
ans=0
for i in range(1,N+1):
  p=factorization(i)
  a=1
  for x,y in p:
    a*=(y+1)
  ans+=a*i
print(ans-1)

### FIXED CODE ###

N=int(input())
ans=0
for i in range(1,N+1):
  ans+=(i+N//i*i)*(N//i)//2
print(ans)
### BUGGY CODE ###

#
import sys
import math
import numpy as np
import itertools

n = int(input())
a=1
ll = [int(i) for i in input().split()] 
for i in range(n):
    a *= ll[i]
if a > 10**18:
        print(-1)
else:
    print(a)




### FIXED CODE ###

#
import sys
import math
import numpy as np
import itertools

n = int(input())
a=1
ll = [int(i) for i in input().split()] 
ll.sort()

for i in range(n):
    a *= ll[i]
    if a == 0:
        print(0)
        exit()
    if a > 10**18:
        print(-1)
        exit()
else:
    print(a)
### BUGGY CODE ###

import sys

def solve():
    N = int(input())
    print(0)
    a = input()
    basis = -1
    if a == "Vacant": return 0
    elif a == "Male": basis = 0
    else: basis = 1
    low, high = 0, N
    while high - low > 1:
        mid = (low + high) // 2
        print(mid)
        a = input()
        if a == "Vacant": break
        else:
            b = (0 if a == "Male" else 1)
            if (mid - basis) % 2 != (a ^ b):
                high = mid
            else:
                low = mid
                basis = b
    else:
        print(low)

    return 0

if __name__ == "__main__":
    solve()


### FIXED CODE ###

N = int(input())

print(0, flush = True)
s = input()
if s == "Vacant": exit()
else:
    reference_state = s
    opposite_state = ("Male" if s == "Female" else "Female") 
    low, high = 0, N
    count = 1
    while count < 20:
        mid = (low + high)//2
        expected_state = (reference_state if mid % 2 == 0 else opposite_state)
        print(mid, flush = True)
        s = input()
        if s == "Vacant":
            break
        else:
            if s == expected_state: low = mid
            else: high = mid
            count += 1
### BUGGY CODE ###

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

F = [0]*(n+2) # [l,r+1): 1<=[l]<[r+1]<=n+1
for _ in range(k):
    l, r = map(int, input().split())
    F[l] += 1
    F[r+1] += -1

# print(F)
S = []
for i in range(n+1): # i:[0, n]
    if F[i] > 0: S.append(i)
    F[i+1] += F[i]

# print(F)
# print(n,k)
# print(S)

MOD = 998244353
dp = [0]*(n+1)  # [0,n]
dp[1] = 1

for i in range(1, n+1): # i:[1,n]
    for s in S:
        if i + s <= n:
            # print('s {} i {} n {}'.format(s,i,n))
            dp[i + s] += dp[i]
            dp[i + s] %= MOD

# print(dp)

print((dp[n] + MOD) % MOD)


### FIXED CODE ###

n, k = map(int, input().split())
LR = []
for _ in range(k):
    l, r = map(int, input().split())
    LR.append([l, r+1])

MOD = 998244353
dp = [0]*(n+1)  # [0,n]
dp[0] = 1
dp[1] = -1

for i in range(n): # i:[0,n-1]
    if i > 0: dp[i] += dp[i-1]
    for j in range(k):
        l, r = LR[j]
        if i+l < n:
            dp[i+l] += dp[i]
            dp[i+l] %= MOD
        if i+r < n:
            dp[i+r] -= dp[i]
            dp[i+r] %= MOD

print((dp[n-1] + MOD) % MOD)
### BUGGY CODE ###

from collections import deque
 
n,m,k= map(int, input().split())
 
fri = [[] for _ in range(n+1)]
blo = [[] for _ in range(n+1)]
 
for i in range(m):
    a, b = map(int, input().split())
    fri[a].append(b)
    fri[b].append(a)
 
for i in range(k):
    a, b = map(int, input().split())
    blo[a].append(b)
    blo[b].append(a)
 
 
gru = [-1] * (n+1)
gru[0] = 0
gru[1] = 0
 
nosa = 1
nowgru = 0
grouplist = [[] for _ in range(n+1)]
grouplist[nowgru].append(nosa)
while True:
 
    d = deque()
    d.append(nosa)
 
    while d:
        v = d.popleft()
        for i in fri[v]:
            if gru[i] != -1:
                continue
            gru[i] = nowgru
            d.append(i)
            grouplist[nowgru].append(i)
 
    nowgru +=1
    if -1 in gru:
        nosa = gru.index(-1)
    else:
        break
 
 
for i in range(1,n+1):
    print(len(set(grouplist[gru[i]])-set(blo[i]))-len(fri[i])-1)

### FIXED CODE ###

from collections import deque

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

fri = [[] for _ in range(n+1)]
blo = [[] for _ in range(n+1)]

for i in range(m):
    a, b = map(int, input().split())
    fri[a].append(b)
    fri[b].append(a)

for i in range(k):
    a, b = map(int, input().split())
    blo[a].append(b)
    blo[b].append(a)


gru = [-1] * (n+1)
gru[0] = 0
visited = [False]*(n+1)
D = {}

for root in range(1,n+1):
    if visited[root]:
        continue
    
    D[root]= set([root])
    d = deque()
    d.append(root)
    while d:
        v = d.popleft()
        visited[v] = True
        gru[v] = root
        for to in fri[v]:
            if visited[to]:
                continue
            D[root].add(to)
            d.append(to)


nans = [0]*n
for i in range(1,n+1):
    g = D[gru[i]]
    ans = len(g)-len(fri[i])-1
    for b in blo[i]:
        if b in g:
            ans -= 1
    nans[i-1] = ans

print(*nans, sep='\n')
### BUGGY CODE ###

s = input()
q = int(input())

for i in range(q):
    x = input().split()
    
    if (x[0] == '1'):
        s = s[::-1]
    elif(x[0] == '2'):
        if(x[1] == '1'):
            s = x[2] + s
        elif(x[1] == '2'):
            s += x[2]

print(s)

### FIXED CODE ###

from collections import deque

revFlag = False

s = deque(input())
q = int(input())

for i in range(q):
    a,b,c, *_ = input().split() + [None, None]
    
    if(a == '1'):
        revFlag = not revFlag
        
    else:
        b = int(b)
        if(revFlag):
            b = (int(b)%2)+1
        
        if(b == 1):
            s.appendleft(c)
        else:
            s.append(c)
            
    #print(_,*s, sep="")

if(revFlag):
    s.reverse()
    
print(*s, sep='')
### BUGGY CODE ###

N,T = map(int,input().split())
AB = [tuple(map(int,input().split())) for i in range(N)]
AB.sort(lambda x:x[0])

dp = [[[-1,-1] for t in range(T)] for i in range(N+1)]
dp[0][0][0] = 0
maxt = 0
for i,(a,b) in enumerate(AB):
    maxt = min(T-1, maxt + a)
    for t in range(maxt, -1,-1):
        for k in range(2):
            dpitk = dp[i][t][k]
            if dpitk < 0: continue
            if dp[i+1][t][k] < dpitk: dp[i+1][t][k] = dpitk
            if t+a < T:
                if dp[i+1][t+a][k] < dpitk + b: dp[i+1][t+a][k] = dpitk + b
            if k==0:
                if dp[i+1][t][1] < dpitk + b: dp[i+1][t][1] = dpitk + b
print(max(a[1] for a in dp[-1]))

### FIXED CODE ###

N,T = map(int,input().split())
AB = [tuple(map(int,input().split())) for i in range(N)]

dp0 = {0:0}
dp1 = {0:0}

for i,(a,b) in enumerate(AB):
    _dp0 = {0:0}
    _dp1 = {0:0}
    for k0,v0 in dp0.items():
        if k0 in _dp0:
            _dp0[k0] = max(_dp0[k0], v0)
        else:
            _dp0[k0] = v0
        if k0+a < T:
            if k0+a in _dp0:
                _dp0[k0+a] = max(_dp0[k0+a], v0+b)
            else:
                _dp0[k0+a] = v0+b
        if k0 in _dp1:
            _dp1[k0] = max(_dp1[k0], v0+b)
        else:
            _dp1[k0] = v0+b
    for k1,v1 in dp1.items():
        if k1 in _dp1:
            _dp1[k1] = max(_dp1[k1], v1)
        else:
            _dp1[k1] = v1
        if k1+a < T:
            if k1+a in _dp1:
                _dp1[k1+a] = max(_dp1[k1+a], v1+b)
            else:
                _dp1[k1+a] = v1+b
    dp0 = _dp0
    dp1 = _dp1

print(max(dp1.values()))
### BUGGY CODE ###

n,m = map(int,input().split())
a = list(range(n+1))
x = 0
for i in range(m,n+2):
    b = sum(a[:i])
    c = sum(a[-i:])
    d = c - b + 1
    x += d
print(x)
    


### FIXED CODE ###

n,k = map(int,input().split())
a = 1
for i in range(k,n+1):
    a += n*i - i**2 + i + 1
print(a%(10**9+7))
### BUGGY CODE ###

import os

import itertools
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

H, W = list(map(int, sys.stdin.readline().split()))
A = [list(sys.stdin.readline().rstrip()) for _ in range(H)]


def ok(h, w):
    return 0 <= h < H and 0 <= w < W and A[h][w] == '.'


nexts = []
for h, w in itertools.product(range(H), range(W)):
    if A[h][w] == '#':
        nexts.append((h, w))

delta = [[0, 1], [0, -1], [1, 0], [-1, 0]]
ans = 0
while nexts:
    nn = []
    for dh, dw in delta:
        for h, w in nexts:
            if ok(h + dh, w + dw):
                A[h + dh][w + dw] = '#'
                nn.append((h + dh, w + dw))
    if not nn:
        break
    ans += 1
    nexts = nn
print(ans)


### FIXED CODE ###

import sys
import numpy as np

sys.setrecursionlimit(10000)
INF = float('inf')

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

counts = np.zeros((H, W))
counts[A == '.'] = np.inf

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

print(int(np.max(counts)))