Harryxun/stf_run huggingface dataset:
import sys
from heapq import *

input = sys.stdin.readline

def main():
    def get_group(k):
        g = ps[k]
        if g < 0:
            return k
        gg = get_group(g)
        ps[k] = gg
        return gg

    def merge(j, k):
        g1 = get_group(j)
        g2 = get_group(k)
        if g1 != g2:
            s1 = -ps[g1]
            s2 = -ps[g2]
            if s2 > s1:
                g1, g2 = g2, g1
            ps[g1] = -(s1 + s2)
            ps[g2] = g1

    hp = []
    n, h, w = map(int, input().split())
    ps = [-1] * (h + w + 2)  # 親(parent)と大きさ(size)。0以上は親のノード。負の場合、そのノードが根で絶対値が大きさ。
    for _ in range(n):
        r, c, a = map(int, input().split())
        heappush(hp, [-a, r, h + c])
    cnt = h + w
    ans = 0
    while cnt and hp:
        a, r, c = heappop(hp)
        gr = get_group(r)
        gc = get_group(c)
        if gr + gc == 0:
            continue
        if gr == gc:
            ps[gr] = 0
        else:
            merge(gr, gc)
        ans -= a
        cnt -= 1
    print(ans)

main()


### FIXED CODE ###

import sys
from heapq import *

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline

def main():
    def get_group(k):
        g = pd[k]
        if g < 0:
            return k
        gg = get_group(g)
        pd[k] = gg
        return gg

    def merge(j, k):
        g1 = get_group(j)
        g2 = get_group(k)
        if g1 != g2:
            d1 = -pd[g1]
            d2 = -pd[g2]
            if d2 > d1:
                g1, g2 = g2, g1
            pd[g2] = g1
            if d1 == d2:
                pd[g1] -= 1

    hp = []
    n, h, w = map(int, input().split())
    pd = [-1] * (h + w + 2)  # 親(parent)と深さ(depth)。0以上は親。負の場合、そのノードが根で絶対値が深さ。
    pd[0] = -(h + w + 2)
    for _ in range(n):
        r, c, a = map(int, input().split())
        heappush(hp, [-a, r, h + c])
    cnt = h + w
    ans = 0
    while cnt and hp:
        a, r, c = heappop(hp)
        gr = get_group(r)
        gc = get_group(c)
        if gr + gc == 0: continue
        if gr == gc:
            merge(gr, 0)
        else:
            merge(gr, gc)
        ans -= a
        cnt -= 1
    print(ans)

main()
N = int(input())
K = int(input())
P = list(map(int,input().split()))
for i in range(N):
  P[i] = (P[i]+1)/2
now = sum(P[:K])
ans = now
for j in range(N-K):
  ans = ans - P[j] + P[j+K]
  ans = max(ans,now)
print(ans)



### FIXED CODE ###

N,K = map(int,input().split())
P = list(map(int,input().split()))
for i in range(N):
  P[i] = (P[i]+1)/2
now = sum(P[:K])
ans = now
for j in range(N-K):
  now = now - P[j] + P[j+K]
  ans = max(ans,now)
print(ans)
n = int(input())
student = list(map(int,input().split()))
a = [0]*n
 
for i in range(n):
  s = student[i] #生徒が出席した番号をメモ
  a[s-1] = i+1
  
print(*ans)

### FIXED CODE ###

n = int(input())
student = list(map(int,input().split()))
a = [0]*n
 
for i in range(n):
  s = student[i] #生徒が出席した番号をメモ
  a[s-1] = i+1
  
print(*a)
S = input()
N = len(S)
ans=[0]*N

def r_search(k):
    count=0
    i=0

    while S[k+i] == "R":
        count += 1
        i+=1

    ans[k+i] += count//2

    if count%2 == 0:
        ans[k+i-1] += count//2
    else:
        ans[k+i-1] += count//2+1
    
    if k+i!=N-1:
        l_search(k+i)
    else:
        ans[N-1]+=1


def l_search(k):
    count=0
    i=0

    while S[k+i] == "L":
        count += 1
        i+=1
        if k+i==N-1:
            count += 1
            break


    ans[k-1] += count//2
    if count%2 == 0:
        ans[k] += count//2
    else:
        ans[k] += count//2+1

    if k+i!=N-1:
        r_search(k+i)

r_search(0)

[print(x) for x in ans]

### FIXED CODE ###

S = input()
N = len(S)
ans=[0]*N


count=0
for i in range(N):
    if S[i]=="R":
        count+=1
    else:
        ans[i-1] += (count+1)//2
        ans[i] += count//2
        count=0

count=0
for i in range(1,N+1):
    if S[N-i]=="L":
        count+=1
    else:
        ans[N-i] += count//2
        ans[N-i+1] += (count+1)//2
        count=0

[print(x) for x in ans]
ans = {}

roop = input()
for k in range(roop):
    str1 = raw_input()
    str2 = raw_input()
    for i in range(len(str1)):
        ans[i, -1] = 0
    for j in range(len(str2)):
        ans[-1, j] = 0
    for i in range (len(str1)):
        for j in range(len(str2)):
            if(str1[i] == str2[j]):
                ans[i, j] = ans[i - 1, j - 1] + 1
            else:
                ans[i, j] = max(ans[i - 1, j], ans[i, j - 1])
    print ans[len(str1) - 1, len(str2) - 1]

### FIXED CODE ###

def LCS():
    str1 = raw_input()
    str2 = raw_input()
    
    after = [0] * (len(str2) + 1)
    
    for i in xrange(1, len(str1) + 1):
        before = after + []
        for j in xrange(1, len(str2) + 1):
             if str1[i - 1] == str2[j - 1]:
                 after[j] = before[j - 1] + 1
             elif after[j - 1] > before[j]: #this is equal to 'max(after[j - 1], before[j])'
                 after[j] = after[j - 1]
    return after[j]

n = input()
for k in xrange(n):
    print LCS()
a = input()
a = a.split()
D = int(a[0])
N = int(a[1])
ans = (100 ** D) * N
if N = 100:
    ans = ans + (100 ** D)
print(ans)


### FIXED CODE ###

a = input()
a = a.split()
D = int(a[0])
N = int(a[1])
ans = (100 ** D) * N
if N == 100:
    ans = ans + (100 ** D)
print(ans)
a,b = map(int,input(),split())
print(a*b)

### FIXED CODE ###

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

result = 0
i = 1
while h > 0:
    h = h // 2
    result = result + i
    i *= 2

print(result)

### FIXED CODE ###

h = int(input())

result = 0
i = 1
while h > 0:
    h = h // 2
    result = result + i
    i *= 2

print(result)
a=[]
while 1:
 n=input()
 if n=='0 0':break
 x,y=map(int,n.split())
 print(y,x) if x>y else:print(n)

### FIXED CODE ###

import sys
for s in sys.stdin:
 if'0 0\n'==s:break
 print(*sorted(map(int,s.split())))
N=int(input())

XY = [list(map(int,input().split())) for _ in range(N)]

x=[]
y=[]

for X,Y in XY:
    x.append(X)
    y.append(Y)
    
l1=[]
c=0
for i in range(N):
    for j in range(N):
        if i==j:
            continue;
        a=x[i]-x[j]
        b=y[i]-y[j]
        """
        if a<=0 and b>=0:
            a=-a
            b=-b
        elif a<=0 and b<=0:
            a=-a
            b=-b
        """
        l1.append(str(a)+"_"+str(b))
        #l1.append([a,b])
v=set(l1)
c=[]
for i in v:
    c.append(l1.count(i))
#c = collections.Counter(l1)      
#values, counts = zip(*c.most_common())    
print(N-max(c))


        


### FIXED CODE ###

N=int(input())

XY = [list(map(int,input().split())) for _ in range(N)]

x=[]
y=[]

for X,Y in XY:
    x.append(X)
    y.append(Y)
    
l1=[]
c=0
for i in range(N):
    for j in range(N):
        if i==j:
            continue;
        a=x[i]-x[j]
        b=y[i]-y[j]
        """
        if a<=0 and b>=0:
            a=-a
            b=-b
        elif a<=0 and b<=0:
            a=-a
            b=-b
        """
        l1.append(str(a)+"_"+str(b))
        #l1.append([a,b])
v=set(l1)
c=[]
for i in v:
    c.append(l1.count(i))
#c = collections.Counter(l1)      
#values, counts = zip(*c.most_common()) 
if c==[]:
    print(1)   
else:
    print(N-max(c))
import numpy as np
from sys import stdin
sys.setrecursionlimit(10**6) 

def main(args):
    a = int(args[0])
    b = int(args[1])
    if 6 <= a and a <= 12:
        v = b//2
    elif a <= 5:
        v = 0
    else:
        v = b
    print(v)

main(stdin.readline().split(" "))

### FIXED CODE ###

import numpy as np
from sys import stdin
#sys.setrecursionlimit(10**6) 

def main():
    a, b = [int(x) for x in stdin.readline().rstrip().split()]
    if 6 <= a and a <= 12:
        v = b//2
    elif a <= 5:
        v = 0
    else:
        v = b
    print(v)

if __name__ == "__main__":
    main()
againstN = [0]*50

for a in range(0,10):
  for b in range(0,10):
    for c in range(0,10):
      for d in range(0,10):
        againstN[a+b+c+d] += 1

inputs=[]
while True:
  try:
    inputs.append(int(input()))
  except EOFError:
    break

for i in inputs:
  print(againstN[i])

### FIXED CODE ###

answermap=[0]*51
answermap[0] = 1
answermap[1] = 4
answermap[2] = 10
answermap[3] = 20
answermap[4] = 35
answermap[5] = 56
answermap[6] = 84
answermap[7] = 120
answermap[8] = 165
answermap[9] = 220
answermap[10] = 282
answermap[11] = 348
answermap[12] = 415
answermap[13] = 480
answermap[14] = 540
answermap[15] = 592
answermap[16] = 633
answermap[17] = 660
answermap[18] = 670
answermap[19] = 660
answermap[20] = 633
answermap[21] = 592
answermap[22] = 540
answermap[23] = 480
answermap[24] = 415
answermap[25] = 348
answermap[26] = 282
answermap[27] = 220
answermap[28] = 165
answermap[29] = 120
answermap[30] = 84
answermap[31] = 56
answermap[32] = 35
answermap[33] = 20
answermap[34] = 10
answermap[35] = 4
answermap[36] = 1
answermap[37] = 0
answermap[38] = 0
answermap[39] = 0
answermap[40] = 0
answermap[41] = 0
answermap[42] = 0
answermap[43] = 0
answermap[44] = 0
answermap[45] = 0
answermap[46] = 0
answermap[47] = 0
answermap[48] = 0
answermap[49] = 0
answermap[50] = 0

inputs = []

while True:
  try:
    inputs.append(int(input()))
  except EOFError:
    break

for i in inputs:
  print(answermap[i])
h,w=map(int,input().split())
data=[[0 for i in range(w+2)] for j in range(h+2)]
for j in range(h):
    s=input()
    for i in range(w):
        if s[i]=="#":
            data[j+1][i+1]=1
flag=True
for i in range(1,h+2):
    for j in range(1,w+2):
        c=0
        for a in range(i-1,i+2):
            for b in range(j-1,j+2):
                c+=data[a][b]
        if c==1:
            flag=False
            break
if flag:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

h,w=map(int,input().split())
data=[[0 for i in range(w+2)] for j in range(h+2)]
for j in range(h):
    s=input()
    for i in range(w):
        if s[i]=="#":
            data[j+1][i+1]=1
flag=True
for i in range(1,h+2):
    for j in range(1,w+2):
        if data[i][j]==1 and data[i-1][j]==data[i+1][j]==data[i][j-1]==data[i][j+1]==0:
            flag=False
            break
if flag:
    print("Yes")
else:
    print("No")
# -*- coding: utf-8 -*-
"""
Created on Sun Jun 17 23:38:43 2018

@author: ashida
"""

N=int(input())

A1 = list( map(int, input().split()))
A2 = list( map(int, input().split()))

SA1 = [0]*N
SA2 = [0]*N

SA1[0] = A1[0]
SA2[N-1] = A2[N-1]

for i in range(N-1):
    SA1[i+1] = SA1[i]+A1[i+1]
    SA2[N-2-i] = SA1[N-1-i]+A1[N-2-i]
    
ans = [0]*N

for i in range(N):
    ans[i] = SA1[i]+SA2[i]

print(max(ans))


### FIXED CODE ###

X = int(input())
A = int(input())
B = int(input())

print((X-A)%B)
import sys
#input = sys.stdin.buffer.readline
input = sys.stdin.readline

# mod=10**9+7
# rstrip().decode('utf-8')
# map(int,input().split())
# import numpy as np


def main():
	n=int(input())
	s=[]
	t=[]
	for i in range(n):
		a,b=input().split()
		s.append(a)
		t.append(int(b))
	x=input()

	for i in range(n):
		if x==s[i]:
			print(sum(t[i+1:]))
            exit(0)













if __name__ == "__main__":
	main()


### FIXED CODE ###

#import sys
#input = sys.stdin.buffer.readline
#input = sys.stdin.readline

# mod=10**9+7
# rstrip().decode('utf-8')
# map(int,input().split())
# import numpy as np


def main():
	n=int(input())
	s=[]
	t=[]
	for i in range(n):
		a,b=input().split()
		s.append(a)
		t.append(int(b))
	x=input()
	for i in range(n):
		if x==s[i]:
			ans=sum(t[i+1:])
			print(ans)
			exit(0)


if __name__ == "__main__":
	main()
import sys

N = int(input())

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

M = N*(N+1)//2

if sum(A) % M != 0:
    print ("NO")
    sys.exit()

able = sum(A) // M

print (M,able)

A.append(A[0])
now = 0

for i in range(N):

    if A[i+1] - A[i] == able:
        continue

    else:
        #print (A[i+1],A[i],able,1-N)
        if ((A[i+1]-A[i])-able) % (1-N) != 0:
            print ("NO")
            sys.exit()

        else:
            now += ((A[i+1]-A[i])-able) // (1-N)


if now <= able:
    print ("YES")
else:
    print ("NO")


### FIXED CODE ###

"""
基本の差はable

 1  2 3  4 5
 4  5 1  2 3
+2  3 4  5 1

 7 10 8 11 9
sa3 -2 3 -2 -2

一度も選ばれてない=3
選ばれてる = -2
一回で -5・・・？
一回選ばれると本来あった +1が消えて -4される →よって-5
"""

import sys

N = int(input())

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

M = N*(N+1)//2

if sum(A) % M != 0:
    print ("NO")
    sys.exit()

able = sum(A) // M

#print (M,able)

A.append(A[0])
now = 0

for i in range(N):

    #print ((A[i+1]-A[i]-able)//N)

    if A[i+1] - A[i] == able:
        continue

    else:
        
        if ((A[i+1]-A[i])-able) % N != 0 or ((A[i+1]-A[i])-able) // N > 0:
            print ("NO")
            sys.exit()

        else:
            now += ((A[i+1]-A[i])-able) // (0-N)


if now == able:
    print ("YES")
else:
    print ("NO")
N = int(input())
A = list(map(int, input().split()))

colors = [0 for _ in range(N + 1)]

for a in A:
    if 1<= a < 400:
        colors[0] = 1
    if 400 <= a < 800:
        colors[1] = 1
    if 800 <= a < 1200:
        colors[2] = 1
    if 1200 <= a < 1600:
        colors[3] = 1
    if 1600 <= a < 2000:
        colors[4] = 1
    if 2000 <= a < 2400:
        colors[5] = 1
    if 2400 <= a < 2800:
        colors[6] = 1
    if 2800 <= a < 3200:
        colors[7] = 1
    if 3200 <= a:
        colors[8] += 1

minimum = sum(colors[:-1])
zero_count = colors.count(0)
over_count = colors[-1]

max = 0
max = min(zero_count, over_count) + minimum

print(minimum, max)


### FIXED CODE ###

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

colors = [0 for _ in range(8)]
over = 0

for a in A:
    if 1 <= a < 400:
        colors[0] = 1
    if 400 <= a < 800:
        colors[1] = 1
    if 800 <= a < 1200:
        colors[2] = 1
    if 1200 <= a < 1600:
        colors[3] = 1
    if 1600 <= a < 2000:
        colors[4] = 1
    if 2000 <= a < 2400:
        colors[5] = 1
    if 2400 <= a < 2800:
        colors[6] = 1
    if 2800 <= a < 3200:
        colors[7] = 1
    if 3200 <= a:
        over += 1

c = colors.count(1)

if over == 0:
    maxi = c
else:
    maxi = c + over

if c == 0:
    mini = 1
else:
    mini = c

print(mini, maxi)
d,t,s=map(int, input().split())
if d/s<=t:
  print("Yes")
elif:
  print("No")

### FIXED CODE ###

d,t,s=map(int, input().split())
if d/s<=t:
  print("Yes")
else:
  print("No")
N,R=map(int,input().split())
print(R if N>=10 else R+(100*(10-K)))

### FIXED CODE ###

N,R=map(int,input().split())
print(R if N>=10 else R+(100*(10-N)))
# C
from math import ceil
#N = int(input())
#T = [[int(i) for i in input().split()] for n in range(N)]
m = T[0]
for n in range(1, N):
    a = ceil(max(m[0]/T[n][0], m[1]/T[n][1]))
    m = [T[n][0] * a, T[n][1] * a]
print(sum(m))

### FIXED CODE ###

# C
from math import ceil
N = int(input())
T = [[int(i) for i in input().split()] for n in range(N)]
m = T[0]

def hoge(a, b):
    if a%b==0:
        return a//b
    else:
        return a//b+1

for n in range(1, N):
    a = max(hoge(m[0],T[n][0]), hoge(m[1],T[n][1]))
    m = [T[n][0] * a, T[n][1] * a]
print(sum(m))
import sys
input = sys.stdin.readline

def F(N,A,B):
    AB = list(zip(A,B))
    AB = [(a,b) for a,b in AB if a < b] # 有用なやつだけ
    AB.sort(key = lambda x: x[1]/x[0], reverse = True)
    if len(AB) == 0:
        return N
    if len(AB) == 1:
        a,b = AB[0]
        x = N//a
        return N + (b-a) * x
    if len(AB) == 2:
        (a,b),(c,d) = AB
        # 2種類目の硬価はa回未満しか使わない：ac個はa優先なので
        return max(N + (N - i * c) // a * (b-a) + i * (d-c) for i in range(M))
    # 効率の良いものから並んでいる
    dp = [0] * (N+1)
    for n in range(N+1):
        x = n
        for a,b in AB:
            if n >= a:
                y = dp[n-a] + b
                if x < y:
                    x = y
        dp[n] = x
    return dp[N]

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

answer = F(F(N,A,B),B,A)
print(answer)

### FIXED CODE ###

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

if K == 1:
  answer = 0
else:
  answer = N-K
print(answer)
import math
from functools import reduce

N = int(input())
input_list = [int(input()) for i in range(N)]

# 最小公倍数を求めるだけ
def lcm_base(x, y):
    return (x * y) // math.gcd(x, y)

def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)

print(lcm(*input_list))

### FIXED CODE ###

from functools import reduce

N = int(input())
input_list = sorted([int(input()) for i in range(N)])

# ユークリッドの互除法
def gcd(x, y):
    if y == 0:
        return x
    else:
        return gcd(y, x % y)

def lcm_base(x, y):
    return (x * y) // gcd(x, y)

def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)

print(lcm(*input_list))
import numpy as np
N = int(input())
L = np.array([int(l) for l in input().split(' ')])
counts =0

for i in range(N):
    for j in range(i+1,N):
        B2  = L[j+1:][(L[j+1:]<L[i]+L[j]) & (L[j+1:]>abs(L[i]-L[j]))]
        counts +=len(B2)
print(counts)
                

### FIXED CODE ###

A,B = map(int, input().split(' '))
print(max(A-2*B,0))
s = list(input())
k = int(input())
count = 0
x = 0
if s[0] != s[-1]:
    for i in range(len(s) - 1):
        if s[i] == s[i + 1]:
            s.pop(i + 1)
            s.insert(i + 1, "")
            count += 1
    count = count * k
else:
    if s[-2] == s[-1]:
        x = 1
    s.append(s[0])
    for i in range(len(s) - 1):
        if s[i] == s[i + 1]:
            s.pop(i + 1)
            s.insert(i + 1, "")
            count += 1
    count = count * k - 1
    if x == 1:
        count += 1
print(int(count))


### FIXED CODE ###

s = list(input())
k = int(input())
count = 0
s1 = list(set(s))
if len(s1) == 1:
    count = int((k * len(s)) / 2)
elif k >= 3:
    t1 = s * 5
    for i in range(len(t1) - 1):
        if t1[i] == t1[i + 1]:
            t1.pop(i + 1)
            t1.insert(i + 1, "")
            count += 1
    if count % 5 == 0:
        count = (count / 5) * k
    elif (count + 1) % 5 == 0:
        count = ((count + 1) / 5) * k - 1
    else:
        count = ((count + 2) / 5) * k - 2
else:
    t1 = s * k
    for i in range(len(t1) - 1):
        if t1[i] == t1[i + 1]:
            t1.pop(i + 1)
            t1.insert(i + 1, "")
            count += 1
print(int(count))
n,t=map(int,input().split())
l=[]
for i in range(n):
    c,time=map(int,input().split())
    if time>=t:
        l.append(c)
print(min(l))

### FIXED CODE ###

n,t=map(int,input().split())
l=[]
for i in range(n):
    c,time=map(int,input().split())
    if time<=t:
        l.append(c)
print(min(l) if l!=[] else "TLE")
n = int(input())
st = input()
r = int(input())

key = st[r-1]

for i in range(n):
  if st[i] == key:
    st[i] = "*"
print("".join(st))

### FIXED CODE ###

n = int(input())
str = input()
str =list(str)
str.append("a")
cs = int(input())

char = str[cs-1]
for i in range(n):
  if str[i] != char:
    str[i:i+1] = "*"
ans = str[0:n]

print(*ans,sep ="")
S = input()
K = int(input())
last = "1"
for i,s in enumerate(S):
    if s != "1":
        last = s
        ind = i
        break
if K-1 < ind:
    print("1")
else:
    print(last)

### FIXED CODE ###

S = input()
K = int(input())
last = "1"
ind = 100
for i,s in enumerate(S):
    if s != "1":
        last = s
        ind = i
        break
if K-1 < ind:
    print("1")
else:
    print(last)
#coding:utf-8
import sys

input_nums = [int(x) for x in split(readline())]

if len(input_num) > 2 :
	sys.exit("illegal input")
    
if (sum(input_nums)) > 16:
  sys.exit("illegal input")
  
if (min(input_nums)) < 1:
  sys.exit("illegal input")
  
if (max_num = max(input_nums)) > 16:
  sys.exit("illegal input")
elif max_num > 8:
  print(":(")
else :
  print('Yay!')

### FIXED CODE ###

#coding:utf-8
import sys

input_nums = [int(x) for x in sys.stdin.readline().split()]

if len(input_nums) > 2 :
	sys.exit("illegal input")
    
if (sum(input_nums)) > 16:
  sys.exit("illegal input")
  
if (min(input_nums)) < 1:
  sys.exit("illegal input")

max_num = max(input_nums)
if max_num > 16:
  sys.exit("illegal input")
elif max_num > 8:
  print(":(")
else :
  print('Yay!')
N, M = (int(i) for i in input().split())
a = []
b = []
for i in range(N):
    data = list(input())
    a.append(data)
for i in range(M):
    data = list(input())
    b.append(data)
    
L = N-M

def check(i,j):
    ans=True
    for line in range(L+1):
        for row in range(L+1):
            if (a[i+line][j+row]!=b[line][row]):
                ans=False
                break
    return ans

ans=False
for i in range(L+1):
    for j in range(L+1):
        ansnow=check(i,j)
#        print(ansnow,i,j)
        if(ansnow==True):
            ans=True
            break
if(ans==True):
    print('Yes')
else:
    print('No')
    

### FIXED CODE ###

a, b = (int(i) for i in input().split())

if a==1:
    a=14
if b==1:
    b=14

if a==b:
    print("Draw")
elif a>b:
    print("Alice")
else:
    print("Bob")
N=int(input())
A==int(input())

N %= 500

if A >= N:
  print('Yes')
else:
  print('No')





### FIXED CODE ###


N = int(input())
A = int(input())

Tmp = N % 500

if A >= Tmp:
    print('Yes')
else:
    print('No')
a={"1":"9","9":"1"}
t=input()
n=""
for i is range(3):
  n+=a[t[i]]
print(n)

### FIXED CODE ###

a = {"1":"9","9":"1"}
z = input()
m = ""
for i in z:
  m += a[i]

print(m)
n=int(input())
lista=list(map(int,input().split()))
listb=list(map(int,input().split()))
listc=list(map(int,input().split()))
list=[]
for i in range(n):
  if lista[i+1]==lista[i]+1:
    list.append(lista[i])
vonus=0
for x in list:
  vonus+=listc[x-1]
print(sum(listb)+vonus)

### FIXED CODE ###

n=int(input())
lista=list(map(int,input().split()))
listb=list(map(int,input().split()))
listc=list(map(int,input().split()))
list=[]
for i in range(2,n+1):
  if lista[i-1]==lista[i-2]+1:
    list.append(lista[i-2])
vonus=0
for x in list:
  vonus+=listc[x-1]
print(sum(listb)+vonus)
H,W=map(int,input().split())
h,w=map(int,input().split())
ptint((H-h)*(W-w))

### FIXED CODE ###

H,W=map(int,input().split())
h,w=map(int,input().split())
print((H-h)*(W-w))
n,d = map(int, input().split())
ans = 0
if n % (2d+1) == 0:
  ans = n//(2d+1)
else:
  ans = n//(2d+1) + 1

### FIXED CODE ###

n,d = map(int, input().split())
ans = 0
if n % (2 * d + 1) == 0:
  ans = n // (2 * d + 1)
else:
  ans = n // (2 * d + 1) + 1
print(ans)
S = input()
N = len(S)
l = []
for i in range(N):
  for j in range(i,N):
    s = S[i:j+1]
    if s.strip("A C G T") == "":
      l.append(s)

m = sorted(l, key=len)
print(len(m[-1]))


### FIXED CODE ###

S = input()
N = len(S)
l = []
for i in range(N):
  for j in range(i,N):
    s = S[i:j+1]
    if s.strip("A C G T") == "":
      l.append(s)
if len(l) == 0:
  print(0)
  exit()
      
m = sorted(l, reverse=True, key=len)
print(len(m[0]))
def run():
  H, N = map(int, input().split())
  ab_li = [tuple(map(int, input().split())) for n in range(N)]
  dp = [float('inf')]*(H+1)
  for i in range(1, H+1):
    for n in range(N):
      a, b = ab_li[n]
      if i == a:
        dp[i] = min(dp[i], b)
      if (i < a) or (dp[i-a] == float('inf')):
        continue
      dp[i] = min(dp[i], dp[i-a]+b)
  if dp[-1] == float('inf'):
    for h in range(H, 0, -1):
      if dp[h] != float('inf'):
        ans = dp[h]+min(ab_li, key=lambda x:x[1])[1]
        break
  else:
    ans = dp[-1]
  for n in range(N):
    a, b = ab_li[n]
    if a > H:
      ans = min(ans, b)
  print(ans)
  
if __name__ == '__main__':
  run()

### FIXED CODE ###

def run():
  H, N = map(int, input().split())
  ab_li = [tuple(map(int, input().split())) for n in range(N)]
  dp = [0]*(H+1)
  for i in range(1, H+1):
    new_li = []
    for n in range(N):
      a, b = ab_li[n]
      if a <= i:
        new_li.append(dp[i-a]+b)
      else:
        new_li.append(b)
    dp[i] = min(new_li)
  print(dp[-1])
  
if __name__ == '__main__':
  run()
n = int(raw_input())
s = ''
for i in range(n):
    s += raw_input()
s = sorted(s)
ans = ''
for i in s:
    ans += i
print ans


### FIXED CODE ###

n = int(raw_input().split()[0])
a = []
for i in range(n):
    a.append(raw_input())
a.sort()
ans = ''
for i in a:
    ans += i;
print ans
_,A = input(),list(map(int,input().split()))
for i in A:
  if i%2 == 1:
    print(2/0)
print("unrated")

### FIXED CODE ###

def GCD(x,y):
    if y==0:
        return x
    return GCD(y,x%y)
def LCM(x,y):
    return x*y // GCD(x,y)
N, M = map(int,input().split())
A = list(map(int,input().split()))
ans = 1
for i in A:
    i //= 2
    ans = LCM(ans,i)
    if (ans//i)%2 == 0:
        print(0)
        exit()
    if ans > M:
        print(0)
        exit()
print(M//ans-M//(ans*2))