Harryxun/stf_run huggingface dataset:
import collections

#入力
H, W = map(int, input().split())

#lst = [['a']*W for _ in range(H)]
count = 0 #白色のマスの総数
lst = []
row = []
for i in range(H):
    row = list(input())
    count += row.count('.')
    lst += [row]
 
#for i in range(H):
#    for j in range(W):
#        if lst[i][j] == '.':
#            count += 1

sx, sy = 1, 1 #スタート位置
gx, gy = H, W #ゴール位置

move = [[-1, 0], [1,0], [0, -1], [0, 1]]

def bfs():
    q = collections.deque()
    INF = 10 ** 3
    d = [[INF]* W for _ in range(H)]
    q.append(0)
    q.append(0)
    d[0][0] = 0

    while True:
        if q.empty():
            break
        px = q.popleft()
        py = q.popleft()
        if px == gx-1 and py == gy-1:
            break
        else:
            for dx, dy in move:
                nx = px + dx
                ny = py + dy

                if 0 <= nx and nx < H and 0 <= ny and ny < W and lst[nx][ny] == '.' and d[nx][ny] == INF:
                    q.append(nx)
                    q.append(ny)
                    d[nx][ny] = d[px][py] + 1
    return d[gx-1][gy-1]

a = bfs()

if a == 10 **9:
    print (-1)
else:
    print (count - a - 1)

### FIXED CODE ###

from queue import Queue

#入力
H, W = map(int, input().split())

#lst = [['a']*W for _ in range(H)]
count = 0 #白色のマスの総数
lst = []
row = []
for i in range(H):
    row = list(input())
    count += row.count('.')
    lst += [row]
 
#for i in range(H):
#    for j in range(W):
#        if lst[i][j] == '.':
#            count += 1

#sx, sy = 1, 1 #スタート位置
#gx, gy = H, W #ゴール位置

move = [[-1, 0], [1,0], [0, -1], [0, 1]]

def bfs():
    q = Queue()
    INF = 10 ** 9
    d = [[INF]* W for _ in range(H)]
    q.put(0)
    q.put(0)
    d[0][0] = 0

    while True:
        if q.empty():
            break
        else:
            px = q.get()
            py = q.get()
            if px == H-1 and py == W-1:
                break
            else:
                for dx, dy in move:
                    nx = px + dx
                    ny = py + dy

                    if 0 <= nx and nx < H and 0 <= ny and ny < W and lst[nx][ny] == '.' and d[nx][ny] == INF:
                        q.put(nx)
                        q.put(ny)
                        d[nx][ny] = d[px][py] + 1
    return d[H-1][W-1]

a = bfs()

if a == 10 **9:
    print (-1)
else:
    print (count - a - 1)
#!/usr/bin/env python
import sys

def _ia(): return [ int(x) for x in sys.stdin.readline().strip().split() ]

n,t = _ia()
ab = []
imax = -1
amax = -1
bmax = -1
for i in range(n):
    _a,_b = _ia()
    ab.append((_a,_b))
    if bmax<0 or (_b>=bmax and _a>ab[imax][0]):
        imax = i
        amax = _a
        bmax = _b
#
dp = [ 0 ] * (t+1)
for i, _ab in enumerate(ab):
    if i==imax: continue
    a,b = _ab
    prev = dp.copy()
    for atot in range(t+1):
        if atot>=a:
            dp[atot] = max(prev[atot],prev[atot-a]+b)
        else:
            dp[atot] = prev[atot]
#
print(max(dp[t-1]+bmax,dp[t]))


### FIXED CODE ###

#!/usr/bin/env python
import sys
from operator import itemgetter

def _ia(): return [ int(x) for x in sys.stdin.readline().strip().split() ]

n,t = _ia()
ab = []
for i in range(n): ab.append(_ia())
ab.sort(key=itemgetter(0))
#
bmax= ab[0][0]
dp = [ [0]*(t) for _ in range(n) ]
for i in range(n-1):
    a,b = ab[i]
    
    prev = dp[i]
    dnew = dp[i+1]
    for atot in range(t):
        if atot>=a: dnew[atot] = max(prev[atot],prev[atot-a]+b)
        else: dnew[atot] = prev[atot]
    #
    bmax = max(bmax,prev[-1]+b)
#
print(max(bmax,dp[-1][-1]+ab[-1][1]))
# -*- coding: utf-8 -*-

import sys
import math


sys.setrecursionlimit(10 ** 6)

input_line = input()
inputs = input_line.split(' ')
A, = list(map(int, inputs))

print(2*R*math.pi)


### FIXED CODE ###

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

import sys
import math


sys.setrecursionlimit(10 ** 6)

input_line = input()
inputs = input_line.split(' ')
R, = list(map(int, inputs))

print(2*R*math.pi)
a, b = input().split()
c = int(a+b)
d = math.sqrt(c)
if d%1 == 0:
  print("Yes")
else:
  print("No")

### FIXED CODE ###

import math
a, b = input().split()
c = a+b
c = int(c)
d = math.sqrt(c)
if d%1 == 0:
  print("Yes")
else:
  print("No")
N = int(input())
hight = list(map(int, input().split()))

def smaller(n,m):
  if n >= m:
    return m
  else:
    return n

a = 0

for i in range(0,N):
  for j in range(i+1,smaller(N,100)):
    if j-i == hight[i] + hight[j]:
      a = a+1

print(a)

distance = [0]


### FIXED CODE ###

X = int(input())

ans = [0,0]
for i in range(-500,500):
  for j in range(-500,500):
    if i**5 - j**5 == X:
      ans[0] = i
      ans[1] = j
      break

ans = " ".join(map(str,ans))
print(ans)
#coding:utf-8
r,D,x = map(int,input().split())
x2001 = r * X - D
x2002 = r * X2001 -D
x2003 = r * X2002 - D
x2004 = r * X2003 - D
x2005 = r * X2004- D
x2006 = r * X2005- D
x2007 = r * X2006 - D
x2008 = r * X2007 - D
x2009 = r * X2008 - D
x2010 = r * X2009 - D
X = [x2001,x2002,x2003,x2004,x2005,x2006,x2007.x2008,x2009,x2010]
print(X)

### FIXED CODE ###

#coding:utf-8
r,D,x = map(int,input().split())
x2001 = r * x - D
x2002 = r * x2001 - D
x2003 = r * x2002 - D
x2004 = r * x2003 - D
x2005 = r * x2004 - D
x2006 = r * x2005 - D
x2007 = r * x2006 - D
x2008 = r * x2007 - D
x2009 = r * x2008 - D
x2010 = r * x2009 - D
print(x2001)
print(x2002)
print(x2003)
print(x2004)
print(x2005)
print(x2006)
print(x2007)
print(x2008)
print(x2009)
print(x2010)
N = int(input())
rate = [0] * 9
for a in [int(x) for x in input().split()]:
  rate[a // 400] += 1

ret = 0
for r in rate[:-1]:
  if r:
    ret += 1

print(ret, ret + rate[-1])

### FIXED CODE ###

N = int(input())
rate = [0] * 9
for a in [int(x) for x in input().split()]:
  rate[min(a, 3200) // 400] += 1

ret = 0
for r in rate[:-1]:
  if r:
    ret += 1

print(max(ret, 1), ret + rate[-1])
inp = input()
m = 0
n = 0
li = ['dream','dreamer','erase','eraser']
while True:
    for i in li:
        if inp.startswith(i):
    	    inpp = inp.replace(i,'',1)
    	    if inpp == '':
    		    m = 1
    		    break
    	    for k in li:
    	    	if inpp.startswith(k):
    		        inp = inpp
    		        n = 1
    		        break
    	    else:
                if k == 'eraser':
                	break
    	    	continue
    	    break
    if m == 1:
    	print('YES')
    	break
    if n != 1:
    	print('NO')
    	break

### FIXED CODE ###

inp = input()
inp = inp[::-1]
li = ['dream','dreamer','erase','eraser']
li = [k[::-1] for k in li]
m = 0
while True:
    for i in li:
        if inp.startswith(i):
    	    inp = inp.replace(i,'',1)
    	    m = 0
    else:
    	if m == 1:
    		break
    	else:
    		m = 1
    		continue
    break
if inp == '':
	print("YES")
else:
	print("NO")
n, k = map(int, input().split())

mo = n%k

mok = abs(mo - k)

if mo <= mok:
    print(mo)
else:
    print(mok)

### FIXED CODE ###

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

print(z, x, y)
import fractions

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

lcm = list[0]
for i in range(1, N):
    lcm = lcm * list[i] // fractions.gcd(lcm, list[i])



ans = 0

for i in range(N):
  ans += int(lcm / list[i])

print(ans % (10**9 + 7))


### FIXED CODE ###

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

def gcd(a, b):
  while b:
    a, b = b, a % b
  return a

def lcm(a, b):
  return a * b // gcd (a, b)

alllcm = 1

for i in range(N):
  alllcm = lcm(alllcm, list[i])

ans = 0

for i in range(N):
  ans += alllcm // list[i]

print(ans % (10**9 + 7))
x=input()
t=0
for i in range(len(x)-1,-1,-1):
  if x[i]=='T':
    t+=1
  else:
    if t>0:
      t-=1
    else:
      s+=1
print(s+t)

### FIXED CODE ###

x=input()
t=0;s=0
for i in range(len(x)-1,-1,-1):
  if x[i]=='T':
    t+=1
  else:
    if t>0:
      t-=1
    else:
      s+=1
print(s+t)
X=int(input())
n=0
while n<10**5:
    A=X-(n**5)
    check=(A**0.2)**5
    if(int(check)==check):
        AnsA=A**0.2
        AnsB=-n
        print(str(int(AnsA))+" "+str(int(AnsB)))
        break
    else:
        n=n+1
m=0
while m<10**5:
    A=X+(m**5)
    check=(A**0.2)**5
    if(int(check)==check):
        AnsA=A**0.2
        AnsB=-m
        print(str(int(AnsA))+" "+str(int(AnsB)))
        break
    else:
        m=m+1

### FIXED CODE ###

X=int(input())

for A in range(-1000,1000):
    for B in range (-1000,1000):
        if(A**5-B**5==X):
            print(A,B)
            break
    else:
        continue
    break
import sys
sys.setrecursionlimit(10000)

def main():
    N = int(input())
    visited = [False] * N
    d = [[] for _ in range(N)]
    for i in range(N-1):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        d[a].append((b,i))
        d[b].append((a,i))

    ans = [0] * (N - 1) 

    def dfs(v, c, p):
        k = 1
        for i in range(len(d[v])):
            u = d[v][i][0]
            ei = d[v][i][1]
            if u == p:
                continue
            if k == c:
                k += 1
            ans[ei] = k
            k += 1
            dfs(u,ans[ei],v)
    
    dfs(0,-1,-1)
    print(max(ans))
    for a in ans:
        print(a)

        

if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(4100000)

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

    ans = [0] * (N - 1) 

    def dfs(v, c, p):
        k = 1
        for i in range(len(d[v])):
            u = d[v][i][0]
            ei = d[v][i][1]
            if u == p:
                continue
            if k == c:
                k += 1
            ans[ei] = k
            k += 1
            dfs(u,ans[ei],v)
    
    dfs(0,-1,-1)
    print(max(ans))
    for a in ans:
        print(a)

        

if __name__ == "__main__":
    main()
import collections
N, K = [int(_) for _ in input().split()]
A1 = [int(_) for _ in input().split()]
A = A1 * 2
a_i = collections.defaultdict(lambda: [])
for i, a in enumerate(A):
    a_i[a] += [i]
i_delta = [0] * (2 * N)
for a in a_i:
    array = a_i[a]
    for i in range(len(array) - 1):
        i_delta[array[i]] = array[i + 1] - array[i] + 1
first = [-1] * N
second = [-1] * N
i = 0
while second[i % N] == -1:
    if first[i % N] == -1:
        first[i % N] = i
    else:
        second[i % N] = i
        break
    i += i_delta[i % N]
i %= N
start = first[i] + (second[i] - first[i]) * (
    (N * K - first[i]) // (second[i] - first[i]))
end = N * K
B = A1[N - (end - start) % N:] + A1 * ((end - start) // N)
dp = [{}]
for i, b in enumerate(B):
    if b in dp[-1]:
        dp = dp[:dp[-1][b]]
    else:
        s = dp[-1].copy()
        s[b] = len(dp)
        dp += [s]
print(*list(a for a, _ in sorted(dp[-1].items(), key=lambda xs: xs[1])))


### FIXED CODE ###

import bisect
N, K, *A = [int(_) for _ in open(0).read().split()]
K -= 1
L = [[] for _ in range(2 * 10**5 + 1)]
for i, a in enumerate(A * 2):
    L[a] += [i]
before_next = [L[a][bisect.bisect(L[a], i)] for i, a in enumerate(A)]
first_cycle = [None] * N
now = 0
idx = 0
cycle = 0
while True:
    if first_cycle[now] is not None:
        break
    first_cycle[now] = cycle
    now = before_next[now] + 1
    dcycle, now = divmod(now, N)
    cycle += dcycle
cycle2 = cycle
cycle1 = first_cycle[now]
#K cycle目=cycle1+(K-cycle1)%(cycle2-cycle1) cycle目
K2 = cycle1 + (K - cycle1) % (cycle2 - cycle1)
if K2:
    f1 = f2 = 0
    for i in range(N - 1, -1, -1):
        if first_cycle[i] == K2 - 1:
            f1 = 1
            break
    for j in range(N - 1, -1, -1):
        if first_cycle[j] == K2:
            f2 = 1
            break
    if f2:
        B = A[j:]
    elif f1:
        B = A[i:] + A
else:
    B = A
ans = []
cnt = [0] * (2 * 10**5 + 1)
for a in B:
    if cnt[a] > 0:
        while True:
            cnt[ans.pop()] -= 1
            if cnt[a] == 0:
                break
    else:
        ans += [a]
        cnt[a] += 1
print(' '.join(map(str, ans)))
n = int(input())
d = list(map(int,input().split()))
comb_sum = 0
for i in range(n-1):
  for j in range(i+1,n):
    comb_sum += d[i] * d[j]
print(comb_sum)

### FIXED CODE ###

a , b = map(int,input().split())
if a <= b *2:
	print(0)
else:
	print(a - b *2)
x,n = map(int,input().split())

arr = [x]
tmp = input()
num = tmp.split(' ')
num_li = [int(i) for i in num]
arr.extend(num_li)

arr.sort()
arr = list(set(arr))

min = x
max = x

for i in range(10000):
    if len(arr) == 1:
        print(x)
        break

    min -= 1
    max += 1

    if min not in arr:
        print(min)
        break

    if max not in arr:
        print(max)
        break

### FIXED CODE ###

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

arr = []

if n == 0:
    print(x)
else:
    tmp = input()
    num = tmp.split(' ')
    num_li = [int(i) for i in num]
    arr.extend(num_li)

    for i in range(10000):

        if x - i not in arr:
            print(x - i)
            break

        if x + i not in arr:
            print(x + i)
            break
s = int(input()).split(" ")
print("bust") if sum(s) >= 22 else print("win")

### FIXED CODE ###

a = [int(x) for x in input().split(" ")]
print("bust") if sum(a) >= 22 else print("win")
N = int(input())
ratio = [tuple(map(int, input().split())) for _ in range(N)]
t,a = 1,1

for nt,na in ratio:
    if nt<t or na<a:
        r = max(-(-t//nt), -(-a//na)
        nt *= r
        na *= r
    t,a = nt,na
    #print(t, a)
print(t+a)


### FIXED CODE ###

N = int(input())
ratio = [tuple(map(int, input().split())) for _ in range(N)]
t,a = 1,1

for nt,na in ratio:
    if nt<t or na<a:
        r = max((t-1)//nt+1, (a-1)//na+1)
        nt *= r
        na *= r
    t,a = nt,na
    #print(t, a)
print(t+a)
import numpy as np
N = int(input())
data_xy = []
for i in range(N):
    A = int(input())
    xy = []
    for i in range(A):
        [x,y] = list(map(int,input().split()))
        xy.append([x-1, y])
    data_xy.append(xy)
data_xy = np.array(data_xy,dtype=np.int64)
ans = 0
for i in range(2**N):
    p_list = [0]*N
    for j in range(N):
        if (i>>j) & 1 == 1:
            p_list[j] = 1
    flag = True
    for j in range(N):
        if p_list[j] == 1:
            for k in range(len(data_xy[j])):
                x = data_xy[j][k][0]
                y = data_xy[j][k][1]
                if p_list[x] != y:
                    flag = False
    if flag == True:
        ans = max(sum(p_list),ans)
print(ans)

### FIXED CODE ###

A = list(map(int,input().split()))
if sum(A) >= 22:
    print('bust')
else:
    print('win')
a,b,c = map(int,input().split())
n = a-b
print(n%c)

### FIXED CODE ###

a,b,c = [int(input()) for i in range(3)]
n = a-b
print(n%c)
N=int(input())
S=list(input())
change_min=N
for leader in range(N):
    S_west=S[:leader]
    S_east=S[leader+1:N]
    change=S_west.count("W")+S_east.count("E")
    if change<=change_min:
        change_min=change
print(change_min)
        

### FIXED CODE ###

a,b=map(int, input().split())
ab_sum=a+b
ab_dif=a-b
ab_pro=a*b
ab_max=max(ab_sum,ab_dif,ab_pro)
print(ab_max)
S = input()
if 1 <= int(S[:2]) <= 12 and 1 <= int(S[2:]) <= 12:
    print("AMBIGUOUS")
elif int(S[:2]) > 12 and int(S[2:]) != 0:
    print("YYMM")
elif int(S[2:]) > 12 int(S[:2]) != 0:
    print("MMYY")
else:
    print("NA")

### FIXED CODE ###

S = input()
if 1 <= int(S[:2]) <= 12 and 1 <= int(S[2:]) <= 12:
    print("AMBIGUOUS")
elif 1 <= int(S[2:]) <= 12:
    print("YYMM")
elif 1 <= int(S[:2]) <= 12:
    print("MMYY")
else:
    print("NA")
s = input()
for i in range(0,len(s)//2):
  if (s[i]!=s[-i-1]):
    print("No")
    break
  if (i == len(s)//2-1)
    print("Yes")


### FIXED CODE ###

s = input()

def check(s):
  if len(s) == 1 or len(s) == 0:
    return True
  if s[0]!=s[-1]:
    return False
  return check(s[1:-1])

mid = len(s)//2

if check(s) and check(s[0:mid]) and check(s[mid+1:]):
  print("Yes")
else:
  print("No")
N, M = map(int, input().split())

group = []

MOD = 1000000007

if M == 0:
    group.append(N+1)
else:
    pre_a = int(input())
    group.append(pre_a)

    for i in range(M-1):
        a = int(input())
        tmp = a - pre_a - 1
        pre_a = a
        group.append(tmp)
    group.append(N - pre_a)

if 0 in group or -1 in group:
    print(0)
else:
    fiv = [1 for i in range(max(group))]
    fiv[0] = 1
    fiv[1] = 1
    for i in range(2, len(fiv)):
        fiv[i] = (fiv[i-1] + fiv[i-2]) % MOD
    ans = 1
    for g in group:
        ans *= fiv[g-1]
        ans %= MOD
    print(ans)


### FIXED CODE ###

import sys
input = sys.stdin.readline

def main():
    N, M =map(int, input().split())
    a = [int(input()) for i in range(M)]

    sep = []
    pre = -1
    ok = True
    for t in a:
        tmp = t - pre - 1
        if tmp == 0:
            ok = False
            break
        sep.append(tmp)
        pre = t
    sep.append(N-pre)
    # print(sep)

    if not ok:
        print(0)
        return
    max_sep = max(sep)

    MOD = 1000000007
    fib = [1] * (max_sep)
    for i in range(2, max_sep):
        fib[i] = fib[i-2] + fib[i-1]
        fib[i] %= MOD
    
    ans = 1
    for s in sep:
        ans *= fib[s-1]
        ans %= MOD
    print(ans)


if __name__ == "__main__":
    main()
K = int(input())

ans_list = []
def dfs(A):
    if len(A)!=0 and int("".join(A))<=10**5:
        ans_list.append(int("".join(A)))
    elif len(A)!=0 and int("".join(A))>10**5:
        return
    if len(A)==0:
        for i in range(1, 10, 1):
            A.append(str(i))
            dfs(A)
            A.pop()
        return

    for i in range(0, 10, 1):
        if abs(int(A[-1])-i)<=1:
            A.append(str(i))
            dfs(A)
            A.pop()
    return
dfs([])
ans_list.sort()
print(ans_list[K-1])

### FIXED CODE ###

import sys
sys.setrecursionlimit(500000)
K = int(input())

ans_list = []

def dfs(l):
    if len(l)==1 and l[0]!="0":
        ans_list.append(int("".join(l)))
    if l!=[] and l[0]=="0":
        return
    if l!=[] and int("".join(l))>3234566667:
        return
    for i in ["0", "1", "2", "3", "4", "5", "6", "7", "8", "9"]:
        l.append(i)
        #ここで絶対値1以下になるものだけdfs
        if len(l)==1:
            dfs(l)
            l.pop()
        elif abs(int(l[len(l)-2])-int(l[len(l)-1]))<=1:
            dfs(l)
            ans_list.append(int("".join(l)))
            l.pop()
        else:
            l.pop()

    return

dfs([])
ans_list.sort()
print(ans_list[K-1])
import bisect,collections,copy,heapq,itertools,math,numpy,string
import sys
f = open('input.txt', 'r')
sys.stdin = f

N, M = map(int, input().split())
As = list(map(int, input().split()))
d = sum(As)
if N < d:
    print(-1)
else:
    print(N-d) 


### FIXED CODE ###

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

d = sum(A)

if N < d:
  print(-1)
else:
  print(N-d)
import sys
rr = lambda: sys.stdin.readline().strip()
ri = lambda: int(rr())
rs = lambda: [int(_) for _ in rr().split()]

S = rr()

if not 1 <= int(S[:1]) <= 12:
    if not 1 <= int(S[2:]) <= 12:
        print('NA')
    else:
        print('YYMM')
elif not 1 <= int(S[2:]) <= 12:
	if not 1 <= int(S[1:]) <= 12:
        print('NA')
    else:
        print('MMYY')
else:
    print('AMBIGUOUS')

### FIXED CODE ###

import sys
rr = lambda: sys.stdin.readline().strip()
ri = lambda: int(rr())
rs = lambda: [int(_) for _ in rr().split()]

S = rr()

if not 1 <= int(S[:2]) <= 12:
    if not 1 <= int(S[2:]) <= 12:
        print('NA')
    else:
        print('YYMM')
elif not 1 <= int(S[2:]) <= 12:
	print('MMYY')
else:
    print('AMBIGUOUS')
from collections import deque, Counter, defaultdict
from itertools import chain, combinations
import json
# import numpy as np
import bisect
import sys
import math
import bisect
from functools import lru_cache
import itertools

sys.setrecursionlimit(10 ** 8)

M = 10 ** 9 + 7
INF = 10 ** 17


def main():
    N = int(input())
    A = [int(a) for a in input().split()]
    # N, K = [int(a) for a in input().split()]
    # A = [int(a) for a in input().split()]
    # T1, T2, T3 = [int(a) for a in input().split()]

    aa = []
    t = A[0]
    start = A[0]
    for ai in A[1:]:
        if t <= ai:
            t = ai
            if start is None:
                start = ai
            continue
        aa.append(
            (start, t)
        )
        t = ai
        start = None
    if start is not None:
        aa.append((start, A[-1]))

    m = 1000
    for a, b in aa:
        c = m // a
        m += (b - a) * c
    print(m)


if __name__ == "__main__":
    main()


### FIXED CODE ###

from collections import deque, Counter, defaultdict
from itertools import chain, combinations
import json
# import numpy as np
import bisect
import sys
import math
import bisect
from functools import lru_cache
import itertools

sys.setrecursionlimit(10 ** 8)

M = 10 ** 9 + 7
INF = 10 ** 17


def main():
    N = int(input())
    A = [int(a) for a in input().split()]
    # N, K = [int(a) for a in input().split()]
    # A = [int(a) for a in input().split()]
    # T1, T2, T3 = [int(a) for a in input().split()]

    aa = []
    t = A[0]
    start = A[0]
    for ai in A[1:]:
        if t <= ai:
            t = ai
            if start is None:
                start = ai
            continue
        aa.append(
            (start, t)
        )
        t = ai
        start = ai
    if start is not None:
        aa.append((start, A[-1]))

    m = 1000
    for a, b in aa:
        if a is None:
            continue
        c = m // a
        m += (b - a) * c
    print(m)


if __name__ == "__main__":
    main()
N, W = [int(i) for i in input().split()]
weight, value = [0] * (N + 1), [0] * (N + 1)
for i in range(1, N + 1):
    weight[i], value[i] = [int(i) for i in input().split()]
#%%
import  numpy as np
dp = np.zeros((N + 1, W + 1))

#%%
for i in range(1, N + 1):
    for j in range(1, W + 1):
        if weight[i] <= j:
            dp[i][j] = max(value[i] + dp[i - 1][j - weight[i]], dp[i - 1][j])
        else:
            dp[i][j] = dp[i - 1][j]
print(int(dp[-1][-1]))



### FIXED CODE ###

N, W = [int(i) for i in input().split()]
weight, value = [0] * (N + 1), [0] * (N + 1)
for i in range(1, N + 1):
    weight[i], value[i] = [int(i) for i in input().split()]
#%%
dp = [[0] * (W + 1) for _ in range(N + 1)]

#%%
for i in range(1, N + 1):
    for j in range(1, W + 1):
        if weight[i] <= j:
            dp[i][j] = max(value[i] + dp[i - 1][j - weight[i]], dp[i - 1][j])
        else:
            dp[i][j] = dp[i - 1][j]
print(int(dp[-1][-1]))
def list_pos(cnt,a,b,ans):
    if ans  >= b :
        return cnt-1
    else :

        ans += a[cnt][1]
        cnt += 1
        return list_pos(cnt,a,b,ans)

N,K = map(int,input().split())
para = {}
for i in range(N):
    a,b  = map(int,input().split())
    if not a in para.keys():
        para[a] = b
    else : para[a] += b

para = sorted(para.items(),key =lambda x:x[0])

p = list_pos(0,para,K,0)
print("{}".format(para[p][0]))


### FIXED CODE ###


def list_pos(cnt,a,b,ans):
    if ans  >= b :
        return cnt-1
    else :

        ans += a[cnt][1]
        cnt += 1
        return list_pos(cnt,a,b,ans)
import sys
sys.setrecursionlimit(100000)
N,K = map(int,input().split())
para = {}
for i in range(N):
    a,b  = map(int,input().split())
    if not a in para.keys():
        para[a] = b
    else : para[a] += b

para = sorted(para.items(),key =lambda x:x[0])

p = list_pos(0,para,K,0)
print("{}".format(para[p][0]))
while True:
    a, b = map(int, raw_input().split())
    def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a%b)
    g = gcd(a,b)
    l = a * b/gcd(a,b)
    print g, l

### FIXED CODE ###

while True:
    try:
        a, b = map(int, raw_input().split())
        def gcd(a, b):
            if b == 0:
                return a
            else:
                return gcd(b, a%b)
        g = gcd(a,b)
        l = a*b/g
        print g, l
    except:
        break
mod = 10 ** 9 + 7

N = int(input())

result = 0

ten = pow(10, N, mod)
nine = pow(9, N, mod)
eight = pow(8, N, mod)

result = (ten - 2 * nine + eight) % mode

print(result)

### FIXED CODE ###

mod = 10 ** 9 + 7

N = int(input())

result = 0

ten = pow(10, N, mod)
nine = pow(9, N, mod)
eight = pow(8, N, mod)

result = (ten - 2 * nine + eight) % mod

print(result)
a = int(input())
b = int(input())
if int(a), int(b) in range(1, 100):
    print(a*b)

### FIXED CODE ###

a, b = map(int, input().split())
print(int(a*b))