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

N,M=map(int,input().split())
s=list(map(int,input().split()))
t=list(map(int,input().split()))
mod=10**9+7
dp=[[ 0 for i in range(M)] for j in range(N)]
sm=[[ 0 for i in range(M)] for j in range(N)]
s1=0
s2=0
if N>M:
  for i in range(N):
    if t[0]==s[i]:
      dp[i][0]=1
    s1=s1+dp[i][0]
    sm[i][0]=s1
    if i<M:
      if s[0]==t[i]:
        dp[0][i]=1
      s2=s2+dp[0][i]
      sm[0][i]=s2
else:
  for i in range(M):
    if s[0]==t[i]:
      dp[0][i]=1
    s2=s2+dp[0][i]
    sm[0][i]=s2
    if i<N:
      if t[0]==s[i]:
        dp[i][0]=1
      s1=s1+dp[i][0]
      sm[i][0]=s1

for i in range(1,N):
  for j in range(1,M):
    if s[i] != t[j]:
      dp[i][j]=0
    else:
      dp[i][j]=sm[i-1][j-1]+1
    sm[i][j]=sm[i-1][j]+sm[i][j-1]-sm[i-1][j-1]+dp[i][j]
ans=(sm[N-1][M-1]+1)%mod
print(ans)

### FIXED CODE ###

N,M=map(int,input().split())
s=list(map(int,input().split()))
t=list(map(int,input().split()))
mod=10**9+7
sm=[[ 0 for i in range(M)] for j in range(N)]
s1=0
s2=0
if N>M:
  for i in range(N):
    if t[0]==s[i]:
      a=1
    else:
      a=0
    s1=s1+a
    sm[i][0]=s1
    if i<M:
      if s[0]==t[i]:
        a=1
      else:
        a=0
      s2=s2+a
      sm[0][i]=s2
else:
  for i in range(M):
    if s[0]==t[i]:
      a=1
    else:
      a=0
    s2=s2+a
    sm[0][i]=s2
    if i<N:
      if t[0]==s[i]:
        a=1
      else:
        a=0
      s1=s1+a
      sm[i][0]=s1
for i in range(1,N):
  for j in range(1,M):
    if s[i] != t[j]:
      sm[i][j]=(sm[i-1][j]+sm[i][j-1]-sm[i-1][j-1])%mod
    else:
      sm[i][j]=(sm[i-1][j]+sm[i][j-1]-sm[i-1][j-1]+sm[i-1][j-1]+1)%mod
ans=(sm[N-1][M-1]+1)%mod
print(ans)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import collections

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

insuList=[]
warukazu = 2
while (P > 1):
  if P % warukazu == 0:
    P = P / warukazu
    insuList.append(warukazu)
  else:
    warukazu+=1

ans=1
c=collections.Counter(insuList)
for key in c.keys():
  while c[key] >= N:
    ans=ans*key
    c[key] -= N

print(ans)

### FIXED CODE ###

# -*- coding: utf-8 -*-
import collections
import math

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

insuList=[]
warukazu = 2
while (warukazu <= math.sqrt(P) +1):
  if P % warukazu == 0:
    P = P / warukazu
    insuList.append(warukazu)
  else:
    warukazu+=1
insuList.append(P)

ans=1
c=collections.Counter(insuList)
for key in c.keys():
  while c[key] >= N:
    ans=ans*key
    c[key] -= N

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

U = 10**6+2
MOD = 10**6+3
 
fact = [1]*(U+1)
fact_inv = [1]*(U+1)
 
for i in range(1,U+1):
    fact[i] = (fact[i-1]*i)%MOD
fact_inv[U] = pow(fact[U], MOD-2, MOD)
 
for i in range(U,0,-1):
    fact_inv[i-1] = (fact_inv[i]*i)%MOD
 
def perm(n, k):
    if k < 0 or k > n:
        return 0
    z = fact[n]
    z *= fact_inv[n-k]
    z %= MOD
    return z
  
q = int(input())
for _ in range(q):
  x, d, n = map(int, input().split())
  if d == 0:
    ans = pow(x, n, MOD)
  else:
    invd = pow(d, MOD-2, MOD)
    y = x * invd % MOD
    if y == 0 or y > y+n-1:
      ans = 0
    else:
      g = pow(d, n, MOD)
      ans = perm((y+n-1)%MOD, n)*g % MOD
  print(ans)

### FIXED CODE ###

U = 10**6+2
MOD = 10**6+3
 
fact = [1]*(U+1)
fact_inv = [1]*(U+1)
 
for i in range(1,U+1):
    fact[i] = (fact[i-1]*i)%MOD
fact_inv[U] = pow(fact[U], MOD-2, MOD)
 
for i in range(U,0,-1):
    fact_inv[i-1] = (fact_inv[i]*i)%MOD
 
def perm(n, k):
    if k < 0 or k > n:
        return 0
    z = fact[n]
    z *= fact_inv[n-k]
    z %= MOD
    return z
  
q = int(input())
for _ in range(q):
  x, d, n = map(int, input().split())
  if d == 0:
    ans = pow(x, n, MOD)
  else:
    invd = pow(d, MOD-2, MOD)
    y = x * invd % MOD
    if y == 0 or y > y+n-1:
      ans = 0
    else:
      g = pow(d, n, MOD)
      ans = perm((y+n-1)%MOD, n)*g % MOD
  print(ans)
### BUGGY CODE ###

N=int(input())
A=list(map(int,input().split()))
B=[A[0]]
for i in range(1,N):
  B.append(B[-1]+A[i])
B = [0]+B

cnt =0
for i in range(N+1):
  for j in range(i):
    #print(j,i,B[i]-B[j])
    if B[i]==B[j]:
      cnt +=1
      
print(cnt)

### FIXED CODE ###

from collections import Counter

N=int(input())
A=list(map(int,input().split()))
B=[A[0]]
for i in range(1,N):
  B.append(B[-1]+A[i])
B = [0]+B
ans=0

d=dict(Counter(B))
for num in d:
  ans += d[num]*(d[num]-1)//2
  
print(ans)
### BUGGY CODE ###

x=int(input())
a=b=c=d=e=f=0
flag=False
for a in range(x//100+1):
  for b in range(x//101+1):
    for c in range(x//102+1):
      for d in range(x//103+1):
        for e in range(x//104+1):
          for f in range(x//105+1):
            if a*100+b*101+c*102+d*103+e*104+f*105==x:
              flag=True
              print(1)
              break
          if flag:
            break
        if flag:
          break
      if flag:
        break
    if flag:
      break
  if flag:
    break
if flag==False:
  print(0)

### FIXED CODE ###

x=int(input())
y=1  # y個購入すると題意をみたす時、1<=y<=x//100、実際に支払い可能な金額は100＊y〜105＊y
if x<100:
  print(0)
else:
  while y<=x//100+1:
    if y*100<=x<=y*105:
      print(1)
      break
    elif y>x//100:
      print(0)
      break
    else:
      y+=1
### BUGGY CODE ###


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

    dp = [[[0 for i in range(2)]for i in range(n+2)] for i in range(n+2)]
    # dp [start][end][chance] is the diffence between X and Y 
    # such for range start to end with the current chance of player
    for start in range(n, 0, -1):
        for end in range(start, n+1):
            for chance in range(2):
                temp = -1 if chance else 1
                val1 = a[start-1]*temp + dp[start+1][end][chance ^ 1]
                val2 = a[end-1]*temp + dp[start][end-1][chance ^ 1]
                dp[start][end][chance] = min(
                    val1, val2) if chance else max(val1, val2)
    print(dp[1][n][0])


if __name__ == "__main__":
    main()


### FIXED CODE ###


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

    dp = [[0 for i in range(n+2)]for i in range(n+2)]
    # dp [start][end] is the diffence between X and Y
    # such for range start to end
    for start in range(n, 0, -1):
        for end in range(start, n+1):
            if start == end:
                dp[start][end] = a[start-1]
            else:
                dp[start][end] = max(a[start-1]-dp[start+1]
                                     [end], a[end-1]-dp[start][end-1])
    print(dp[1][n])


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

from collections import Counter,defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue
sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))


n = inp()
a = inpl()
ans = 0
a.sort()
for i in range(n-2):
    for j in range(i+1,n-1):
        for k in range(j+1,n):
            if a[k] < a[j] + a[i]:
                ans += 1

print(ans)


### FIXED CODE ###

from collections import Counter,defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue
sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

n = inp()
a = inpl()
ans = 0
a.sort()
for i in range(n-2):
    for j in range(i+1,n-1):
        b = a[j+1:]
        tmp = a[i] + a[j] - 1
        tt = bisect.bisect_right(b,tmp)
        if tt > 0 :
            ans += tt
print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(700000)
N, Q = map(int, input().split())
d = [[] for i in range(N)]

for i in range(N-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    d[b].append(a)
    d[a].append(b)

ans = [0]*N

for i in range(Q):
    p, x = map(int, input().split())
    p -= 1
    ans[p] += x

def dfs(cur, parent):
    for child in d[cur]:
        if child != parent:
            ans[child] += ans[cur]
            dfs(child,cur)
dfs(0,-1) 

print(*ans)

### FIXED CODE ###

N, Q = map(int, input().split())
d = [0 for i in range(N)]

for i in range(N-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    d[b] = a
ans = [0 for i in range(N)]

for i in range(Q):
    p, x = map(int, input().split())
    p -= 1
    ans[p] += x

for i in range(1, N):
    ans[i] += ans[d[i]]

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

n,m = map(int,input().split())
s = list(input())
abli = [tuple(map(int,input().split())) for i in range(m)]

def addEdge(graph,u,v):
    graph[u].append(v)


def adjAB(graph,node):
    Aflag =False
    Bflag =False
    for i in graph[node]:
        if s[i-1]=='A':
            Aflag = True
        if s[i-1]=='B':
            Bflag = True
        if Aflag and Bflag:
            break
    if Aflag and Bflag:
        return(True)
    else:
        return(False)


def deleteNode(graph,node):
    graph.pop(node,None)
    s[node-1] = 'C'
        


from collections import defaultdict
graphAB = defaultdict(list)

for i,j in abli:
    addEdge(graphAB,i,j)
    if i != j:
        addEdge(graphAB,j,i)


visitset = set(graphAB.keys())
deleteset=set()

while bool(visitset):
    i = visitset.pop()
    #print(i,visitset)
    if not adjAB(graphAB,i):
        deleteset.add(i)
        #print(i)
        tmp = set(graphAB[i])
        visitset = (visitset | tmp) - deleteset
        deleteNode(graphAB,i)




if graphAB == {}:
    print('No')
else:
    print('Yes')





### FIXED CODE ###

#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#

"""
GC027 C
"""

n,m = map(int,input().split())
s = list(input())
edges = [tuple(map(int,input().split())) for i in range(m)]
ali = [0 for i in range(n)]
bli = [0 for i in range(n)]


def addEdge(graph,u,v):
    graph[u].add(v)


from collections import defaultdict
graphAB = defaultdict(set)

def incrementAB(node,adj):
    if s[adj-1] == 'A':
        ali[node-1]+=1
    if s[adj-1] == 'B':
        bli[node-1]+=1

def decrementAB(node,adj):
    if s[adj-1] == 'A':
        ali[node-1]-=1
    if s[adj-1] == 'B':
        bli[node-1]-=1

for i,j in edges:
    addEdge(graphAB,i,j)
    addEdge(graphAB,j,i)

def adjAB(node):
    if ali[node-1]!=0 and bli[node-1]!=0:
        return(True)
    else:
        return(False)

graphvers = set(graphAB.keys())
visitset = set()
for i in range(1,n+1):
    if not i in graphvers:
        s[i-1] = 'C'
    else:
        for j in graphAB[i]:
            incrementAB(i,j)
        if not adjAB(i):
            visitset.add(i)


while bool(visitset):
    #print(graphAB)
    #print(graphABopp)
    #print(abli)
    i = visitset.pop()
    for j in graphAB[i]:
        if s[j-1] != 'C':
            decrementAB(j,i)
            if not adjAB(j):
                visitset.add(j)
    s[i-1] = 'C'

#print(graphAB)
#print(graphABopp)

sset= set(s)
sset.add('C')
sset.remove('C')
if bool(sset):
    print('Yes')
else:
    print('No')
### BUGGY CODE ###

# 逆元
# a^n mod を計算する
def modpow(a, n, mod):
    res = 1
    while n > 0:
        if n & 1:
            res = res * a % mod
        a = a * a % mod
        n >>= 1
    return res

# a^{-1} mod を計算する
def modinv(a, mod):
    return modpow(a, mod - 2, mod)


x, y = map(int, input().split())

mod = 10 ** 9 + 7

if (x + y) % 3 == 0 and min(x, y) * 2 >= max(x, y):
    a = (2 * y - x) // 3
    b = (2 * x - y) // 3
    x = 1
    for i in range(2, a + b + 1):
        x = x * i % mod
    for i in range(2, a + 1):
        x = x * modinv(i, mod) % mod
    for i in range(2, b + 1):
        x = x * modinv(i, mod) % mod
    print(x)
else:
    print(0)

### FIXED CODE ###

# 互いに素なa,bについて、a*x+b*y=1の一つの解
def extgcd(a, b):
    r = [1, 0, a]
    w = [0, 1, b]
    while w[2] != 1:
        q = r[2] // w[2]
        r2 = w
        w2 = [r[0] - q * w[0], r[1] - q * w[1], r[2] - q * w[2]]
        r = r2
        w = w2
    # [x,y]
    return [w[0], w[1]]


# aの逆元(mod m)を求める。(aとmは互いに素であることが前提)
def mod_inv(a, m):
    x = extgcd(a, m)[0]
    return (m + x % m) % m


x, y = map(int, input().split())

mod = 10 ** 9 + 7

if (x + y) % 3 == 0 and min(x, y) * 2 >= max(x, y):
    a = (2 * y - x) // 3
    b = (2 * x - y) // 3
    x = 1
    for i in range(2, a + b + 1):
        x = x * i % mod
    for i in range(2, a + 1):
        x = x * mod_inv(i, mod) % mod
    for i in range(2, b + 1):
        x = x * mod_inv(i, mod) % mod
    print(x)
else:
    print(0)
### BUGGY CODE ###

r, g, b, n = map(int, input().split())

ans = 0
for i in range(n // r + 1):
    for j in range((n - i * r) // g + 1):
        if i * r + j * g > n:
            break
        k = n - (i * r + j * g)

        if k % b == 0:
            ans += 1

print(ans)

### FIXED CODE ###

r, g, b, n = map(int, input().split())

ans = 0
for i in range(n // r + 1):
    for j in range((n - i * r) // g + 1):
        k = n - (i * r + j * g)
        if k % b == 0:
            ans += 1

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

from collections import Counter
 
def main():
    s = list(map(int,input()[::-1]))
 
    t = []
    m = 0
    for i,s_i in enumerate(s):
        m = m+s_i*10**i
        t.append(m%2019)
    
    c = Counter(t)
    ans = c[0]
    for i in c.values():
 
        ans += i*(i-1)//2
    print(ans)
 
if __name__ == "__main__":
    main()

### FIXED CODE ###

from collections import Counter

def main():
    s = list(map(int,input()[::-1]))

    t = []
    m = 0
    for i,s_i in enumerate(s):
        m = m+s_i*pow(10,i,2019)
        t.append(m%2019)
    
    c = Counter(t)
    ans = c[0]
    for i in c.values():

        ans += i*(i-1)//2
    print(ans)

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

n,m,k=map(int,input().split())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
aa=[0]
bb=[0]
a_sum=0
b_sum=0

for i in range(n):
    if (a_sum+a[i])<=k:
        a_sum+=a[i]
        aa.append(a_sum)
    else:
        break
for i in range(m):
    if (b_sum+b[i])<=k:
        b_sum+=b[i]
        bb.append(b_sum)
    else:
        break

#print(aa)
#print(bb)
cnt=0
for i in range(len(aa)):
    for j in range(len(bb)):
        if (aa[i]+bb[j])<=k:
            cnt=max(cnt,i+j)
print(cnt)


### FIXED CODE ###

n,m,k=map(int,input().split())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
aa=[0]
bb=[0]
a_sum=0
b_sum=0

for i in range(n):
    if (a_sum+a[i])<=k:
        a_sum+=a[i]
        aa.append(a_sum)
    else:
        break
for i in range(m):
    if (b_sum+b[i])<=k:
        b_sum+=b[i]
        bb.append(b_sum)
    else:
        break

#print(aa)
#print(bb)
cnt=len(bb)-1
ans=0
for i in range(len(aa)):
    for j in range(cnt,-1,-1):
        if bb[j]<=(k-aa[i]):
            cnt=j
            ans=max(ans,(i+j))
            break
print(ans)
### BUGGY CODE ###

x, k, d = map(int, input().split())

for i in range(k):
    if abs(x+d) < abs(x-d):
        if abs(x)<abs(x+d):
            if (k-i)%2 == 0:
                break;
            else:
                x = x+d
                break
        x = x+d
    else:
        if abs(x)<abs(x-d):
            if (k-i)%2 == 0:
                break;
            else:
                x = x-d
                break
        x = x-d
print(abs(x))

### FIXED CODE ###

x, k, d = map(int, input().split())
x = abs(x)
s = int(x/d)
ans = x%d

if k < s:
    print(x-d*k)
else:
    if ans < -ans+d:
        if (k-s)%2 == 0:
            print(ans)
        else:
            print(-ans+d)
    else:
        if (k-s)%2 == 0:
            print(ans)
        else:
            print(-ans+d)
### BUGGY CODE ###

N = int(input())
results = []
for i in range(1,N):
    for j in range(1,N):
        if i+j == N:
            si = str(i)
            sj = str(j)
            count1 = 0
            for x in si:
                count1 += int(x)
            for y in sj:
                count1 += int(y)
            results.append(count1)
print(min(results))

### FIXED CODE ###

N = int(input())
results = []
for i in range(1,N):
    results.append(sum(map(int,str(i))) + sum(map(int,str(N-i))))
print(min(results))
### BUGGY CODE ###

from collections import deque
import sys

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

flag = [ [False] * N for i in range(N) ]
crash = [False] * N
cost = [float("-inf")] * N
cost[0] = 0

dic = {}
for i in range(N):
    dic[i] = []

    

for i in range(M):

    A,B,C = map(int,input().split())
    A -= 1
    B -= 1

    dic[A].append([B,C-P])

q = deque([0])

cnt = 0

while len(q) > 0:

    now = q.popleft()

    for bc in dic[now]:
    
        b = bc[0]
        c = bc[1]

        #print (now,b,flag[now],crash[now],flag[b],crash[b])

        if b == N-1 and crash[now]:
            print (-1)
            sys.exit()

        if cost[now] + c > cost[b]:


            if flag[now][b] and not crash[b]:

                crash[b] = True

                cost[b] = cost[now] + c

                flag[b] = flag[now].copy()
                flag[b][b] = True
            
                q.append(b)

            elif not flag[now][b]:
                
                cost[b] = cost[now] + c
                crash[b] = crash[now]
                cost[b] = cost[now] + c
                crash[b] = crash[now]

                flag[b] = flag[now].copy()
                flag[b][b] = True

                q.append(b)

    cnt += 1

    if cnt > M * N:
        print (-1)
        sys.exit()

print (max(0,cost[N-1]))
    

### FIXED CODE ###


"""

https://atcoder.jp/contests/abc137/tasks/abc137_e

辺の重みからPを引いておく
→あとはベルマンフォード？

正の閉路探索→むずくね？
閉路があったとしても、増えなきゃあっていい…

→まずゴールにたどり着ける頂点を列挙
→たどり着けない点は無意味なのでremove

→あとはベルマンフォード
"""

import sys
sys.setrecursionlimit(200000)

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

lis = [ [] for i in range(N) ]
rev = [ [] for i in range(N) ]
exist = [False] * N

for i in range(M):

    A,B,C = map(int,input().split())
    A -= 1
    B -= 1

    lis[A].append([B , C - P])
    rev[B].append(A)

def dfs(v):

    exist[v] = True
    for nex in rev[v]:
        if not exist[nex]:
            dfs(nex)

dfs(N-1)

dis = [float("-inf")] * N
dis[0] = 0

for i in range(N+1):

    flag = False

    for v in range(N):
        for uc in lis[v]:

            if exist[uc[0]] and dis[uc[0]] < dis[v] + uc[1]:
                #print (uc[0] , dis[v] + uc[1])
                dis[uc[0]] = dis[v] + uc[1]
                flag = True

if flag:
    print (-1)
else:
    print (max( 0 , dis[N-1] ))
### BUGGY CODE ###

import sys
import math
import itertools
import collections
import heapq
import re
import numpy as np
from functools import reduce

rr = lambda: sys.stdin.readline().rstrip()
rs = lambda: sys.stdin.readline().split()
ri = lambda: int(sys.stdin.readline())
rm = lambda: map(int, sys.stdin.readline().split())
rl = lambda: list(map(int, sys.stdin.readline().split()))
inf = float('inf')
mod = 10**9 + 7

k, s = rm()
cnt = 0
for x in range(k, -1, -1):
    for y in range(k, -1, -1):
        for z in range(k, -1, -1):
            if x+y+z == s:
                cnt += 1
print(cnt)















### FIXED CODE ###

import sys
import math
import itertools
import collections
import heapq
import re
import numpy as np
from functools import reduce

rr = lambda: sys.stdin.readline().rstrip()
rs = lambda: sys.stdin.readline().split()
ri = lambda: int(sys.stdin.readline())
rm = lambda: map(int, sys.stdin.readline().split())
rl = lambda: list(map(int, sys.stdin.readline().split()))
inf = float('inf')
mod = 10**9 + 7

k, s = rm()
cnt = 0
for x in range(k, -1, -1):
    for y in range(k, -1, -1):
        if 0 <= s-x-y <= k:
            cnt += 1
print(cnt)
### BUGGY CODE ###

import sys
from functools import lru_cache


def main():
    N = int(input())
    P = tuple(map(int, input().split()))

    Kcost = [0] * (N * N)
    for sn in range(N * N):
        row, clm = divmod(sn, N)
        Kcost[sn] = min(row, N - row - 1, clm, N - clm - 1)

    Sitting = [1] * (N * N)
    Kcount = 0


    #@lru_cache(maxsize=None)
    def Kcheck(csn, qsn, cdsn):
        if Kcost[cdsn] > Kcost[qsn] + Sitting[qsn]:
            Kcost[cdsn] = Kcost[qsn] + Sitting[qsn]
            queue.append(cdsn)


    for sn in P:
        csn = sn - 1
        Kcount += Kcost[csn]
        Sitting[csn] = 0
        queue = [csn]

        while queue:
            qsn = queue.pop()
            for dsn in (1, -1, N, -N):
                div, mod = divmod(qsn, N)
                if mod == 0 and dsn == -1: continue
                if mod == N - 1 and dsn == 1: continue
                if div == 0 and dsn == -N: continue
                if div == N - 1 and dsn == N: continue

                Kcheck(csn, qsn, qsn + dsn)

    print(Kcount)


if __name__ == '__main__':
    main()

sys.exit()


### FIXED CODE ###

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

Kcost = [min(row, N - 1 - row, clm, N - 1 - clm) for row in range(N) for clm in range(N)]

Sitting = [1] * (N * N)
Kcount = 0


def Kcheck(qsn, cdsn):
    if Kcost[cdsn] > Kcost[qsn] + Sitting[qsn]:
        Kcost[cdsn] = Kcost[qsn] + Sitting[qsn]
        queue.append(cdsn)


for sn in P:
    csn = sn - 1
    Kcount += Kcost[csn]
    Sitting[csn] = 0
    queue = [csn]

    while queue:
        qsn = queue.pop()
        div, mod = divmod(qsn, N)
        if mod: Kcheck(qsn, qsn - 1)
        if mod != N - 1: Kcheck(qsn, qsn + 1)
        if div: Kcheck(qsn, qsn - N)
        if div != N - 1: Kcheck(qsn, qsn + N)

print(Kcount)
### BUGGY CODE ###

# -*- coding: utf-8 -*-

from collections import deque

X,Y,A,B,C = map(int, input().split())
P = list(map(int, input().split()))
Q = list(map(int, input().split()))
R = list(map(int, input().split()))

def sort(L):
  if len(L)==1:
    return L
  left = sort(L[:len(L)//2])
  right = sort(L[len(L)//2:])
  result = []
  left.append(-1)
  right.append(-1)
  left_index = 0
  right_index = 0
  while len(result)<len(L):
    if left[left_index]>=right[right_index]:
      result.append(left[left_index])
      left_index += 1
    else:
      result.append(right[right_index])
      right_index += 1
  return result

P = sort(P)[:X]
Q = sort(Q)[:Y]
R = sort(P+Q+R)[:X+Y]
print(sum(R))

### FIXED CODE ###

# -*- coding: utf-8 -*-

from collections import deque

X,Y,A,B,C = map(int, input().split())
P = list(map(int, input().split()))
Q = list(map(int, input().split()))
R = list(map(int, input().split()))

def sort(L):
  if len(L)==1:
    return L
  left = sort(L[:len(L)//2])
  right = sort(L[len(L)//2:])
  result = []
  left.append(-1)
  right.append(-1)
  left_index = 0
  right_index = 0
  while len(result)<len(L):
    if left[left_index]>=right[right_index]:
      result.append(left[left_index])
      left_index += 1
    else:
      result.append(right[right_index])
      right_index += 1
  return result

P = sort(P)[:X]
Q = sort(Q)[:Y]
R = sort(R)

P_index = X-1
Q_index = Y-1
R_index = 0

while True:
  if P[P_index] <= Q[Q_index] and R[R_index]>P[P_index]:
    P[P_index] = R[R_index]
    P_index = max(0, P_index-1)
    R_index += 1
  elif P[P_index] > Q[Q_index] and R[R_index]>Q[Q_index]:
    Q[Q_index] = R[R_index]
    Q_index = max(0, Q_index-1)
    R_index += 1
  else:
    break
  if R_index>=len(R):
    break

print(sum(P)+sum(Q))
### BUGGY CODE ###

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

INF = 10**11 + 1
dp = [[INF]*(10**5 + 1) for _ in range(N+1)]
dp[0][0] = 0

for i in range(N):
  w, v = map(int, input().split())
  for j in range(10**5 + 1):
    dp[i+1][j] = min(dp[i][j], dp[i][max(0, j-v)] + w)

ans = 0
    
for i, x in enumerate(dp[-1]):
  if x <= W:
    ans = i

print(ans)

### FIXED CODE ###

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

INF = 10**11 + 1
dp = [[INF]*(10**5 + 1) for _ in range(N+1)]
dp[0][0] = 0

for i in range(N):
  w, v = map(int, input().split())
  for j in range(10**5 + 1):
    dp[i+1][j] = min(dp[i][j], dp[i][max(0, j-v)] + w)

ans = 0
    
for i, x in enumerate(dp[-1]):
  if x <= W:
    ans = i

print(ans)