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

import sys
sys.setrecursionlimit(10000000)
def input():
    return sys.stdin.readline()[:-1]
from bisect import *
from collections import *
from heapq import *
import itertools
import math
INF = 10**9
MOD = 10**9+7

def dfs(v):
    vis[v] = 0
    for u in es[v]:
        if vis[u]:
            k = dfs(u)
            if k != -1:
                return k
            vis[u] = 1
        else:
            return u
    return -1

N, M = map(int, input().split())
es = [[] for i in range(N+1)]
for i in range(M):
    a, b = map(int, input().split())
    es[a-1].append(b-1)
flg = 0
lst = list(range(N))
ans = -1
for i in range(N):
    for w in lst:
        vis = [1] * N
        s = dfs(w)
        if s != -1:
            flg = 1
            dq = deque()
            p = [-1] * N
            for v in es[s]:
                dq.append(v)
                p[v] = s
            while len(dq) > 0:
                v = dq.popleft()
                if v == s:
                    break
                for u in es[v]:
                    if p[u] == -1:
                        dq.append(u)
                        p[u] = v
            tmp = [s]
            v = p[v]
            while v != s:
                tmp.append(v)
                v = p[v]
            if ans == -1 or len(tmp) < len(ans):
                ans = tmp
                lst = tmp[1:]
if flg:
    print(len(ans))
    for x in ans:
        print(x+1)
else:
    print(-1)


### FIXED CODE ###

import sys
sys.setrecursionlimit(10000000)
def input():
    return sys.stdin.readline()[:-1]
from bisect import *
from collections import *
from heapq import *
import itertools
import math
INF = 10**9
MOD = 10**9+7

N, M = map(int, input().split())
es = [[] for i in range(N+1)]
for i in range(M):
    a, b = map(int, input().split())
    es[a].append(b)
ansr, ansd = -1, INF
for r in range(1, N+1):
    d = [INF] * (N+1)
    d[0] = 0
    dq = deque()
    for w in es[r]:
        dq.append(w)
        d[w] = 1
    while len(dq) > 0:
        v = dq.popleft()
        if v == r:
            break
        nd = d[v]+1
        for u in es[v]:
            if nd < d[u]:
                d[u] = nd
                dq.append(u)
    if d[r] < ansd:
        ansd = d[r]
        ansr = r
if ansr == -1:
    print(-1)
else:
    vis = [0] * (N+1)
    vis[0] = 1
    p = [-1] * (N+1)
    dq = deque()
    for v in es[ansr]:
        vis[v] = 1
        p[v] = 0
        dq.append(v)
    while len(dq) > 0:
        v = dq.popleft()
        if v == ansr:
            break
        for u in es[v]:
            if vis[u] == 0:
                vis[u] = 1
                p[u] = v
                dq.append(u)
    lst = []
    v = ansr
    while p[v] != -1:
        lst.append(v)
        v = p[v]
    print(len(lst))
    print(*lst, sep = '\n')
### BUGGY CODE ###

k,s=map(int,input().split())
ans=0
for x in range(k+1):
    for y in range(k+1):
        for z in range(k+1):
            if x+y+z==s:
                ans+=1
print(ans) 

### FIXED CODE ###

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

n = int(input())
p = list(map(int,input().split()))
check = []
for i in range(n):
    for j in range(0,i+1):
        if p[i] > p[j]:
            check.append(i)
            continue
print(n-len(set(check)))

### FIXED CODE ###

n = int(input())
p = list(map(int,input().split()))
ans = 0
mini = n
for i in p:
    if i <= mini:
        ans += 1
        mini = i 
print(ans)
### BUGGY CODE ###

N,K = input().split(" ")
N = int(N)
K = int(K)
p = input().split(" ")
expected_list = []
max_list = []
for i in range(N):
  expected_list.append((int(p[i])+1)/2)
  
for i in range(N):
  anan = 0
  for j in range(K):
    try:
      anan += expected_list[i+j]
    except:
      pass
  max_list.append(anan)
  
print(max(max_list))

### FIXED CODE ###

N,K = input().split(" ")
N = int(N)
K = int(K)
p = input().split(" ")
expected_list = []
max_list = []
for i in range(N):
  expected_list.append((int(p[i])+1)/2)
anan = 0
for j in range(K):
  anan += expected_list[j]
max_list.append(anan)
for i in range(N):
  if i == 0:
    continue
  anan = 0
  try:
    anan = max_list[i-1]-expected_list[i-1]+expected_list[i+K-1]
  except:
    pass
  max_list.append(anan)
  
print(max(max_list))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(1000000)
class Node:
  def __init__(self, n):
    self.number = n
    self.children = []
    self.value = 0
def get_descendants(nodes, dc, i):
  if dc[i] is not None:
    return dc[i]
  dc[i] = []
  dc[i].extend(nodes[i].children)
  for j in nodes[i].children:
    dc[i].extend(get_descendants(nodes, dc, j))
  return dc[i]
n, q = map(int, input().split())
nodes = [Node(i) for i in range(0, n + 1)]
nodes[0] = None
dc = [None for i in range(0, n + 1)]
for i in range(n - 1):
  a, b = map(int, input().split())
  nodes[a].children.append(b)
for _ in range(q):
  p, x = map(int, input().split())
  nodes[p].value += x
  for d in get_descendants(nodes, dc, p):
    nodes[d].value += x
print(' '.join(str(nodes[i].value) for i in range(1, n + 1)))


### FIXED CODE ###

import sys
sys.setrecursionlimit(1000000)
def main():
  _map = map
  _input = input
  _int = int
  def calc_results(results, pvalue, i):
    results[i] = pvalue + values[i]
    for j in childrens[i]:
      calc_results(results, results[i], j)
  n, q = _map(_int, _input().split())
  values = [0] * (n + 1)
  results = [0] * (n + 1)
  childrens = [[] for _ in range(n + 1)]
  for i in range(n - 1):
    a, b = _map(_int, _input().split())
    childrens[a].append(b)
  for _ in range(q):
    p, x = _map(_int, _input().split())
    values[p] += x
  calc_results(results, 0, 1)
  print(*[results[i] for i in range(1, n + 1)])
main()
### BUGGY CODE ###

S = input()
Q = int(input())
Query = [input().split() for i in range(Q)]

ans = S
for query in Query:
    T = query[0]
    if T == '1':
        # Sの前後を反転
        ans = ans[::-1]
    else:
        F = query[1]
        if F == '1':
            # 文字列Sの先頭にCを追加
            ans = query[2] + ans
        else:
            # 文字列Sの末尾にCを追加
            ans = ans + query[2]

print(ans)

### FIXED CODE ###

S = input()
Q = int(input())
Query = [input().split() for i in range(Q)]

mode = True  # True: Normal False: Reverse
pre = []
aft = []
for query in Query:
    if query[0] == '1':
        # モードを反転
        mode = not mode
    else:
        if (mode and (query[1] == '1')) or (not mode and (query[1] == '2')):
            pre.append(query[2])
        else:
            aft.append(query[2])
    
ans = ''.join(pre[::-1]) +  S + ''.join(aft)
    
if not mode:
    ans = ans[::-1]
 
print(ans)
### BUGGY CODE ###

S = input()
N = len(S)
S = list(S)
S.reverse()

dp = [[0]*13 for _ in range(100100)]
dp[0][0] = 1
mod = 10**9+7
for i in range(1, N + 1):
    if S[i-1] == "?":
        for j in range(13):
            for k in range(10):
                dp[i][(j + k*10**(i-1)) % 13] += dp[i-1][j]
    else:
        for j in range(13):
            dp[i][(j+int(S[i-1])*10**(i-1)) % 13] = dp[i-1][j]

    for j in range(13):
        dp[i][j] %= mod

print(dp[N][5])


### FIXED CODE ###

S = input()
N = len(S)
S = list(S)
S.reverse()

dp = [[0]*13 for _ in range(N + 1)]
dp[0][0] = 1
mod = 10**9+7
pow10 = 1
for i in range(1, N + 1):
    if S[i-1] == "?":
        for j in range(13):
            for k in range(10):
                dp[i][(j + k*pow10) % 13] += dp[i-1][j]
    else:
        for j in range(13):
            dp[i][(j+int(S[i-1])*pow10) % 13] = dp[i-1][j]
    pow10 = (pow10 * 10) % 13
    for j in range(13):
        dp[i][j] %= mod

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

N=int(input())
import math
for i in range(1,N+1):
    ans=0
    for x in range(1,33):
        for y in range(1,33):
            if x^2+y^2<1000:
                a=-(3*(x*x)+3*(y*y)+2*x*y)/4+i
                if a>0:
                    b=(math.sqrt(a)-(x+y)/2)
                    if b>0 and b%1==0.0:
                        ans+=1

    print(ans)



### FIXED CODE ###

N=int(input())
li=[0]*N
for x in range(1,101):
    for y in range(1,101):
        for z in range(1,101):
            temp=x**2+y**2+z**2+x*y+y*z+z*x
            if temp<=N:
                li[temp-1]+=1
for i in range(N):
    print(li[i])
### BUGGY CODE ###

import sys

def ev(v):
    return sum(range(1,v+1)) * 1.0/v

N, K = [int(x) for x in sys.stdin.readline().strip().split(" ")]
p = [ev(int(x)) for x in sys.stdin.readline().strip().split(" ")]

m = 0
i = 0
while K+i <= N:
    v = 0
    for k in range(K):
        #v += ev(p[i+k])
        v += p[i+k]
    if m < v:
        m = v
    i += 1
print(m)


### FIXED CODE ###

import sys
 
ma = {}
def _sum(n):
    if not n in ma:
        ma[n] = sum(range(1,n+1))
    return ma[n]

def ev(v):
    return _sum(v) * 1.0/v
 
N, K = [int(x) for x in sys.stdin.readline().strip().split(" ")]
p = [ev(int(x)) for x in sys.stdin.readline().strip().split(" ")]
 

cur = sum([p[i] for i in range(K)])
_max = cur

i = K-1
j = 0

while i < N - 1:
    cur -= p[j]
    i += 1
    j += 1
    cur += p[i]
    if _max < cur:
        _max = cur

print(_max)
### BUGGY CODE ###

# 5 
# 1 1 2 2

# 5人の部下
# 社員番号 2の社員の直属の上司の社員番号が 1, 社員番号 3の社員の直属の上司の社員番号が 1, 社員番号 4の社員の直属の上司の社員番号が 2, 社員番号 5の社員の直属の上司の社員番号が 2,
 

N = int(input())

AnStr = input().split(' ')
zyosiList = []
for v in AnStr:
  zyosiList.append(int(v))

for i in range(1, N + 1):
  print(zyosiList.count(i))

### FIXED CODE ###

N = int(input())

AnStr = input().split(' ')
zyosiList = []
a = {}
for v in AnStr:
  zyosiList.append(int(v))
  if v in a:
    a[v] += 1
  else:
    a[v] = 0

for i in range(1, N + 1):
  if str(i) in a:
    print(a[str(i)]+1)
  else:
    print(0)
### BUGGY CODE ###

import numpy as np
import bisect

n = int(input())
l = np.array(list(map(int, input().split())))

l.sort()

ans = 0
for a in range(n - 2):
    for b in range(a + 1, n - 1):
        ans += bisect.bisect_left(l, l[a] + l[b]) - (b + 1)
print(ans)


### FIXED CODE ###

import numpy as np
import bisect

n = int(input())
l = np.array(list(map(int, input().split())))

# l.sort()

# ans = 0
# for a in range(n - 2):
#     for b in range(a + 1, n - 1):
#         ans += bisect.bisect_left(l, l[a] + l[b]) - (a + 1)
# print(ans)

res = 0
l = sorted(l)
for i in range(1, n - 1):
    b = l[i]
    for j in range(0, i):
        a = l[j]
        res += bisect.bisect_left(l, a + b) - (i + 1)
print(res)
### BUGGY CODE ###

import sys
import copy
n=int(input())
a=[]
for i in range(n):
  a.append(list(map(int,input().split())))

day=0

match=[0 for i in range(n)]
jyunban=[i for i in range(n)]

while True:
  jyunban_n=[]
  day+=1
  check=[True for i in range(n)]
  for i in jyunban:
    if match[i]>=n-1:
      check[i]=False
    if check[i]==False:
      continue
    else:
      vs=a[i][match[i]]-1
      if check[i] and check[vs] and a[i][match[i]]-1==vs and a[vs][match[vs]]-1==i:
        match[i]+=1
        match[vs]+=1
        check[i]=False
        check[vs]=False
        jyunban_n.append(i)
        jyunban_n.append(vs)
      
    if i==jyunban[-1]:
      if not False in check:
        print(-1)
        sys.exit()
  if min(match)==n-1 and min(match)==max(match):
    break
  jyunban=copy.copy(jyunban_n)
        
print(day)


### FIXED CODE ###

import sys
MAX_INT = int(10e9)
MIN_NUM = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()
 
N = I()
a = [IL()[::-1] for i in range(N)]
 
used = [-1]*N
updatelist = [i for i in range(N)]
total = N*(N-1)//2
cnt = 0
days = 0
ul = []
while updatelist:
  ul = []
  for i in updatelist:
    #print(a)
    #print(i+1)
    if len(a[i]) > 0 and used[i] != days:
      numIND = a[i][-1] -1
      #print(numIND+1)
      if a[numIND][-1] == i+1 and used[numIND] != days:
        a[i].pop(-1)
        a[numIND].pop(-1)
        used[i] = days
        used[numIND] = days
        ul.append(i)
        ul.append(numIND)
        cnt += 1
  else:
    updatelist = ul[:]
    if len(ul) != 0:
      days += 1
#print(a)
#print(cnt)
if cnt == total:
  print(days)
else:
  print(-1)
### BUGGY CODE ###

from collections import *
from itertools import *
from bisect import *
from heapq import *
import copy
import math
from fractions import gcd
N=int(input())
A=[list(map(int,input().split())) for i in range(N)]
for i in range(N):
    for m in range(N-1):
        A[i][m]-=1
A=[list(reversed(a)) for a in A]
playerlst=set([i for i in range(N)])

count=0
while playerlst:
    lst=copy.copy(playerlst)
    flag=0
    while lst:
        p=lst.pop()
        p2=A[p][-1]
        if p2 in lst and A[p2][-1]==p:
            flag=1
            A[p].pop()
            A[p2].pop()
            lst.remove(p2)
            for P in [p,p2]:
                if not A[P]:
                    playerlst.remove(P)
    if not flag:
        print(-1)
        exit()
    count+=1
print(count)


### FIXED CODE ###

"""from collections import *
from itertools import *
from bisect import *
from heapq import *

import math
from fractions import gcd"""
import copy
N=int(input())
A=[list(reversed(list(map(int,input().split())))) for i in range(N)]
for i in range(N):
    for m in range(N-1):
        A[i][m]-=1

playerlst=set([i for i in range(N)])

count=0
nlst=copy.copy(playerlst)
while playerlst:
    flag=0
    lst=set()
    playedlst=set()
    while nlst:
        p=nlst.pop()
        if not p in lst and p in playerlst:
            p2=A[p][-1]
            if not p2 in lst and p2 in playerlst:
                if A[p2][-1]==p:
                    flag=1
                    A[p].pop()
                    A[p2].pop()
                    lst.add(p)
                    lst.add(p2)
                    if p2 in nlst:
                        nlst.remove(p2)
                    playedlst.add(p)
                    playedlst.add(p2)
                    if not A[p]:
                        playerlst.remove(p)
                    if not A[p2]:
                        playerlst.remove(p2)
    if not flag:
        print(-1)
        exit()
    count+=1
    nlst=copy.copy(playedlst)
print(count)
### BUGGY CODE ###

import sys
from collections import defaultdict

input = sys.stdin.buffer.readline
N = int(input())
A = list(map(int, input().split()))
MOD = 10**9 + 7

D = defaultdict(int)
for i in range(N - 1):
    for j in range(i + 1, N):
        v = A[i] * A[j] % MOD
        D[v] += 1
# print(D)

ans = 0
for key, item in D.items():
    ans += key * item
    # ans = (ans + (key * item)) % MOD
ans %= MOD
print(ans)


### FIXED CODE ###

import sys
input = sys.stdin.buffer.readline
MOD = 10**9 + 7

N = int(input())
A = [0] + list(map(int, input().split()))

C = [0]
for i in range(1, len(A)):
    C.append(C[-1] + A[i])

ans = 0
for i in range(1, N):
    ans += A[i] * (C[-1] - C[i])

ans %= MOD
print(ans)
### BUGGY CODE ###

n, m = map(int, input().split())
x = []
for i in range(m):
   p, s = map(str, input().split())
   x.append([int(p), s])

y = []
ac = 0
wa = 0
for p, s in x:
   if (s == 'AC' and [p, s] not in y):
      y.append([p, s])
      ac += 1
   elif (s == 'WA' and [p, 'AC'] not in y):
      y.append([p, s])
      wa += 1
print(ac, wa)


### FIXED CODE ###

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

ac = [False] * N
wa = [0] * N
for _ in range(M):
   p, S = input().split()
   p = int(p) - 1
   if (S == 'AC'):
      ac[p] = True
   else:
      if not ac[p]:
         wa[p] += 1

a = 0
b = 0
for i in range(N):
   if ac[i]:
      a += 1
      b += wa[i]
print(*[a, b])
### BUGGY CODE ###

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

ruiA = [0]
ruiB = [0]
for i in range(N):
    ruiA.append(ruiA[-1] + A[i])
for i in range(M):
    ruiB.append(ruiB[-1] + B[i])

MAX = 0
for i in range(N+1):
    for j in range(M+1):
        if ruiA[i] + ruiB[j] <= K and i + j > MAX:
            MAX = i + j

print(MAX)


### FIXED CODE ###

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

ruiA = [0]
ruiB = [0]
for i in range(N):
    ruiA.append(ruiA[-1] + A[i])
for i in range(M):
    ruiB.append(ruiB[-1] + B[i])

MAX = 0
j = M

for i in range(N+1):
    if ruiA[i] > K:
        break
    while ruiA[i] + ruiB[j] > K:
        j -= 1
    MAX = max(MAX, i+j)

print(MAX)
### BUGGY CODE ###

N,M=map(int,input().split())
path=[[False]*N for i in range(N)]
for i in range(M):
  x,y=map(int,input().split())
  path[x-1][y-1]=True
  path[y-1][x-1]=True

minm=[float('inf')]*N
result=[0]*N
flag=[False]*N
minm[0]=0

while True:
  v=-1
  for i in range(N):
    if (not flag[i]) and (v==-1):
      v=i
    elif (not flag[i]) and minm[i]<minm[v]:
      v=i
  if v==-1:
    break
  flag[v]=True
    
  for j in range(N):
    if path[v][j]==True and minm[j]>minm[v]+1:
      minm[j]=minm[v]+1
      result[j]=v+1
      
if float('inf') in minm:
  print('No')
else:
  print('Yes')
  for i in range(N-1):
    print(result[i+1])

### FIXED CODE ###

from collections import deque
N,M=map(int,input().split())
to=[[] for _ in range(N)]
for _ in range(M):
  a,b=map(int,input().split())
  to[a-1].append(b-1)
  to[b-1].append(a-1)

q=deque([0])
r=[None]*N
r[0]=0
while q:
  x=q.popleft()
  for i in to[x]:
    if r[i] is None:
      q.append(i)
      r[i]=x+1
      
print('Yes')
for i in range(N):
  if r[i]!=0:
    print(r[i])
### BUGGY CODE ###

import scipy.misc as scm
N = int(input())
A = [int(i) for i in input().split()]
ca = [A[0]] + [0]*(N-1)

for i in range(1,N):
    ca[i] = ca[i-1] + A[i]

count = 0
for i in list(set(ca)):
    if i == 0:
        count += sum([1 if j == 0 else 0 for j in ca])
    count += scm.comb(
        sum([1 if j == i else 0 for j in ca])
    ,2,1)


print(count)

### FIXED CODE ###

N = int(input())
A = [int(i) for i in input().split()]
ca = [A[0]] + [0]*(N-1)

for i in range(1,N):
    ca[i] = ca[i-1] + A[i]

count = 1
number = 0
number += ca.count(0)
sca = sorted(ca) + ['hoge']
for i in range(1,N+1):
    if sca[i] == sca[i-1]:
        count += 1
    else:
        number += count*(count - 1)/2
        count = 1


print(int(number))
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
b=list(set(a))
c,ans=0,0
for x in b:
  c=a.count(x)
  if c>=int(x):
    ans+=c-int(x)
  else:
    ans+=c
print(ans)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
a.sort()
cnt,ans=0,0
p=0
for x in a:
  if p==x:
    cnt+=1
  else:
    if cnt>p:
      ans+=cnt-p
    elif cnt<p:
      ans+=cnt
    p=x
    cnt=1
if cnt>p:
  ans+=cnt-p
elif cnt<p:
  ans+=cnt
print(ans)
### BUGGY CODE ###

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

ab=[None]*n
for i in range(n):
    ab[i]=tuple(map(int,input().split()))

dp=[float('inf')]*(h+1)

for i in range(1,h+1):
    for a,b in ab:
        if 0 < i-a:
            dp[i]=min(dp[i], dp[i-a]+b)
        else:
            dp[i]=min(dp[i], b)
print(dp[h])

### FIXED CODE ###

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

ab=[None]*n
for i in range(n):
    ab[i]=tuple(map(int,input().split()))

dp=[float('inf')]*(h+1)

for i in range(1,h+1):
    for a,b in ab:
        if 0 < i-a:
            dp[i]=min(dp[i], dp[i-a]+b)
        else:
            dp[i]=min(dp[i], b)
print(dp[h])
### BUGGY CODE ###

n, m = map(int, input().split())
a = [int(input()) for i in range(m)]
if m > n // 2:
  print(0)
else:
  dp = [0] * (n+1)
  dp[0] = 1
  if 1 not in a:
    dp[1] = 1
  for i in range(2, n+1):
    if i not in a:
      dp[i] = dp[i-1] + dp[i-2]
  print(dp[-1]%(10 ** 9 + 7))

### FIXED CODE ###

n, m = map(int, input().split())
a = [int(input()) for i in range(m)]
l = [1] * (n+1)
for j in a:
  l[j] = 0
x = 10 ** 9 + 7
if m > n // 2:
  print(0)
else:
  dp = [0] * (n+1)
  dp[0] = 1
  if 1 not in a:
    dp[1] = 1
  for i in range(2, n+1):
    if l[i]:
      dp[i] = (dp[i-1] + dp[i-2]) % x
  print(dp[-1])
### BUGGY CODE ###

n, a, b = map(int, input().split())
mod = 10**9+7
ans = pow(2, n, mod)-1

modp = mod                     # 素数であることが前提
max_r = 10 ** 7               # 必要分だけ用意する 10**7が限度
factinv = [1, 1] + [0]*max_r  # factinv[n] = ((n!)^(-1) mod modp)
inv = [0, 1] + [0]*max_r      # factinv 計算用

fact = {}

def cmb(n, r, p):
    assert n < p, 'n is less than modp'
    assert r < max_r, 'n in less than max_n'
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    if (n, r) in fact:
        return fact[(n, r)] * factinv[r] % p
    else:
        f = 1
        for i in range(n, n-r, -1):
            f = f * i % p
        fact[(n, r)] = f
        return f * factinv[r] % p

for i in range(2, max_r + 1):
    inv[i] = (-inv[modp % i] * (modp // i)) % modp
    factinv[i] = (factinv[i-1] * inv[i]) % modp

ans-=cmb(n, a, mod)
ans-=cmb(n, b, mod)
print(ans%mod)


### FIXED CODE ###

n, a, b = map(int, input().split())
mod = 10**9+7
ans = pow(2, n, mod)-1

modp = mod

def cmb(n, r, p):
    r = min(r, n-r)
    upper = 1
    for i in range(n, n-r, -1):
        upper = (upper*i)%p
        
    lower = 1
    for i in range(1, r+1):
        lower = (lower*i)%p
    
    # フェルマーの小定理よりp素数ならupper**(p-2)は逆元
    return (upper*pow(lower, p-2, p))%p

ans-=cmb(n, a, mod)
ans-=cmb(n, b, mod)
print(ans%mod)
### BUGGY CODE ###

import itertools
import math
import functools

k = int(input())
li = [i for i in range(1,k+1)]
all_li = list(itertools.product(li, repeat=3))
ans = 0
for a in all_li:
    ans += functools.reduce(math.gcd, a)
print(ans)


### FIXED CODE ###

import math
k = int(input())
count = 0
for i in range(1,k+1):
    for j in range(1,k+1):
        for k in range(1,k+1):
            tmp = math.gcd(i,j)
            count += math.gcd(tmp,k)
print(count)
### BUGGY CODE ###

x = input()
while ("ST" in x):
    x = x.replace("ST", '')
print(len(x))

### FIXED CODE ###

x = input()
ans = []
for i in range(len(x)):
    if (x[i] == "S"):
        ans.append("S")
    else:
        if (len(ans) != 0):
            if (ans[-1] == "S"):
                ans.pop(-1)
            else:
                ans.append("T")
        else:
            ans.append("T")
print(len(ans))
### BUGGY CODE ###

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

dp1 = [[0]*T for _ in range(N+1)]
rev_AB = AB[::-1]
dp2 = [[0]*T for _ in range(N+1)]
for i,(ab,rev_ab) in enumerate(zip(AB,rev_AB),1):
  a = ab[0]
  rev_a = rev_ab[0]
  b = ab[1]
  rev_b = rev_ab[1]
  l_1 = dp1[i-1]
  l_2 = dp2[i-1]
  for t in range(1,T):
    if a>t:
      dp1[i][t]=l_1[t]
      
    else:
      dp1[i][t] = max(l_1[t],l_1[t-a]+b)
      
    if rev_a>t:
      dp2[i][t]=l_2[t]
    
    else:
      dp2[i][t] = max(l_2[t],l_2[t-rev_a]+rev_b)
      
      
    

      
lis = [0]*N
for i in range(1,N+1):
  l_1 = dp1[i-1]
  l_2 = dp2[N-i]
  b = AB[i-1][1]
  for t in range(T):
    lis[i-1] = max(l_1[t]+l_2[T-1-t]+b,lis[i-1])

    
print(max(lis))

### FIXED CODE ###

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

dp1 = [[0]*T for _ in range(N+1)]
rev_AB = AB[::-1]
dp2 = [[0]*T for _ in range(N+1)]
for i,(ab,rev_ab) in enumerate(zip(AB,rev_AB),1):
  a = ab[0]
  rev_a = rev_ab[0]
  b = ab[1]
  rev_b = rev_ab[1]
  l_1 = dp1[i-1]
  l_2 = dp2[i-1]
  for t in range(1,T):
    if a>t:
      dp1[i][t]=l_1[t]
      
    else:
      dp1[i][t] = max(l_1[t],l_1[t-a]+b)
      
    if rev_a>t:
      dp2[i][t]=l_2[t]
    
    else:
      dp2[i][t] = max(l_2[t],l_2[t-rev_a]+rev_b)
      
      
    

      
lis = [0]*N
for i in range(1,N+1):
  l_1 = dp1[i-1]
  l_2 = dp2[N-i]
  b = AB[i-1][1]
  for t in range(T):
    lis[i-1] = max(l_1[t]+l_2[T-1-t]+b,lis[i-1])

    
print(max(lis))