Harryxun/stf_run huggingface dataset:
while 1:
	n=list(raw_input())
	if n[0]==n[1]==n[2]==n[3]=="0": break
	elif n[0]==n[1]==n[2]==n[3]:
		print "NA"
		continue
	count=0
	while 1:
		if n==["6","1","7","4"]:
			print count
			break
		m=sorted(n)[::-1]
		l=sorted(n)[n.count("0"):]
		n=list(str(int("".join(map(str,m)))-int("".join(map(str,l)))))
		count+=1

### FIXED CODE ###

while 1:
    n=raw_input()
    if n=="0000": break
    if int(n)%1111==0:
        print "NA"
        continue
    ans = 0
    while n!="6174":
        n="".join(sorted(n))
        n=str(int(n[::-1])-int(n)).zfill(4)
        ans+=1
    print ans
import itertools as it

N, M, X = map(int, input().split())
book = [[int(_) for _ in input().split()] for i in range(N)]

combs = it.product([0, 1], repeat=N)
prices = []
for comb in combs:
    # print(comb)
    bag = [0] * M+1
    for i in range(N):
        if comb[i] == 0:
            continue
        else:
            for j in range(M+1):
                bag[j] += book[i][j]

    if min(bag[1:]) < X:
        continue
    else:
        prices.append(bag[0])

if len(prices) == 0:
    print(-1)
else:
    print(min(prices))

### FIXED CODE ###

import itertools as it

N, M, X = map(int, input().split())
book = [[int(_) for _ in input().split()] for i in range(N)]

combs = it.product([0, 1], repeat=N)
prices = []
for comb in combs:
    # print(comb)
    bag = [0] * (M+1)
    for i in range(N):
        if comb[i] == 0:
            continue
        else:
            for j in range(M+1):
                bag[j] += book[i][j]

    if min(bag[1:]) < X:
        continue
    else:
        prices.append(bag[0])

if len(prices) == 0:
    print(-1)
else:
    print(min(prices))
for i in range(0,2*b2,2):
    for j in range(0,100,2):
        t[i][j]="#"
for i in range(0,2*b3,2):
        t[2*b2][i]="#"
print(100,100)
for i in range(50):
    print("".join(s[i]))
for i in range(50):
    print("".join(t[i]))

### FIXED CODE ###

a,b=map(int,input().split())
s=[["#" for i in range(100)] for j in range(50)]
t=[["." for i in range(100)] for j in range(50)]

a2,a3=(a-1)//50,(a-1)%50
for i in range(0,2*a2,2):
    for j in range(0,100,2):
        s[i][j]="."
for i in range(0,2*a3,2):
    s[2*a2][i]="."

b2,b3=(b-1)//50,(b-1)%50
for i in range(2,2*b2+2,2):
    for j in range(0,100,2):
        t[i][j]="#"
for i in range(0,2*b3,2):
        t[2*b2+2][i]="#"
print(100,100)
for i in range(50):
    print("".join(s[i]))
for i in range(50):
    print("".join(t[i]))
a=int((input())
print(a+a**2+a**3)

### FIXED CODE ###

a=int(input())
print(a+a**2+a**3)
n=int(input())
xbox=[]
ybox=[]
for i in range(n):
    x,y = map(int,input().split())
    xbox.append(x)
    ybox.append(y)
xmax=max(xbox)
xmin = min(xbox)
ymax=max(ybox)
ymin=min(ybox)
box1=[]
box2=[]
box3=[]
box4=[]
for i in range(n):
    box1.append(xmax+ymax-xbox[i]-ybox[i])
    box2.append(-xmin + ymax + xbox[i] - ybox[i])
    box2.append(xmax - ymax - xbox[i] + ybox[i])
    box2.append(-xmax - ymax + xbox[i] + ybox[i])
print(max([max(box1)-min(box1),max(box2)-min(box2),max(box3)-min(box3),max(box4)-min(box4)]))


### FIXED CODE ###

n=int(input())
xbox=[]
ybox=[]
for i in range(n):
    x,y = map(int,input().split())
    xbox.append(x)
    ybox.append(y)
xmax=max(xbox)
xmin = min(xbox)
ymax=max(ybox)
ymin=min(ybox)
box1=[]
box2=[]
box3=[]
box4=[]
for i in range(n):
    box1.append(xmax+ymax-xbox[i]-ybox[i])
    box2.append(-xmin + ymax + xbox[i] - ybox[i])
    box3.append(xmax - ymax - xbox[i] + ybox[i])
    box4.append(-xmax - ymax + xbox[i] + ybox[i])
print(max([max(box1)-min(box1),max(box2)-min(box2),max(box3)-min(box3),max(box4)-min(box4)]))
X = int(input())

for i in range(0, X):
    result += (i+1)
    if X >= result:
        print(i+1)
        break

### FIXED CODE ###

X = int(input())

result = 0
for i in range(0, X):
    result += (i+1)
    if X <= result:
        print(i+1)
        break
import math
PI = math.pi

r = int(row_input())
men = r**2 * PI
sen = r*2 * PI

print('%.6f %.6f' % (men, sen))

### FIXED CODE ###

import math
PI = math.pi

r = input()
men = r*r * PI
sen = r*2 * PI

print('%.6f %.6f' % (men, sen))
import math
A B H M = map(int, input().split())
Mkaku = 6 * M
Hkaku = (H * 60 + M) / 2
r1 = Hkaku * math.pi / 180
r2 = Mkaku * math.pi / 180
v1x = A * math.cos(r1)
v1y = A * math.sin(r1)
v2x = B * math.cos(r2)
v2y = B * math.sin(r2)
ans = ((v1x - v2x) ** 2 + (v1y - v2y) ** 2) ** 1/2
print(ans)

### FIXED CODE ###

import math
A, B, H, M = map(int, input().split())
Mkaku = 6 * M
Hkaku = (H * 60 + M) / 2
r1 = Hkaku * math.pi / 180
r2 = Mkaku * math.pi / 180
v1x = A * math.cos(r1)
v1y = A * math.sin(r1)
v2x = B * math.cos(r2)
v2y = B * math.sin(r2)
ans = ((v1x - v2x) ** 2 + (v1y - v2y) ** 2) ** (1 / 2)
print(ans)
#!/usr/bin/env python3
import sys

def main():
    a = int(sys.stdin.readline().rstrip())
    b = int(sys.stdin.readline().rstrip())

    print((a-1)*(b-1))
    

if __name__ == '__main__':
    main()

### FIXED CODE ###

#!/usr/bin/env python3
import sys

def main():
    a, b = [int(x) for x in sys.stdin.readline().rstrip().split()]
    print((a-1)*(b-1))
    

if __name__ == '__main__':
    main()
s = list(input())
a_index = [i for i, x in enumerate(s) if x == 'A']
z_index = [i for i, x in enumerate(s) if x == 'Z']
distance = []

for i in a_index:
    for j in z_index:
        if i <= j:
            dis = abs(i-j)
            distance.append(dis)
        else:
            break

print(max(distance)+1)


### FIXED CODE ###

s = input()

print(s.rfind('Z') - s.find('A') + 1)
import heapq

n, m = list(map(int, input().split()))
cards = list(map(int, input().split()))
cards.sort()

queries = []
for i in range(m):
    q = list(map(int, input().split()))
    queries.append(q)
queries.sort(key=lambda x: x[1])
queries.reverse()

ans = 0
pos = 0
for q in queries:
    b, c = q
    if cards[min(pos+b-1, n-1)] < c:
        # print('a')
        pos = pos + b
        ans += c * b
        if pos == n:
            break
    else:
        for i in range(b):
            if cards[pos + i] < c:
                # print('b')
                ans += c
            else:
                # print('c')
                pos += i
                for j in range(pos, n):
                    ans += cards[j]

                pos = n
                break
        break

if pos < n:
    for j in range(pos, n):
        ans += cards[j]

print(ans)



### FIXED CODE ###

import heapq

n, m = list(map(int, input().split()))
cards = list(map(int, input().split()))
cards.sort()

queries = []
for i in range(m):
    q = list(map(int, input().split()))
    queries.append(q)
queries.sort(key=lambda x: x[1])
queries.reverse()

ans = 0
pos = 0
for q in queries:
    b, c = q
    if cards[min(pos+b-1, n-1)] < c:
        # print('a')
        pos = pos + b
        ans += c * (b - max(0, pos-n))
        if pos >= n:
            break
    else:
        for i in range(b):
            if cards[pos+i] < c:
                # print('b')
                ans += c
            else:
                # print('c')
                pos += i
                for j in range(pos, n):
                    ans += cards[j]

                pos = n
                break
        break

if pos < n:
    for j in range(pos, n):
        ans += cards[j]

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

ans=abs(abs(x)-abs(y))

if y<x<0 or 0<y<x:
    ans+=2

elif y<x x<0<y:
    ans+=1

print(ans)

### FIXED CODE ###

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

ans=abs(abs(x)-abs(y))

if y<x<0 or 0<y<x:
    ans+=2

elif y<x or x<0<y:
    ans+=1

print(ans)
n,a,b=map(int,input().split())
ans=0
for i in range(1,n+1):
  ii=list(i)
  ii=sum(ii)
  if ii in range(a,b+1):
    ans+=i
print(ans)

### FIXED CODE ###

a=list(map(int,input().split()))
sumy=0
for i in range(int(a[0]+1)):
    b=[]
    b+=str(i)
    c=0
    for t in range(len(b)):
        c+=int(b[t])
    if c>=a[1] and c<=a[2]:
        sumy+=i
print(sumy)
a,b=map(int,input().split())
s=sorted([input() for i in range(N)])
print(*s,sep="")

### FIXED CODE ###

n,l=map(int,input().split())
s=sorted([input() for i in range(n)])
print(*s,sep="")
n, k, q = list(map(int, input().split()))
a = [int(input()) for i in range(q)]
p = [k-q]*n

for i in range(q):
    p[a[i]] += 1

      
for n in p:
  if n>0:
    print("Yes")
  else:
    print("No")

### FIXED CODE ###

n, k, q = list(map(int, input().split()))
a = [int(input()) for i in range(q)]
p = [k-q]*n

for i in range(q):
    p[a[i]-1] += 1
    
for n in p:
  if n>0:
    print("Yes")
  else:
    print("No")
#! -*- coding:utf-8 -*-

def search(values,hp,vp,fruit):
    if not (0<=hp<len(values)): return
    if not (0<=vp<len(values[hp])): return
    if fruit!=values[hp][vp]: return
    values[hp][vp]=0
    search(values,hp-1,vp,fruit)
    search(values,hp+1,vp,fruit)
    search(values,hp,vp-1,fruit)
    search(values,hp,vp+1,fruit)

def solve(values):
    count=0
    for i in range(len(values)):
        for j in range(len(values[i])):
            if values[i][j] in ['@','#','*']:
                search(values,i,j,values[i][j])
                count+=1
    return count

def main():
    line=input()
    values=list()
    while line!='0 0':
        H,W = list(map(int,line.split(' ')))
        value = list()
        for _ in range(H):
            value.append([x for x in input().strip()])
    for value in values:
        print(solve(value))

if __name__=='__main__':
    main():

### FIXED CODE ###

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

import sys
sys.setrecursionlimit(10**6)

def search(field,hp,vp,item):
	if not (0<=hp<len(field)): return
	if not (0<=vp<len(field[hp])): return
	if item!=field[hp][vp]: return
	field[hp][vp]=True
	for dh,dv in [[0,1],[0,-1],[1,0],[-1,0]]:
		search(field,hp+dh,vp+dv,item)
#	search(field,hp-1,vp,item)
#	search(field,hp+1,vp,item)
#	search(field,hp,vp-1,item)
#	search(field,hp,vp+1,item)

def solve(field):
	count,valid_items=0,set(['@','#','*'])
	for i in range(len(field)):
		for j in range(len(field[i])):
			if field[i][j] in valid_items:
				search(field,i,j,field[i][j])
				count+=1
	return count

def main():
	line = input().strip()
	while line!='0 0':
		H,W = list(map(int,line.split(' ')))
		field = list()
		for _ in range(H):
			field.append(list(input().strip()))
		print(solve(field))
		line = input().strip()

if __name__=='__main__':
	main()
S=input()
# S = "??2??5"
# S= "?44"

MOD = 10**9+7
dp = {}
for i in range(13):
    dp[(-1,i)] = 0
dp[(-1,0)] = 1
for t,ss in enumerate(S[::-1]):
    for i in range(13):
        dp[(t,i)] = 0
    if ss=="?":
        for i in range(13):
            for j in range(10):
                dp[(t,(j*10**t+i)%13)] += dp[(t-1,i)]
                dp[(t,(j*10**t+i)%13)] %= MOD
    else:
        s = int(ss)
        for i in range(13):
            dp[(t,(s*10**t+i)%13)] += dp[(t-1,i)]
            dp[(t,(j*10**t+i)%13)] %= MOD


print(dp[(t,5)])

### FIXED CODE ###

S=input()
# S="".join(["?" for _ in range(10**5)])
# S = "??2??5"
# S= "?44"

MOD = 10**9+7
dp = [[0 for i in range(13)] for j in range(len(S)+1)]
dp[0][0] = 1
for t,ss in enumerate(S[::-1]):
    if t==0:
        tt = 1
    else:
        tt = (10*tt)%13
    if ss=="?":
        for i in range(13):
            for j in range(10):
                k = (j*tt+i)%13
                dp[t+1][k] += dp[t][i]%MOD
    else:
        s = int(ss)
        for i in range(13):
            k = (s*tt+i)%13
            dp[t+1][k] += dp[t][i]%MOD

print(dp[t+1][5]%MOD)
S = input()
a = S / 3600
b = S % 3600
c = b / 60
d = b % 60
print a + ":" + c + ":" + d

### FIXED CODE ###

S = input()
if S >= 0 and S <= 86400:
   a = S // 3600
   b = S % 3600
   c = b // 60
   d = b % 60
   print "%d:%d:%d" % (a, c, d)
while True:
    count = 0
    num = [int(i) for i in input().split("")]
    if num[0] == 0:
        break
    for n in num:
        count += n
    print(count + "\n")
     

### FIXED CODE ###

while True:
    x = input()
    if x == "0":
        break
    num = [int(i) for i in x]
    print(sum(num))
from itertools import accumulate as ac
n=int(input())
a,b=[],[]
for i in range(n):
    x,s=map(int,input().split())
    a.append(x)
    b.append(s)
r=[0]+list(ac(b))
l=r[:]
for i in range(n):
    r[i]+=-a[i]
    l[i+1]+=-a[i]
q,d=r[0],0
for i in range(1,n+1):
    d=max(l[i]-q,d)
    q=min(q,r[i-1])
print(d)

### FIXED CODE ###

k,a,b=map(int,input().split());print(1+2*((k-a-1)//(a-b)+1)if a-b>0 else(1 if k<=a else -1))
# avg_temp = temp - x * 0.006

input_str = input().split("\n")
# a = [int(x) for x in a]
number = int(input_str[0])

temp = int(input_str[1].split()[0])
goal = int(input_str[1].split()[1])

Hn = list(map(int, input_str[2].split()))

avg_temp = [(temp - (Hn * 0.006)) / goal for Hn in Hn]

if goal >= 0:
    print(int((avg_temp.index(max(avg_temp))) + 1))
else:
    print(int((avg_temp.index(min(avg_temp))) + 1))

### FIXED CODE ###

def main(n, t, a, h):
    def formula(t, x): return t - x * 0.006
    res = []

    for _h in h:
        res.append(abs(a - formula(t, _h)))

    print(res.index(min(res)) + 1)


if __name__ == "__main__":
    n = int(input())
    t, a = map(int, input().split(' '))
    h = list(map(int, input().split(' ')))

    main(n, t, a, h)
x=impot()
print(x**3)

### FIXED CODE ###

import sys

d = int(sys.stdin.readline().rstrip())
print(d**3)
S=input()
n=len(S)
ans=[]
for i in range(n):
  cnt=0
  for j in range(j,n):
    if S[j]=='A' or S[j]=='C' or S[j]=='G' or S[j]=='T':
      cnt+=1
  ans.append(cnt)
print(max(ans))

### FIXED CODE ###

s=list(input())
cnt=0
ans=0
l=list("ATCG")
 
for i in s:
    if i in l:
        cnt+=1
        ans=max(ans,cnt)
    else:
        cnt=0
print(ans)
n,k=map(int,input().split())
A=list(map(int,input().split()))
mod=10**9+7
A.sort()
def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod
N = 10**4
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル
for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )
ans,bns=0,0
for j in range(n-k+1):
  ans=(ans+(A[n-j-1]-A[j])*cmb(n-j-1,k-1,mod))%mod
print(ans%mod)

### FIXED CODE ###

n,k=map(int,input().split())
A=list(map(int,input().split()))
mod=10**9+7
A.sort()
def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod
N = 10**5
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル
for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )
ans,bns=0,0
for j in range(n-k+1):
  ans=(ans+(A[n-j-1]-A[j])*cmb(n-j-1,k-1,mod))%mod
print(ans%mod)
import sys
sys.setrecursionlimit(1000000000)

def modpow(x,p,mod):
    ret=1
    for i in range(100):
        if (1<<i)&p:
            ret=ret*x%mod
        x=x*x%mod
    return ret

def inverse_table(n,mod):
    table=[]
    for i in range(0,n+1):
        table.append(modpow(i,mod-2,mod))
    return table

def factorial_table(n,mod):
    table=[1]
    for i in range(1,n+1):
        table.append(table[-1]*i%mod)
    return table


it=inverse_table(10**5,1000000007)
ft=factorial_table(10**5,1000000007)

memo={}
def c(n,k,it,ft,mod):
    return ft[n]*it[ft[k]]*it[ft[(n-k)]]%mod

n,k=map(int,input().split())
a=sorted(map(int,input().split()))
hoge=[]
while True:
    hoge.append(c(n-1,k-1,it,ft,1000000007))
    if n-1==k-1:
        break
    n-=1
ans=0
for i in range(len(hoge)):
    ans-=hoge[i]*a[i]%1000000007
    ans+=hoge[i]*a[-i-1]%1000000007
    ans%=1000000007
print(ans)



### FIXED CODE ###

def modpow(x,p,mod):
    ret=1
    for i in range(64):
        if (1<<i)&p:
            ret=ret*x%mod
        x=x*x%mod
    return ret

def inverse_table(n,mod):
    table=[]
    for i in range(0,n+1):
        table.append(modpow(i,mod-2,mod))
    return table

def factorial_table(n,mod):
    table=[1]
    for i in range(1,n+1):
        table.append(table[-1]*i%mod)
    return table

def inverse_factorial_table(n,it,mod):
    table=[1]
    for i in range(1,n+1):
        table.append(table[-1]*it[i]%mod)
    return table

it=inverse_table(10**5,1000000007)
ft=factorial_table(10**5,1000000007)
ift=inverse_factorial_table(10**5,it,1000000007)
def c(n,k,it,ft,mod):
    return ft[n]*ift[k]*ift[(n-k)]%mod
n,k=map(int,input().split())
a=sorted(map(int,input().split()))
hoge=[]
while True:
    hoge.append(c(n-1,k-1,it,ft,1000000007))
    if n-1==k-1:
        break
    n-=1
ans=0
for i in range(len(hoge)):
    ans-=hoge[i]*a[i]%1000000007
    ans+=hoge[i]*a[-i-1]%1000000007
    ans%=1000000007
print(ans)
S = input()

count = 0
for j in range(4, len(S)+1):
    for i in range(len(S)-4):
        if S[i:i+4] % 2019 == 0:
            count += 1

print(count)

### FIXED CODE ###

S = input()

n = len(S)
m = 2019

S_ = S[::-1]

x = 1
total = 0
modlis = [0 for i in range(m)]

ans = 0
for i in range(n):
    modlis[total] += 1
    #print("S_[i]:", S_[i])
    #print("int(S_[i])*x:", int(S_[i])*x)
    #print("total:", total)
    total += int(S_[i])*x
    #print("total:", total)
    total %= m
    #print("total:", total)
    ans += modlis[total]
    #print("x:", x)
    x = x * 10 % m
    #print("x:", x)

print(ans)
d, g = map(int, input().split())
p = []
c = []
for _ in range(d):
    _p, _c = map(int, input().split())
    p.append(_p)
    c.append(_c)

res = 0
count = 0
ans_list = []

def dfs(i, p, c, res, count):
    if i == 0:
        if res >= g:
            ans_list.append(count)
    else:
        for j in reversed(range(p[i - 1] + 1)):
            _count = count + j
            _res = res + 100 * j * i
            if j == p[i - 1]:
                _res += c[i - 1]
            if res <= g:
                dfs(i - 1, p, c, _res, _count)
                break

dfs(d, p, c, res, count)
print(min(ans_list))

### FIXED CODE ###

import numpy as np
d, g = map(int, input().split())
p = []
c = []
for _ in range(d):
    _p, _c = map(int, input().split())
    p.append(_p)
    c.append(_c)

s = np.arange(1, d + 1) * 100
p = np.array(p)

ans_list = []

bool_list = [False] * d

state_list = []

def dfs(i, n, bool_list):
    bool_list = bool_list.copy()
    if i == n:
        state_list.append(bool_list)
    else:
        dfs(i + 1, n, bool_list)
        bool_list[i] = True
        dfs(i + 1, n, bool_list)

dfs(0, d, bool_list)

for state in state_list:
    if np.dot(s * p, state) + np.dot(c, state) >= g:
        ans_list.append(np.dot(p, state))
    else:
        score = max(s * np.array([not i for i in state]))
        for j in range(1, p[score//100 - 1] + 1):
            if np.dot(s * p, state) + np.dot(c, state) + score * j >= g:
                ans_list.append(np.dot(p, state) + j)

print(min(ans_list))
import itertools

n,m = map(int,input().split())
path=[[False]*n for _ in range(n)]
for _ in range(m):
  a,b = map(int,input().split())
  a-=1
  b-=1
  path[a][b]=True
  path[b][a]=True
ans=0
for i in itertools.permutations(range(n),n):
  if i[0]==0:
    for j in rannge(n):
      if j ==n-1:
        ans+=1
      if not path[i[j]][i[j+1]]:
        break
print(ans)

### FIXED CODE ###

import itertools

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

path = [[False] * n for i in range(n)]
for i in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    path[a][b] = True
    path[b][a] = True

ans = 0

# 頂点を並び替える順列を生成してループ
for i in itertools.permutations(range(n), n):
    # 頂点1が始点
    if i[0] == 0:
        # 生成した順列の中をさらにループ
        for j in range(n):
            # n - 1 まで続いたら条件を満たすパスが存在する
            if j == n - 1:
                ans += 1
                break
            # i[j] から i[j + 1] に行くパスがなければ終了
            if not path[i[j]][i[j + 1]]:
                break

print(ans)
import math
N = int(input())
A = list(map(int, input().split()))

ans = math.prod(A)

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


### FIXED CODE ###

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

A.sort()

if A[0] == 0:
  print(0)
  exit()

ans = 1
for a in A[::-1]:
  ans *= a
  if ans > 10**18:
    print('-1')
    break
else:
  print(ans)
a, b, x = map(int, input().split())
A = b//x
B = a//x
if a%x == 0:
    print(A-B+1)
else:
    print(A-B)

### FIXED CODE ###

a, b, c = map(str, input().split())
print(a[0]+b[0]+c[0])
h, w = map(int, input().split())
field = [list(input().split()) for _ in range(h)]
dx = [1, 0, -1, 0, 1, -1, -1, 1]
dy = [0, 1, 0, -1, 1, 1, -1, -1]
for i in range(h):
    for j in range(w):
        if field[i][j] != "#":
            num = 0
            for k in range(8):
                ni = i + dy[k]
                nj = j + dx[k]
                if nj < 0 or h <= nj:
                    continue
                if ni < 0 or w <= ni:
                    continue
                if field[ni][nj] == "#":
                    num += 1
            field[i][j] = num
for out in field:
    print("".join(out))


### FIXED CODE ###

h, w = map(int, input().split())
field = [list(input()) for _ in range(h)]
dx = [1, 0, -1, 0, 1, -1, -1, 1]
dy = [0, 1, 0, -1, 1, 1, -1, -1]
for i in range(h):
    for j in range(w):
        if field[i][j] == "#":
            continue
        num = 0
        for k in range(8):
            ni = i + dy[k]
            nj = j + dx[k]
            if ni < 0 or h <= ni:
                continue
            if nj < 0 or w <= nj:
                continue
            if field[ni][nj] == "#":
                num += 1
        field[i][j] = str(num)
for out in field:
    print("".join(out))
a,b,c,d=map(int,input().split())
print(min(b,d)-max(a,c))


### FIXED CODE ###

n=list(map(int,input()))
re=n[::-1]
for i in range(len(n)):
    if n[i]==re[i]:
        print("Yes")
        break
    else:
        print("No")
        break
n = int(input())
a = list(map(int,input().split()))
b = []
c = 0
for i in range(1,n):
    s = a[i-1]-a[i]
    if s >= 0:
        s = s+c 
        b.append(s)
        c = max(c,s)
    else:
        c = 0
        b.append(c)
print(sum(b)

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
b = []
c = 0
for i in range(1,n):
    c = max(c,a[i-1])
    s = c-a[i]
    if s >= 0:
        b.append(s) 
print(sum(b))
def e():
    N, W = map(int, input().split())
    wv = [list(map(int, input().split())) for _ in range(N)]
    dp = [[0] * (W + 1) for _ in range(N + 1)]
    for i in range(N):
        for j in range(W + 1):
            if j - wv[i][0] >= 0:
                dp[i + 1][j] = max(dp[i + 1][j],
                                   dp[i][j - wv[i][0]] + wv[i][1])
            dp[i + 1][j] = max(dp[i + 1][j], dp[i][j])
    return dp[-1][-1]


if __name__ == '__main__':
    ans = e()
    print(ans)


### FIXED CODE ###

def e():
    N, W = map(int, input().split())
    wv = [list(map(int, input().split())) for _ in range(N)]
    v = [wv[i][1] for i in range(len(wv))]
    V = sum(v)
    dp = [[10 ** 9] * (V + 1) for _ in range(N + 1)]
    dp[0][0] = 0
    for i in range(N):
        for j in range(V + 1):
            if j - wv[i][1] >= 0:
                dp[i + 1][j] = min(dp[i + 1][j],
                                   dp[i][j - wv[i][1]] + wv[i][0])
            dp[i + 1][j] = min(dp[i + 1][j], dp[i][j])
    for k, p in enumerate(dp[-1]):
        if p <= W:
            r = k
    return r


if __name__ == '__main__':
    ans = e()
    print(ans)
a, b, c, d = [int(t) for t in input(t)]
print(max([b*d, a*c, a*d, b*d]))

### FIXED CODE ###

a, b, c, d = [int(t) for t in input().split()]
print(max([b*d, a*c, a*d, b*c]))
n, k = (int(i) for i in input().split())  
s=str(input())
if k == n:
    r=s[0:(k-1)] + s[n].lower()
elif k == 1:
    r=s[0].lower() + s[1:n]
else:
    r=s[0:(k-1)] + s[k-1].lower() + s[k:n]
print(r)

### FIXED CODE ###

n, k = (int(i) for i in input().split())  
s=str(input())
if k == n:
    r=s[0:(k-1)] + s[n-1].lower()
elif k == 1:
    r=s[0].lower() + s[1:n]
else:
    r=s[0:(k-1)] + s[k-1].lower() + s[k:n]
print(r)
import numpy as np
def Expected_Value(x):
    EV = 0
    for i in range(1,x+1):
        EV += i/x
    return EV
N, K = map(int, input().split())
pi = np.array(list(map(int, input().split())))
ma = 0
for i in range(N-K+1):
    x = sum(pi[i:i+K])
    if x > ma:
        ma = x
        max_index = i
array_max = (np.array(pi[max_index:max_index+K])-1) *0.5 + 1
print(array_max.sum())

### FIXED CODE ###

S, T = map(str,input().split())
A, B = map(int,input().split())
U = input()
if U == S:
    A -= 1
else:
    B -= 1
print(str(A) +' '+ str(B))