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

H, W = map(int, input().split())
s = []
ans = 0

for i in range(H):
    s.append(input())

def getCount(h, w):
    if s[h][w] == '#':
        return 0
    cnt = 0

    if s[h][w] == '.':
        cnt += 1

    # to right
    for i in range(w+1, W):
        if s[h][i] == '.':
            cnt += 1
        else:
            break

    # to left
    #if w > 0:
    #for i in range(w - 1, -1, -1):
    for i in reversed(range(w)):
        if s[h][i] == '.':
            cnt += 1
        else:
            break

    # to down
    for i in range(h+1, H):
        if s[i][w] == '.':
            cnt += 1
        else:
            break

    # to up
    for i in reversed(range(h)):
        if s[i][w] == '.':
            cnt += 1
        else:
            break

    return cnt

for i in range(H):
    for j in range(W):
        ans = max(ans, getCount(i, j))

print(ans)


### FIXED CODE ###

H, W = map(int, input().split())
s, ans = [], 0
dpr = [[0] * W for _ in range(H)]
dpl = [[0] * W for _ in range(H)]
dpd = [[0] * W for _ in range(H)]
dpu = [[0] * W for _ in range(H)]

for i in range(H):
    s.append(input())

# to right
for i in range(H):
    for j in reversed(range(W)):
        if j == W-1 and s[i][j] == '.':
            dpr[i][j] = 1
        elif s[i][j] == '#':
            dpr[i][j] = 0
        else:
            dpr[i][j] = dpr[i][j+1] + 1

# to left
for i in range(H):
    for j in range(0, W):
        if j == 0 and s[i][j] == '.':
            dpl[i][j] = 1
        elif s[i][j] == '#':
            dpl[i][j] = 0
        else:
            dpl[i][j] = dpl[i][j-1] + 1

# to down
for i in reversed(range(H)):
    for j in range(W):
        if i == H-1 and s[i][j] == '.':
            dpd[i][j] = 1
        elif s[i][j] == '#':
            dpd[i][j] = 0
        else:
            dpd[i][j] = dpd[i+1][j] + 1

# to up
for i in range(0, H):
    for j in range(W):
        if i == 0 and s[i][j] == '.':
            dpu[i][j] = 1
        elif s[i][j] == '#':
            dpu[i][j] = 0
        else:
            dpu[i][j] = dpu[i-1][j] + 1

for i in reversed(range(H)):
    for j in reversed(range(W)):
        cnt = dpr[i][j] + dpl[i][j] + dpd[i][j] + dpu[i][j] - 3
        ans = max(ans, cnt)

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

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

    d = [a[i] - a[i-1] for i in range(1, n)]
    d.insert(0, a[0])
    d.append(k - a[-1])

    d = tuple(d)

    most_min_path = 10000

    for i in range(n):
        if i == 0:
            normal_ck = sum(d) - d[i] - d[-1]
            reverse_ck = sum(d) - d[i+1]
        elif i == n - 1:
            normal_ck = sum(d) - d[i]
            reverse_ck = sum(d) - d[i+1] - d[0]
        else:
            normal_ck = sum(d) - d[i]
            reverse_ck = sum(d) - d[i+1]

        min_ck = normal_ck if normal_ck < reverse_ck else reverse_ck
        if most_min_path > min_ck:
            most_min_path = min_ck

    print(most_min_path)


if __name__ == '__main__':
    main()

### FIXED CODE ###

k, n = map(int, input().split())
a = list(map(int, input().split()))
a.append(a[0] + k)

d = [a[i+1] - a[i] for i in range(n)]
l = 0
for i in range(n):
    l = max(l, a[i+1] - a[i])
print(k - l)
### BUGGY CODE ###

#! /usr/bin/env python3

s = input()
k = int(input())

alphabets = 'abcdefghijklmnopqrstuvwxyz'

dic = []

for char in alphabets:
    
    index = 0
    ss = []
    while index != -1:
        index = s.find(char, index)

        if index != -1:
            ss.append(s[index:])
            index += 1

    if  len(ss) > 0:
        ss.sort()
        for x in ss:
            for i in range(len(x)):
                if x[0:i+1] not in dic:
                    dic.append(x[0:i+1])
                    if len(dic) >= k:
                        break
        if len(dic) >= k:
            break

print(dic[k-1])


### FIXED CODE ###

#! /usr/bin/env python3

s = input()
k = int(input())

alphabets = 'abcdefghijklmnopqrstuvwxyz'

dic = []

for char in alphabets:
    
    index = 0
    ss = []
    while index != -1:
        index = s.find(char, index)

        if index != -1:
            tmp = s[index:index + 5]
            isSubstring = False
            for sss in ss:
                if sss.find(tmp) == 0:
                    isSubstring = True
                    break
            if isSubstring == False:
                ss.append(tmp)

            index += 1

    if  len(ss) > 0:
        ss.sort()
        for x in ss:
            for i in range(len(x)):
                if x[0:i+1] not in dic:
                    dic.append(x[0:i+1])
                    if len(dic) >= k:
                        break
        if len(dic) >= k:
            break

print(dic[k-1])
### BUGGY CODE ###

N = int(input())
a=[int(i) for i in input().split()]

sum_a=sum(a)
ans = 10**11
for i in range(N-1):
    x = abs(sum_a - 2 * sum(a[:i+1]))
    if x<ans:
        ans=x


print(ans)


### FIXED CODE ###

N = int(input())
a=[int(i) for i in input().split()]

sum_a=sum(a)
ans = 10**11
x=0
for i in range(N-1):
    x += a[i]
    diff = abs(sum_a - 2 * x)
    if diff<ans:
        ans=diff


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

n = int(input())
red_point_list = [[int(j) for j in input().split()] for i in range(n)]
blue_point_list = [[int(j) for j in input().split()] for i in range(n)]

px = red_point_list[0][0]
py = red_point_list[0][1]

tmp = []
for i, p in enumerate(blue_point_list):
    if px < p[0] and py < p[1]:
        new_blue_points = blue_point_list.copy()
        new_blue_points.pop(i)
        tmp.append((1, new_blue_points))

if len(tmp) == 0:
    tmp = [(0, blue_point_list)]

for a, b in red_point_list[1:]:
    new_tmp = []
    for count, blue_points in tmp:
        for i, p in enumerate(blue_points):
            if a < p[0] and b < p[1]:
                new_blue_points = blue_points.copy()
                new_blue_points.pop(i)
                new_tmp.append((count+1, new_blue_points))
            else:
                new_tmp.append((count, blue_points))
    tmp = new_tmp

print(max(tmp, key=lambda x: x[0])[0])


### FIXED CODE ###

n = int(input())
red_point_list = [[int(j) for j in input().split()] for i in range(n)]
blue_point_list = [[int(j) for j in input().split()] for i in range(n)]

count = 0
for c, d in sorted(blue_point_list, key=lambda x: x[0]):
    tmp_index = 0
    tmp_y = -1
    for i, p in enumerate(red_point_list):
        if c > p[0] and d > p[1]:
            if p[1] >= tmp_y:
                tmp_index = i
                tmp_y = p[1]

    if tmp_y > -1:
        count += 1
        red_point_list.pop(tmp_index)

print(count)
### BUGGY CODE ###

def triples(N):
  _ = 0
  if N < 2:
    pass
  else:
    limit = (N - 2) ** (1 / 2)
    for x in range(1,int(limit) + 1):
      for y in range(1,int(limit) + 1):
        for z in range(1,int(limit) + 1):
          if (x + y) ** 2 + (y + z) ** 2 + (z + x) ** 2 == 2 * N:
            _ += 1
  return _

N = int(input())
for n in range(1,N + 1):
  print(triples(n))

### FIXED CODE ###

N = int(input())
L = [0] * N
for x in range(1,101):
  for y in range(1,101):
    for z in range(1,101):
      n = int(((x + y) ** 2 + (y + z) ** 2 + (z + x) ** 2)/ 2 )
      if n <= N:
        L[n - 1] += 1
print(*L, sep='\n')
### BUGGY CODE ###

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

# １からNまでの値をもつサイコロを振ったときの期待値
def ex(x:int):
    return (x*(x+1)/2)/x

# 期待値のリストを作る
kitaichi = []
kitaichi_goukei = []
for i in range(len(p)):
    kitaichi.append(ex(p[i]))
    if i+1 >= k:
        kitaichi_goukei.append(sum(kitaichi[i+1-k:i+1]))
print (max(kitaichi_goukei))

### FIXED CODE ###

N,K = map(int,input().split())
p = list(map(int,input().split()))
ex = [1/2*(i+1) for i in p]
total = [0]

for i in range(N):
    total.append (total[i] + ex[i])

ans = 0
for i in range(N+1-K):
    tmp = total[i+K] - total[i]
    if ans < tmp:
        ans = tmp

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

import math

N=int(input())
A=[0]*N
for i in range(N):
  A[i] = int(input())

S = sum(A)
dp = [[0 for i in range(S+1)] for j in range(N+1)]
dp[0][0]=1
for i in range(1,N+1):
  for j in range(S+1):
    if A[i-1] <= j:
      dp[i][j] = dp[i-1][j-A[i-1]] + (dp[i-1][j]*2)
    else:
      dp[i][j] = dp[i-1][j]*2
bad_r = sum(dp[N][math.ceil(S/2):S+1])

if S%2 == 0:  
  dp2 = [[0 for i in range(S+1)] for j in range(N+1)]
  dp2[0][0]=1
  for i in range(1,N+1):
    for j in range(S+1):
      if A[i-1] <= j:
        dp2[i][j] = dp2[i-1][j-A[i-1]] + dp2[i-1][j]
      else:
        dp2[i][j] = dp2[i-1][j]
  bad_rg = dp2[N][int(S/2)]
else:
  bad_rg = 0
  
ans = 3**N - bad_r*3 + bad_rg*3
print(ans%998244353)

### FIXED CODE ###

import sys
import math

input = sys.stdin.readline
N=int(input())
A = [int(input()) for i in range(N)]
mod = 998244353

S = sum(A)
maxA = max(A)
dp = [[0]*(S+1+maxA-math.ceil(S/2)) for j in range(N+1)]
dp[0][S-math.ceil(S/2)]=1
for i in range(1,N+1):
  for j in range(S+1-math.ceil(S/2)):
    dp[i][j] = (dp[i-1][j+A[i-1]]*2 + dp[i-1][j])%mod
bad_r = sum(dp[N])

if S%2 == 0:
  dp2 = [[0]*(S+1+maxA-math.ceil(S/2)) for j in range(N+1)]
  dp2[0][S-math.ceil(S/2)]=1
  for i in range(1,N+1):
    for j in range(S+1-math.ceil(S/2)):
      dp2[i][j] = (dp2[i-1][j+A[i-1]] + dp2[i-1][j])%mod
  bad_rg = dp2[N][0]
else:
  bad_rg = 0
  
ans = 3**N - bad_r*3 + bad_rg*3
print(ans%mod)
### BUGGY CODE ###

n, k = map(int,input().split())
weight = []
for i in range(n):
    weight.append(int(input()))
tmp_numberOfGroup = 0
tmp_p = max(weight) - 1
while tmp_numberOfGroup+1 != k:
    tmp_p += 1
    tmp_weight = 0
    tmp_numberOfGroup = 0
    for tmp_w in weight:
        if tmp_w+tmp_weight > tmp_p:
            tmp_numberOfGroup += 1
            tmp_weight = tmp_w
        else:
            tmp_weight += tmp_w

if k == 1:
    tmp_p = sum(weight)

print(tmp_p)

### FIXED CODE ###



def p(k,w,maxP):
    count = 1
    tmpWeight = 0
    for x in w:
        if tmpWeight+x <= maxP:
            tmpWeight += x
        else:
            count += 1
            if count > k :
                return False
            tmpWeight = x
    

    return True




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


w = []

for _ in range(n):
    w.append((int)(input()))
rangeMax = sum(w)
rangeMin = max(w)
rangeMid = 0
while rangeMin < rangeMax:
    rangeMid = (rangeMax + rangeMin)//2
    '''print(p(k,w,rangeMid))
    print(p(k,w,rangeMid+1))
    print("---")
    '''
    if p(k,w,rangeMid) == True:
        rangeMax = rangeMid
    else:
        rangeMid += 1
        rangeMin = rangeMid

print(rangeMid)
### BUGGY CODE ###

def make_divisor_list(num):
    if num < 1:
        return []
    elif num == 1:
        return [1]
    else:
        divisor_list = []
        divisor_list.append(1)
        for i in range(2, num // 2 + 1):
            if num % i == 0:
                divisor_list.append(i)
        divisor_list.append(num)

        return divisor_list
a,b = map(int,input().split())
a_set = set(make_divisor_list(a))
b_set = set(make_divisor_list(b))
matched_list = list(a_set & b_set)
print(max(matched_list))



### FIXED CODE ###

a,b = map(int,input().split())
def gcd(x,y):
    q = max(x,y)  %  min(x,y)
    if q == 0 :
        return [min(x,y),0]
    return gcd(min(x,y),q)

print(max(gcd(a,b)))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(4100000)

line = input().split()
nPerson = int(line[0])
nFriend = int(line[1])
nBlock  = int(line[2])

friends = [[] for i in range(nFriend)]
for i in range(nFriend):
  line = input().split()
  friends[i] =[int(line[0]), int(line[1]) ]

blocks = [[] for i in range(nBlock)]
for i in range(nBlock):
  line = input().split()
  blocks[i] = [int(line[0]), int(line[1]) ]
  
connected = [[] for i in range(nPerson+1)]
  
for i in friends:
  if i[1] not in connected[i[0]]:
    connected[i[0]].append(i[1])
  if i[0] not in connected[i[1]]:
    connected[i[1]].append(i[0])

blocked = [[] for i in range(nPerson+1)]
for i in blocks:
  if i[1] not in blocked[i[0]]:
    blocked[i[0]].append(i[1])
  if i[0] not in blocked[i[1]]:
    blocked[i[1]].append(i[0])
  
for i in range(len(connected)):
  connected[i] = set(connected[i])
for i in range(len(blocked)):
  blocked[i] = set(blocked[i])
  
nCand = [0]*(nPerson+1)

def findCand(target,curPer):
  if visited[curPer] == True :
    return
  visited[curPer] = True
  if curPer not in connected[target] and curPer not in blocked[target]:
    nCand[target] += 1
  for i in connected[curPer]:
    findCand(target,i)

for i in range(1,nPerson+1):
  visited = [False]*(nPerson+1)
  visited[i] = True
  for j in connected[i]:
    findCand(i,j)

res = ""
for i in range(1,nPerson+1):
  res += str(nCand[i]) + " "
  
print(res)
  

### FIXED CODE ###

class unionFind():
  def __init__(self,n):
    self.size = n
    self.parents = [-1]*n
  def find(self, x):
     if self.parents[x] < 0:
       return x
     else:
       self.parents[x] = self.find(self.parents[x])
       return self.parents[x]
      
  def union(self, x, y):
    x = self.find(x)
    y = self.find(y)

    if x == y:
      return
    if self.parents[x] > self.parents[y]:
      x, y = y, x
    self.parents[x] += self.parents[y]
    self.parents[y] = x

  def grpsize(self, x):
    return -self.parents[self.find(x)]
  def roots(self):
    return [i for i, x in enumerate(self.parents) if x < 0]
  def members(self, x):
    root = self.find(x)
    return [i for i in range(self.size) if self.find(i) == root]
  def __str__(self):
    return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())
      
import sys
sys.setrecursionlimit(4100000)

line = input().split()
nPerson = int(line[0])
nFriend = int(line[1])
nBlock  = int(line[2])

friends = [[] for i in range(nFriend)]
for i in range(nFriend):
  line = input().split()
  friends[i] =[int(line[0])-1, int(line[1])-1]

nconnected = [0]*nPerson
for i in friends:
    nconnected[i[0]] += 1
    nconnected[i[1]] += 1
  
  
blocks = [[] for i in range(nBlock)]
for i in range(nBlock):
  line = input().split()
  blocks[i] = [int(line[0])-1, int(line[1])-1]

uf = unionFind(nPerson)
for i in friends:
  uf.union(i[0],i[1])

nblocked = [0]*nPerson
for i in blocks:
  if uf.find(i[0]) == uf.find(i[1]):
    nblocked[i[0]] += 1
    nblocked[i[1]] += 1
  
res = ""
for i in range(nPerson):
  res += str(uf.grpsize(i)-nconnected[i] -nblocked[i]-1) + " "

print(res)
### BUGGY CODE ###

s = [int(x) for x in input()]

for k in range(len(s)//2 + 1, len(s)+1):
    if (not all(s[len(s)-k:k])) and any(s[len(s)-k:k]):
        print(k - 1)
        break
else:
    print(len(s))

### FIXED CODE ###

s = [int(x) for x in input()]

for k in range((len(s)+1)//2 + 1, len(s)+1):
    if s[k-1] != s[k-2] or s[-k] != s[-k+1]:
        print(k - 1)
        break
else:
    print(len(s))
### BUGGY CODE ###

import sys
input=sys.stdin.readline
def main():
    r,c,k=map(int,input().split())
    v=dict()
    for _ in range(k):
        ri,ci,a=map(int,input().split())
        ri-=1
        ci-=1
        v[(ri,ci)]=a
    dp=[[[0]*4 for _ in range(c)] for i in range(r)]
    #print(dp)
    if (0,0) in v:
        if v[(0,0)]>0:
            dp[0][0][1]=v[(0,0)]
    for i in range(r):
        for j in range(c):
            if i>0:
                if (i,j) in v:
                    if v[(i,j)]>0:
                        for k in range(min(3,j+1)+1):
                            dp[i][j][1]=max(dp[i][j][1],dp[i-1][j][k]+v[(i,j)])
                for k in range(4):
                    dp[i][j][k]=max(dp[i][j][k],dp[i-1][j][k])
            if j>0:
                if (i,j) in v:
                    if v[(i,j)]>0:
                        for k in range(min(3,j+1)+1):
                            if k>0:
                                dp[i][j][k]=max(dp[i][j][k],dp[i][j-1][k-1]+v[(i,j)])
                for k in range(4):
                    dp[i][j][k]=max(dp[i][j][k],dp[i][j-1][k])
    #print(dp)
    print(max(dp[r-1][c-1]))
if __name__=="__main__":
    main()

### FIXED CODE ###

import sys
input=sys.stdin.readline
def main():
    r,c,k=map(int,input().split())
    v=[[0]*c for _ in range(r)]
    for _ in range(k):
        ri,ci,a=map(int,input().split())
        ri-=1
        ci-=1
        v[ri][ci]=a
    dp=[[[0]*c for _ in range(r)] for i in range(4)]
    #print(dp)
    if v[0][0]>0:
        dp[1][0][0]=v[0][0]
    for i in range(r):
        for j in range(c):
            for k in range(4):
                if i>0:
                    dp[1][i][j]=max(dp[1][i][j],dp[k][i-1][j]+v[i][j])
                    dp[0][i][j]=max(dp[0][i][j],dp[k][i-1][j])
                if j>0:
                    if k>0:
                        dp[k][i][j]=max(dp[k][i][j],dp[k-1][i][j-1]+v[i][j])
                    dp[k][i][j]=max(dp[k][i][j],dp[k][i][j-1])
    #print(dp)
    ans=0
    for i in range(4):
        ans=max(dp[i][r-1][c-1],ans)
    return print(ans)
if __name__=="__main__":
    main()
### BUGGY CODE ###

import sys
n, m = [int(i) for i in sys.stdin.readline().split()]
graph = {i : [] for i in range(n)}
edge_ls = []
for i in range(m):
    a, b, c = [int(i) for i in sys.stdin.readline().split()]
    a -= 1
    b -= 1
    graph[a].append((b, c))
    edge_ls.append((a, b, c))

INF = float("inf")
d = [-INF for i in range(n)]
d[0] = 0
res = True
before_ls = [i for i in range(n)]
for i in range(n):
    flg = False
    for _from, _to, cost in edge_ls:
        if d[_to] < d[_from] + cost and d[_from] != -INF:
            d[_to] = d[_from] + cost
            before_ls[_to] = _from
            flg = True
    if not flg:
        break
cur = n - 1
root = set()
while cur != 0:
    root.add(cur)
    cur = before_ls[cur]
root.add(0)
flg = False
for _from, _to, cost in edge_ls:
    if d[_to] < d[_from] + cost and d[_from] != -INF:
        d[_to] = d[_from] + cost
        before_ls[_from] = _to
        if _to in root:
            flg = True
if flg:
    print("inf")
else:
    print(d[-1])

### FIXED CODE ###

N, M = [int(i) for i in input().split()]
G_ls = []
d = [-float("inf") for i in range(N)]
for i in range(M):
    a, b, c = [int(i) for i in input().split()]
    a -= 1
    b -= 1
    G_ls.append([a,b,c])

def update(x, y, is_updated):
    if x < y:
        is_updated = True
        x = y
    return x, is_updated
d[0] = 0
G_ls.sort(key=lambda x:x[0])
for i in range(N):
    for j in range(M):
        is_updated = False
        a, b, c = G_ls[j]
        d[b], is_updated = update(d[b], d[a] + c, is_updated)
if is_updated:
    print("inf")
else:
    print(d[-1])
### BUGGY CODE ###

H, W = map(int, input().split())
S = [list(input()) for _ in range(H)]
ans = 0
for i in range(H):
    for j in range(W):
        if S[i][j] == '#':
            continue
        cnt = 1
        a = i
        b = j
        while a+1 <= H-1:
            if S[a+1][b] == '#':
                break
            cnt += 1
            a += 1
        a = i
        while a-1 >= 0:
            if S[a-1][b] == '#':
                break
            cnt += 1
            a -= 1
        a = i
        b = j
        while b+1 <= W-1:
            if S[a][b+1] == '#':
                break
            cnt += 1
            b += 1
        b = j
        while b-1 >= 0:
            if S[a][b-1] == '#':
                break
            cnt += 1
            b -= 1
        ans = max(ans, cnt)
print(ans)


### FIXED CODE ###

import sys
input = sys.stdin.readline
import numpy as np

H, W = map(int, input().split())
S = np.array([list(input().rstrip()) for _ in range(H)]) == '.'
ups = np.zeros((H,W), dtype=int)
downs = np.zeros((H,W), dtype=int)
lefts = np.zeros((H,W), dtype=int)
rights = np.zeros((H,W), dtype=int)

for h in range(1, H):
    ups[h] = (ups[h-1] + 1) * S[h-1]
    downs[H-h-1] = (downs[H-h] + 1) * S[H-h]
for w in range(1, W):
    lefts[:, w] = (lefts[:, w-1] + 1) * S[:, w-1]
    rights[:, W-w-1] = (rights[:, W-w] + 1) * S[:, W-w]
print(np.amax((ups+downs+lefts+rights)*S)+1)
### BUGGY CODE ###

from bisect import bisect_right
n = int(input())
d = {}
for a in map(int, input().split()):
  if a in d:
    d[a] += 1
  else:
    d[a] = 1
t = 1
valids = []
while t < 2 * 10 ** 9:
  t *= 2
  valids.append(t)
result = 0
while True:
  prev = result
  keys = list(d.keys())
  keys.sort(reverse = True)
  for x in keys:
    t = valids[bisect_right(valids, x)] - x
    if t not in d:
      continue
    if x == t and d[x] == 1:
      continue
    result += 1
    if d[x] == 1:
      del d[x]
    else:
      d[x] -= 1
    if d[t] == 1:
      del d[t]
    else:
      d[t] -= 1
    break
  if prev == result:
    break
print(result)

### FIXED CODE ###

from bisect import bisect_right
n = int(input())
d = {}
for a in map(int, input().split()):
  if a in d:
    d[a] += 1
  else:
    d[a] = 1
t = 1
valids = []
while t < 2 * 10 ** 9:
  t *= 2
  valids.append(t)
result = 0
while True:
  prev = result
  keys = list(d.keys())
  keys.sort(reverse = True)
  for x in keys:
    if x not in d:
      continue
    t = valids[bisect_right(valids, x)] - x
    while True:
      if t not in d:
        break
      if x == t and d[x] == 1:
        break
      result += 1
      if d[x] == 1:
        del d[x]
      else:
        d[x] -= 1
      if d[t] == 1:
        del d[t]
      else:
        d[t] -= 1
      if x not in d:
        break
  if prev == result:
    break
print(result)
### BUGGY CODE ###

N,W = map(int,input().split())
w = []
v = []
for i in range(N):
  w_,v_ = map(int,input().split())
  w.append(w_)
  v.append(v_)

dp = [[0]*(W+1) for _ in range(N+1)]

def memo(i,j):
  if dp[i][j]:
    return dp[i][j]
  if i == N:
    dp[i][j] = 0
  elif w[i] > j:
    dp[i][j] = memo(i+1,j)
  else:
    dp[i][j] = max(memo(i+1,j),memo(i+1,j-w[i])+v[i])
  return dp[i][j] 
print(memo(0,W))

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**9)
N,W = map(int,input().split())
w = []
v = []
for i in range(N):
  w_,v_ = map(int,input().split())
  w.append(w_)
  v.append(v_)

dp = [[0]*(W+1) for _ in range(N+1)]

def memo(i,j):
  if dp[i][j]:
    return dp[i][j]
  if i == N:
    dp[i][j] = 0
  elif w[i] > j:
    dp[i][j] = memo(i+1,j)
  else:
    dp[i][j] = max(memo(i+1,j),memo(i+1,j-w[i])+v[i])
  return dp[i][j] 
print(memo(0,W))
### BUGGY CODE ###

import numpy as np
N=int(input())
A=list(map(int,input().split()))
L=list()
B=0
for i in range(N):
    L.append(A[i])
    L.sort()
    B += L[i]-A[i]
print(B)

### FIXED CODE ###

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

for i in range(1,N):
    if A[i] > Mi:
        Mi = A[i]
    B += Mi - A[i]
print(B)
### BUGGY CODE ###

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

half_sum_water = sum(water) // 2

ans = []

m = n // 2
for i in range(n):
    mount = half_sum_water
    for j in range(m):
        mount = mount - water[(i + 1 + (j * 2)) % n]
    print(mount * 2,end = ' ')

print()


### FIXED CODE ###

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

half_sum_water = sum(water) // 2

ans = []

m = n // 2
x0 = half_sum_water
for i in range(m):
    x0 = x0 - water[(1 + (i * 2)) % n]

print(x0 * 2,end = ' ')

x = x0
for i in range(n - 1):
    x = water[i] - x
    print(x * 2,end = ' ')

print()
### BUGGY CODE ###

S = input()
Q = int(input())
for i in range(Q):
    q = input().split()
    if len(q) == 1:
        S = S[::-1]
    else:
        if q[1] == '1':
            S = q[2] + S
        else:
            S = S + q[2]
print(S)


### FIXED CODE ###

from collections import deque
S = input()
Q = int(input())
pre = deque()
suf = deque()
rev = False
for i in range(Q):
    q = input().split()
    if len(q) == 1:
        rev = not rev
    else:
        if (not rev and q[1] == '1') or (rev and q[1] == '2'):
            pre.appendleft(q[2])
        else:
            suf.append(q[2])
if rev:
    S = S[::-1]
    p = list(suf)[::-1]
    s = list(pre)[::-1]
else:
    p = list(pre)
    s = list(suf)
print(''.join(p) + S + ''.join(s))
### BUGGY CODE ###


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

if s==3*k:
    print(1)
else:
    ans=0
    for i in range(k+1):
        if i>s:
            break
        for j in range(k+1):
            if i+j>s:
                break
            for jj in range(k+1):
                if i+j+jj==s:
                    ans+=1
                elif i+j+jj>s:
                    break
    print(ans)

### FIXED CODE ###

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

if s==3*k:
    print(1)
else:
    ans=0
    for i in range(k+1):
        if i>s:
            break
        for j in range(k+1):
            if i+j+k>=s and s-i-j>=0:
                ans+=1


    print(ans)