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

import copy
import sys

h, w = map(int, input().split())
S_outer = [input() for _ in range(h)]


def get_shortest_steps(S_inner, visited, i_inner, j_inner, steps):
    if i_inner == -1 or i_inner == h or j_inner == -1 or j_inner == w:
        return sys.maxsize
    if visited[i_inner * 20 + j_inner]:
        return sys.maxsize
    if S_inner[i_inner][j_inner] == "#":
        return sys.maxsize
    visited[i_inner * 20 + j_inner] = True
    if shortest_steps_map[i_inner * 20 + j_inner] > steps:
        shortest_steps_map[i_inner * 20 + j_inner] = steps
    get_shortest_steps(S_inner, copy.copy(visited), i_inner + 1, j_inner, steps + 1)
    get_shortest_steps(S_inner, copy.copy(visited), i_inner, j_inner + 1, steps + 1)
    get_shortest_steps(S_inner, copy.copy(visited), i_inner - 1, j_inner, steps + 1)
    get_shortest_steps(S_inner, copy.copy(visited), i_inner, j_inner - 1, steps + 1)
    return


result = -1
for i_outer in range(h):
    for j_outer in range(w):
        visited_outer = [False] * (h * 20 + w + 1)
        shortest_steps_map = [500] * (h * 20 + w + 1)
        get_shortest_steps(S_outer, copy.copy(visited_outer), i_outer, j_outer, 0)

        for i in range(len(shortest_steps_map)):
            if shortest_steps_map[i] == 500:
                shortest_steps_map[i] = 0

        if max(shortest_steps_map) > result:
            result = max(shortest_steps_map)
print(result)

### FIXED CODE ###

import sys
import numpy as np
from collections import deque

h, w = map(int, input().split())
maze = [list(input()) for _ in range(h)]
direction = [(1, 0), (0, 1), (-1, 0), (0, -1)]

max_step = 0
for i in range(h):
    for j in range(w):
        largest_step = 0
#        print("start: ", i, j)
        if maze[i][j] == "#":
            continue
        visited = [[False] * w for _ in range(h)]
        distance = [[-1] * w for _ in range(h)]
        plan = deque()
        step = 0
        plan.appendleft((i, j, step))
        distance[i][j] = step
        visited[i][j] = True
        while plan:
            y, x, step = plan.pop()
#            print(" ", x, y, step)
            # if step > largest_step:
            #     largest_step = step
            for next_direction in direction:
                next_y = y + next_direction[0]
                next_x = x + next_direction[1]
                if -1 == next_x or next_x == w or -1 == next_y or next_y == h or maze[next_y][next_x] == "#" or visited[next_y][next_x]:
                    continue
                distance[next_y][next_x] = distance[y][x] + 1
                visited[next_y][next_x] = True
                plan.appendleft((next_y, next_x, step + 1))
#        print(largest_step)
        # if largest_step > max_step:
        #     max_step = largest_step
        max_step = max(max_step, np.max(np.array(distance)))

print(max_step)
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
mx=len(bin(max(a)))
b=["0"*(mx-len(bin(x)))+bin(x)[2:] for x in a]

out=["" for _ in range(n)]
ref=[0 for _ in range(mx-2)]
for j in range(n):
    work=b[j]
    for i in range(mx-2):
        ref[i]+=int(work[i])
        ref[i]%=2

for j in range(n):
    work=b[j]
    for i in range(mx-2):
        if int(work[i])==ref[i]:out[j]+="0"
        else : out[j]+="1"

c=[str(int(y,2)) for y in out]
print(" ".join(c))

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
mx=len(bin(max(a)))
b=["0"*(mx-len(bin(x)))+bin(x)[2:] for x in a]

out=["" for _ in range(n)]
for i in range(mx-2):
    tot=0
    for j in range(n):
        tot+=int(b[j][i])
    tot=tot%2
    for j in range(n):
        if tot==int(b[j][i]):out[j]+="0"
        else : out[j]+="1"
c=[str(int(y,2)) for y in out]
print(" ".join(c))
### BUGGY CODE ###

s = input().split()
h = int(s[0])
k = int(s[1])
s = list(map(int,input().split()))
for i in range(k):
    if len(s)>0:
        s.remove(max(s))
print(sum(s))

### FIXED CODE ###

s = list(map(int, input().split()))
n=s[0]
k=s[1]
s = list(map(int, input().split()))
s.sort()
if n<k:
    print(0)
else:
    print(sum(s[0:n-k]))
### BUGGY CODE ###

import sys
import itertools
# import numpy as np
import time
import math
import heapq
from collections import defaultdict
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# map(int, input().split())
S = input()
K = int(input())

d = sorted(list(S))
x = set(d)
for c in d:
    left = S.index(c)
    while left < len(S):
        if S[left] != c:
            left += 1
            continue
        j = 2
        while left + j <= len(S):
            x.add(S[left:left+j])
            j += 1
        left += 1
    if len(x) >= K:
        break
x = sorted(list(x))
# print(x)
print(x[K - 1])

### FIXED CODE ###

import sys
import itertools
# import numpy as np
import time
import math
import heapq
from collections import defaultdict
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# map(int, input().split())
S = input()
K = int(input())

d = sorted(list(S))
x = set(d)
for c in d:
    left = S.index(c)
    while left < len(S):
        if S[left] != c:
            left += 1
            continue
        j = 2
        while j <= K:
            x.add(S[left:left+j])
            j += 1
        left += 1
    if len(x) >= K:
        break
x = sorted(list(x))
print(x[K - 1])
### BUGGY CODE ###

s = input()
now = len(s)
while 1:
    if 7 <= now:
        if s[now-7:now] == "dreamer":
            now -= 7
    if 6 <= now:
        if s[now-6:now] == "eraser":
            now -= 6
    if 5 <= now:    
        if s[now-5:now] == "erase":
            now -= 5
        if s[now-5:now] == "dream":
            now -= 5
    if now == 0:
        print("YES")
        exit()
    elif now < 5:
        print("NO")
        exit()

### FIXED CODE ###

s = input()
now = len(s)
while 1:
    flag = 1
    if 7 <= now:
        if s[now-7:now] == "dreamer":
            now -= 7
            flag = 0
    if 6 <= now:
        if s[now-6:now] == "eraser":
            now -= 6
            flag = 0
    if 5 <= now:    
        if s[now-5:now] == "erase":
            now -= 5
            flag = 0
        if s[now-5:now] == "dream":
            now -= 5
            flag = 0
    if flag:
        print("NO")
        exit()
    if now == 0:
        print("YES")
        exit()
    elif now < 5:
        print("NO")
        exit()
### BUGGY CODE ###

import bisect
N = int(input())
L = list(map(int, input().split()))
L.sort()
ans = 0
for i in range(N):
    for j in range(i + 1, N):
        l = L[j] - L[i]
        r = L[j] + L[i]
        ans += bisect.bisect_left(L[j+1:], r) - bisect.bisect_right(L[j+1:], l)
print(ans)

### FIXED CODE ###

import bisect
N = int(input())
L = list(map(int, input().split()))
L.sort()
ans = 0
for i in range(N):
    for j in range(i + 1, N):
        r = L[j] + L[i]
        ans += bisect.bisect_left(L[j+1:], r)
print(ans)
### BUGGY CODE ###

N, M = map(int, input().split())
s = []
e = []
for i in range(M):
  a, b = map(int, input().split())
  if a == 1:
    s.append(b)
  if b == N:
    e.append(a)
ans = 'IMPOSSIBLE'
for k in s:
  if k in e:
    ans = 'POSSIBLE'
    break
print(ans)

### FIXED CODE ###

N, M = map(int, input().split())
s = []
e = []
for i in range(M):
  a, b = map(int, input().split())
  if a == 1:
    s.append(b)
  if b == N:
    e.append(a)
if set(s) & set(e):
  print('POSSIBLE')
else:
  print('IMPOSSIBLE')
### BUGGY CODE ###

import sys 
from math import gcd
# from numba import jit
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
mod = 10 ** 9 + 7
N = int(readline())
A = list(map(int,readline().split()))
# @jit(cache=True)
def lcm(N,a):
    x = a[0]
    for i in range(1, N):
        x = (x * a[i]) // gcd(x, a[i])
    ans = 0 
    for i in range(N):
        ans += x // a[i] % mod
    return ans%mod
ans = lcm(N,A)
print(ans)

### FIXED CODE ###

import sys 
from functools import reduce
from math import gcd
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
mod = 10 ** 9 + 7
N = int(readline())
A = list(map(int,readline().split()))
lcm = reduce(lambda x,y:x*y//gcd(x,y),A)
ans = 0
ans = sum(lcm//x for x in A)
print(ans%mod)
### BUGGY CODE ###

def main():
    h, w = map(int, input().split())
    a = [list(map(int, input().split())) for _ in range(h)]
    b = [list(map(int, input().split())) for _ in range(h)]
    c = [[None]*w for _ in range(h)]
    for i in reversed(range(h)):
        for j in reversed(range(w)):
            c[i][j] = abs(a[i][j] - b[i][j])
            if i < h-1:
                c[i][j] += c[i+1][j]
            if j < w-1:
                c[i][j] += c[i][j+1]
    t = [[set() for j in range(w)] for i in range(h)]
    t[0][0].add(abs(a[0][0] - b[0][0]))
    for i in range(h):
        for j in range(w):
            if 0 < i and 0 < j:
                buf = t[i-1][j] | t[i][j-1]
                for v in buf:
                    t[i][j].add(abs(v + (a[i][j] - b[i][j])))
                    t[i][j].add(abs(v - (a[i][j] - b[i][j])))
            elif 0 < i:
                buf = t[i-1][j]
                for v in buf:
                    t[i][j].add(abs(v + (a[i][j] - b[i][j])))
                    t[i][j].add(abs(v - (a[i][j] - b[i][j])))
            elif 0 < j:
                buf = t[i][j-1]
                for v in buf:
                    t[i][j].add(abs(v + (a[i][j] - b[i][j])))
                    t[i][j].add(abs(v - (a[i][j] - b[i][j])))
    ans = float("inf")
    for v in t[i][j]:
        ans = min(ans, abs(v))
    print(ans)

if __name__ == "__main__":
    main()

### FIXED CODE ###

import numpy as np
def main():
    h, w = map(int, input().split())
    a = [list(map(int, input().split())) for _ in range(h)]
    b = [list(map(int, input().split())) for _ in range(h)]
    n = 80*(80+80) + 10
    m = n//2
    dp = [[None]*w for i in range(h)]
    for i in range(h):
        for j in range(w):
            dp[i][j] = np.zeros(n, np.bool)
    dp[0][0][m+abs(a[0][0] - b[0][0])] = True
    dp[0][0][m-abs(a[0][0] - b[0][0])] = True
    for i in range(h):
        for j in range(w):
            x = abs(a[i][j] - b[i][j])
            if 0 < i and 0 < h:
                dp[i][j][x:] |= dp[i-1][j][:n-x]
                dp[i][j][:n-x] |= dp[i-1][j][x:]
                dp[i][j][x:] |= dp[i][j-1][:n-x]
                dp[i][j][:n-x] |= dp[i][j-1][x:]
            elif 0 < i:
                dp[i][j][x:] |= dp[i-1][j][:n-x]
                dp[i][j][:n-x] |= dp[i-1][j][x:]
            elif 0 < j:
                dp[i][j][x:] |= dp[i][j-1][:n-x]
                dp[i][j][:n-x] |= dp[i][j-1][x:]
    ans = float("inf")
    for i in range(m-80-1, m+80+2):
        if dp[h-1][w-1][i]:
            ans = min(ans, abs(m-i))
    print(ans)

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

H,W,D = map(int,input().split())
A = [list(map(int,input().split())) for i in range(H)]
C = [[] for i in range(H*W+1)]
for i in range(H):
    for j in range(W):
        C[A[i][j]] = (i,j)
Q = int(input())
for i in range(Q):
    L,R = map(int,input().split())
    cost = 0
    i,j = C[L]
    while L!=R:
        L+=D
        x,y = C[L]
        cost += abs(x-i)+abs(y-j)
        i,j = C[L]
    print(cost)

### FIXED CODE ###

#19:38
#20:19

H,W,D = map(int,input().split())
MAX = H*W
A = [list(map(int,input().split())) for i in range(H)]
Point = [0]*(MAX+1)
for h in range(H):
    for w in range(W):
        Point[A[h][w]] = (h,w)
K = []
for i in range(1,D+1):
    List = []
    n = i
    h,w = Point[n]
    cost = 0
    while n<=MAX:
        y,x = Point[n]
        cost += abs(h-y)+abs(w-x)
        List.append(cost)
        h,w = y,x
        n+=D
    K.append(List)
Q = int(input())
for i in range(Q):
    L,R = map(int,input().split())
    a,l,r = (L-1)%D,(L-1)//D,(R-1)//D
    print(K[a][r]-K[a][l])
### BUGGY CODE ###

import numpy as np
N,K = (int(x) for x in input().split())
p1 = np.array(list(map(int, input().split())))
p2 = np.array([np.sum(p1[i:i+K]) for i in range(N-K+1)])
max = np.amax(p2)
print((max+K) / 2)

### FIXED CODE ###

import numpy as np
N,K = (int(x) for x in input().split())
p1 = np.array(list(map(int, input().split())))
s1 = p1.cumsum()
s2 = np.append(0, s1)
p2 = np.array([(s2[i+K] - s2[i]) for i in range(N-K+1)])
max = np.amax(p2)
print((max+K) / 2)
### BUGGY CODE ###

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

ans = 1
for i in range(len(a)):
    ans *= a[i]

if ans > 10 ** 18:
    print(-1)
else:
    print(ans)


### FIXED CODE ###

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

    try:
        if a.index(0):
            print(0)
            sys.exit()
    except ValueError:
        pass

    ans = 1
    for i in range(n):
        ans *= a[i]
        if ans > 10 ** 18:
            print(-1)
            sys.exit()

    print(ans)


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

import sys
from bisect import bisect_left

input = sys.stdin.buffer.readline
N = int(input())
A = sorted(list(map(int, input().split())))
B = sorted(list(map(int, input().split())))
C = sorted(list(map(int, input().split())))

ans = 0
for i in range(len(C)):
    c = C[i]
    b_idx = bisect_left(B, c)
    for j in range(b_idx):
        b = B[j]
        a_idx = bisect_left(A, b)
        ans += a_idx
print(ans)


### FIXED CODE ###

import sys
from bisect import bisect_left

input = sys.stdin.buffer.readline
N = int(input())
A = sorted(list(map(int, input().split())))
B = sorted(list(map(int, input().split())))
C = sorted(list(map(int, input().split())))

cumsum = [0]
for i in range(len(B)):
    b = B[i]
    a_idx = bisect_left(A, b)
    cumsum.append(cumsum[i] + a_idx)
# print('cumsum', cumsum)

ans = 0
for i in range(len(C)):
    c = C[i]
    b_idx = bisect_left(B, c)
    ans += cumsum[b_idx]
print(ans)
### BUGGY CODE ###

def findDivisors(n): 
      
    # List to store the count 
    # of divisors 
    div = [0 for i in range(n + 1)] 
      
    # For every number from 1 to n 
    for i in range(1, n + 1): 
          
        # Increase divisors count for 
        # every number divisible by i 
        for j in range(1, n + 1): 
            if j * i <= n: 
                div[i * j] += 1
    return div

n=int(input())
ans=0
dp=findDivisors(n)
for i in range(len(dp)):
	ans+=(dp[i]*(i))
#print(*dp)
print(ans)

### FIXED CODE ###

def findDivisors(n): 
      
    # List to store the count 
    # of divisors 
    div = [0 for i in range(n + 1)] 
      
    # For every number from 1 to n 
    for i in range(1, n + 1): 
          
        # Increase divisors count for 
        # every number divisible by i 
        for j in range(1, n + 1): 
            if j * i <= n: 
                div[i * j] += 1
            else:
              break
    return div

n=int(input())
ans=0
dp=findDivisors(n)
for i in range(len(dp)):
	ans+=(dp[i]*(i))
#print(*dp)
print(ans)
### BUGGY CODE ###

import math

n=int(input())
total=0

for i in range(n):
  for j in range(n):
    for k in range(n):
      gcdij=math.gcd(i+1,j+1)
      gcd=math.gcd(gcdij,k+1)
      total+=gcd
      
print(total)

### FIXED CODE ###

n=int(input())

total=0

for i in range(n):
  #print(f'i+1={i+1}')
  j=i
  while j<n:
    #print(f'j+1={j+1}')
    k=j
    while k<n:
      #print(f'k+1={k+1}')
      kouho=min(i+1,j+1,k+1)
      while True:
        #kouhoが最大公約数の時
        if (i+1)%kouho==0 and (j+1)%kouho==0 and (k+1)%kouho==0:
          #３つとも同じ数字
          if i==j and j==k:
            total+=kouho
          #２つのみ同じ数字
          elif i==j or j==k or k==i:
            total+=kouho*3
          #同じ数字がない時
          else:
            total+=kouho*6
          break
        else:
          kouho -= 1
      k+=1
    j+=1
          
print(total)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**7)
n,m=map(int,input().split())
g=[[] for _ in range(n)]
for _ in range(m):
    u,v=map(int,input().split())
    u,v=u-1,v-1
    g[u].append(v)
mi=set(range(n))
flg=False
def dfs(v,seen):
    for nv in g[v]:
        if seen[nv]!=-1:#閉路
            seen[nv]=v
            return nv
        else:
            seen[nv]=v
            t=dfs(nv,seen)
            if t!=-1:return t
            seen[nv]=-1
    return -1
while mi:
    v=mi.pop()
    seen=[-1]*n
    f=dfs(v,seen)
    if f!=-1:break
if f==-1:
    print(-1)
    exit()
#print(seen,f)
ff=f
path={f}
while seen[f] not in path:
    f=seen[f]
    path.add(f)

#print(seen,path,ff)
from collections import deque
todo=deque([ff])
seen=[[-1,-1] for _ in '_'*n]
d=0
seen[ff][1]=d
flg=False
start=[-1,-1]
while todo:
    v=todo.popleft()
    d+=1
    for nv in g[v]:
        if nv in path:
            if seen[nv][1]!=-1:
                seen[nv][0]=v
                if start[0]==-1:
                    start=[nv,seen[nv][1]]
                else:
                    if start[1]<seen[nv][1]:
                        start=[nv,seen[nv][1]]
                flg=True
            else:
                todo.append(nv)
                seen[nv]=[v,d]
    if flg:break
s=nv
ans=[s+1]
#print(seen,nv)
while seen[nv][0]!=s:
    nv=seen[nv][0]
    ans.append(nv+1)
print(len(ans))
print(*ans,sep='\n')


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)
n,m=map(int,input().split())
g=[[] for _ in range(n)]
for _ in range(m):
  u,v=map(int,input().split())
  u,v=u-1,v-1
  g[u].append(v)
mi=set(range(n))
flg=False
def func(path):
  chk=set(path)
  if len(path)!=2:
    for i,v in enumerate(path):
      nvs=[nv for nv in g[v] if nv in chk]
      if len(nvs)==1:continue
      for nv in nvs:
        if nv==path[(i+1)%len(path)]:continue
        ary=[nv]
        for j,vj in enumerate(path):
          if vj==nv:break
        if i>j:
          ary=path[j:i+1]
        else:
          ary=path[:i+1]+path[j:]
        #print(path,ary,i,j)
        func(ary)
  print(len(path))
  for v in path:
    print(v+1)
  exit()

def dfs(v,seen):
  mi.discard(v)
  for nv in g[v]:
    if seen[nv]!=-1:# 巡回閉路
      seen[nv]=v
      path=[v]
      chk={v}
      while seen[v] not in chk:
        v=seen[v]
        path.append(v)
        chk.add(v)
      path.reverse()
      func(path)
    else:
      seen[nv]=v
      dfs(nv,seen)
      seen[nv]=-1
while mi:
  v=mi.pop()
  seen=[-1]*n
  dfs(v,seen)
print(-1)
exit()
### BUGGY CODE ###

N = int(input())
A = [int(x) for x in input().split()]

gokei = 0
for i in range(len(A)):
    gokei += A[i] * sum(A)
    gokei -= A[i] * A[i]
gokei = gokei // 2
ans = gokei % 1000000007
print(ans)


### FIXED CODE ###

N = int(input())
A = [int(x) for x in input().split()]

gokei = sum(A) ** 2
for i in range(len(A)):
    gokei -= A[i] * A[i]
gokei = gokei // 2
ans = gokei % 1000000007
print(ans)
### BUGGY CODE ###

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

for i in range(N):
    ans *= A[i]
    if 0 in A:
        ans = 0
        break
    if ans > 1000000000000000000:
        ans = -1
        break

print(ans)

### FIXED CODE ###

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


if 0 in A:
    ans = 0
else:
    for i in range(N):
        ans *= A[i]
        if ans > 1000000000000000000:
            ans = -1
            break

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

# -*- coding: utf-8 -*-
"""
Created on Sun Mar 24 20:23:42 2019

@author: SCREAM
"""

count = 0;
maxnum=0;
n,m = input().split();

s = input();




for j in range(int(m)):
    x,y = input().split();
    i =int(x)-1
    while(i<int(y)-1):
        if(s[i]=='A' and s[i+1] == 'C'):
            count = count +1;
            i = i+2;
        else:
            i = i+1;
    print(count);  
    count = 0;
   
        

    


### FIXED CODE ###

import numpy as np;
count = 0;
maxnum=0;
n,m = input().split();
mark=np.zeros(int(n));
s = input();

for i in range(1,int(n)):
    if(s[i]=='C' and s[i-1] == 'A'):
        count= count +1;
    mark[i] = count;
for j in range(int(m)): 
    x,y = input().split();
    print(int(mark[int(y)-1])-int(mark[int(x)-1]))
### BUGGY CODE ###

n = int(input())
ls = list(map(int, input().split()))
if 0 in ls:
    print(0)
else:
    ans = 1
    for i in ls:
        ans *= i

    if ans > 10**18:
        print(-1)
    else:
        print(ans)


### FIXED CODE ###

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

ans = 1
if 0 in num:
    print(0)
    exit()
else:
    for i in num:
        ans *= i
        if ans > 10**18:
            print(-1)
            exit()

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

import copy
n=int(input())
l1=[int(input()) for i in range(n)]

for i in range(n):
  l2 = copy.copy(l1)
  del l2[i]
  print(max(l2))

### FIXED CODE ###

n=int(input())
l1=[int(input()) for i in range(n)]
l2=sorted(l1)
max1=l2[-1]
max2=l2[-2]
for i in l1:
  if i == max1:
    print(max2)
  else:
    print(max1)
### BUGGY CODE ###

import numpy as np
amari = np.array([[i] for i in range(10)])
p = 10**9 + 7
s =  str(input())
n = len(s)
dp = np.zeros((n+1, 13))
dp[0, 0] = 1
for i in range(n):
  if s[n-1-i] == '?':
    for j in range(13):
      dp[i+1][(j + amari)%13] += dp[i][j]
  else:
    for j in range(13):
      dp[i+1][(j + amari[int(s[n-1-i])])%13] += dp[i][j]
  dp[i + 1, :] %= p
  amari = amari*10 %13
print(int(dp[n, 5]))

### FIXED CODE ###

amari = [i for i in range(10)]
p = 10**9 + 7
s =  str(input())
n = len(s)
ans = [0]*13
ans[0] = 1
for i in reversed(s):
  dp = [0]*13
  if i == '?':
    for j in range(13):
      for k in amari:
        dp[(j + k)%13] += ans[j]
  else:
    for j in range(13):
      dp[(j + amari[int(i)])%13] += ans[j]
      
  for i in range(len(dp)):
    dp[i] %= p
  ans = dp
  for i in range(len(amari)):
    amari[i] = amari[i]*10%13
print(ans[5])
### BUGGY CODE ###

N = int(input())
X = input()

a = int(X, 2)
b = X.count("1")
k = 2 ** (N-1)

for i in range(N):
    if X[i] == "0":
        x = a + k
        y = b + 1
    else:
        x = a - k
        y = b - 1
    k //= 2

    if x == 0:
        print(0)
    else:
        ans = 1
        t = x % y
        while t > 0:
            t %= bin(t).count("1")
            ans += 1
        print(ans)


### FIXED CODE ###

N = int(input())
X = input()

a = int(X, 2)
b = X.count("1")

if b > 1:
    a1 = a % (b-1)
else:
    a1 = 0
a0 = a % (b+1)

for i in range(N):
    if X[i] == "1":
        if b == 1:
            print(0)
            continue
        t = (a1 - pow(2, N-1-i, b-1)) % (b-1)
    else:
        t = (a0 + pow(2, N-1-i, b+1)) % (b+1)
    
    ans = 1
    while t > 0:
        t %= bin(t).count("1")
        ans += 1
    print(ans)
### BUGGY CODE ###

from functools import lru_cache
N,W=map(int,input().split())
weights,profits = [0]*N, [0]*N
for i in range(N):
    weights[i],profits[i] = map(int,input().split())
@lru_cache(None)
def knapsack_recursive(capacity, currentIndex):


    if capacity <= 0 or currentIndex >= len(profits): return 0

    profit = 0
    if weights[currentIndex] <= capacity:
        profit = profits[currentIndex] + knapsack_recursive(capacity - weights[currentIndex], currentIndex + 1)
    tmp = knapsack_recursive(capacity, currentIndex + 1)
    if tmp > profit:
        profit = tmp  
    return profit
  
def main():

    res = knapsack_recursive(W, 0)

    print(res)
if __name__ == "__main__":
	main()

### FIXED CODE ###

def main():
  n, w = [int(e) for e in input().split()]
  t = [-1 for i in range(w + 1)]
  t[w] = 0
  for _ in range(n):
    nw, nv = [int(e) for e in input().split()]
    for i in range(nw, w + 1):
      if t[i] == -1:
        continue
      if t[i - nw] < t[i] + nv:
        t[i - nw] = t[i] + nv
  print(max(t))
main()