Harryxun/stf_run huggingface dataset:
def edit_distance(d):
 n =len(d)
 A=[[0 for i in range(n)] for j in range(n)]
 for long in range(2, n+1):
  for i in range(0,n+1-long):
   k=i-1+long
   def f(i,j,k):
    return A[i][j-1]+A[j][k]+]+M[i][0]*M[j-1][1]*M[k][1]
   A[i][k] = min([f(i,j,k) for j in range(i+1,k+1)])
  return A[0][n-1]
n = input()
M = []
for i in range(n):
 M.append(map(int, raw_input().split()))
print edit_distance(M)

### FIXED CODE ###

def edit_distance(M):
  n = len(M)



  m = [[0 for i in range(n)] for j in range(n)]
   
  for long in range(2, n+1):

    for i in range(0, n-long+1):

      j = i + long - 1

      def a(i, k ,j):
        return m[i][k] + m[k+1][j] + M[i][0]*M[k][1]*M[j][1]
      m[i][j] = min(a(i, k, j) for k in range(i, j))
   
  return m[0][n-1]
 
n = input()
M = []
 
for i in range(n):
  M.append(map(int, raw_input().split()))
print edit_distance(M)
N = int(input())
ans = False
for i in range(N):
    s = input()
    if(s == "Y"):
        ans = True
if(ans):
    print("Four")
else:
    print("Three")

### FIXED CODE ###

N = int(input())
ans = False
s = list(input().split())
for i in s:
    if(i == "Y"):
        ans = True
if(ans):
    print("Four")
else:
    print("Three")
def inv(a,p):
    if a==1:
        return 1
    elif a==0:
        return 0
    return p-(inv(p%a,p)*(p//a))%p
x,y=map(int,input().split())
if (x+y)%3!=0:
    print("0")
    exit()
n=(x+y)//3
r=(2*x-y)//3
p=10**9+7
def fact(n,p):
    a=[[] for _ in range(n+1)]
    a[0]=1
    for i in range(n):
        a[i+1]=(a[i]*(i+1))%p
    return a
f=fact(n,p)
if len(f)<=r:
    print("0")
    exit()
c=f[-1]
d=f[r]
e=f[n-r]
dd=inv(d,p)
ee=inv(e,p)
ans=(c*dd*ee)%p
print(ans)

### FIXED CODE ###

def inv(a,p):
    if a==1:
        return 1
    elif a==0:
        return 0
    return p-(inv(p%a,p)*(p//a))%p
x,y=map(int,input().split())
if (x+y)%3!=0:
    print("0")
    exit()
if x==0 and y>0:
    print("0")
    exit()
if y/x>2 or y/x<0.5:
    print("0")
    exit()
n=(x+y)//3
r=(2*x-y)//3
p=10**9+7
def fact(n,p):
    a=[[] for _ in range(n+1)]
    a[0]=1
    for i in range(n):
        a[i+1]=(a[i]*(i+1))%p
    return a
f=fact(n,p)
c=f[-1]
d=f[r]
e=f[n-r]
dd=inv(d,p)
ee=inv(e,p)
ans=(c*dd*ee)%p
print(ans)
K = int(input())

import math

ans = 0
for i in range(1, K+1):
    for j in range(1, K+1):
        a = gcd(i, j)
        for k in range(1, K+1):
            ans += gcd(a,k)

print(ans)



### FIXED CODE ###

K = int(input())

import math

ans = 0
for i in range(1, K+1):
    for j in range(1, K+1):
        a = math.gcd(i, j)
        for k in range(1, K+1):
            ans += math.gcd(a,k)

print(ans)
N,A,B = map(int,input().split())
C = B - A

if C == 1:
    kabe = int(min(N-B,A-1))
    print(kabe + 1)
elif C % 2 == 0:
    print(int(C / 2))
else:
    NB = N-B
    A1 = A-1
    if NB < A1:
        NA = N-A
        zan = int((NA-NB-1)/2)
        print(int(NB+1+zan))
    else:
        zan = int(((B-1)-A1-1)/2)
        print(int(A1+1+zan)
    

### FIXED CODE ###

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

C = B-A

if C % 2 == 0:
    print(C//2)
else:
    a = min(A-1, N-B) + 1 + (B-A-1)//2
    print(a)
from heapq import*
N,M,*t=map(int,open(0).read().split())
v=[[]for _ in'_'*M]
for i in range(N):
	if M<t[2*i]:v[t[2*i]-1]+=[t[2*i+1]]
z=0
q=[]
for i in v:
	for j in i:heappush(q,-j)
	z-=len(q)and heappop(q)
print(z)

### FIXED CODE ###

from heapq import*
(N,M),*t=[map(int,s.split())for s in open(0)]
v=[[]for _ in'_'*M]
z=0
for a,b in t:
	if a<=M:v[a-1]+=[b]
q=[0]*M
for i in v:
	for j in i:heappush(q,-j)
	z-=heappop(q)
print(z)
the_string = raw_input()
COLS, ROWS = the_string.split()
two_string = raw_input()
co, ro = two_string.split()


Mylist= [[0 for cols in range(int(COLS))] for rows in range(int(ROWS))]

for cols in range(int(co)):
        for rows in range(int(ROWS)):
                Mylist[rows][cols]=1

for rows in range(int(ro)):
        for cols in range(int(COLS)):
                Mylist[rows][cols]=1

d = sum(row.count(0) for row in Mylist)

print(d)

### FIXED CODE ###

the_string = raw_input()
COLS, ROWS = the_string.split()
two_string = raw_input()
co, ro = two_string.split()


Mylist= [[0 for cols in range(int(COLS))] for rows in range(int(ROWS))]

for cols in range(int(co)):
        for rows in range(int(ROWS)):
                Mylist[rows][cols]=1

for rows in range(int(ro)):
        for cols in range(int(COLS)):
                Mylist[rows][cols]=1

d = sum(row.count(0) for row in Mylist)

print(d)
import sys
input = sys.stdin.readline
S = input()
T = input()
score_list = []
for i in range(len(S) - len(T)):
  s = S[i:i+len(T)]
  score = 0
  for i in range(len(s)):
    if s[i] != T[i]:
      score += 1
  score_list.append(score)
print(min(score_list))


### FIXED CODE ###

import sys
input = sys.stdin.readline
S = input().strip()
T = input().strip()
score_list = []
for i in range(len(S) - len(T) + 1):
  s = S[i:i+len(T)]
  score = 0
  for i in range(len(s)):
    if s[i] != T[i]:
      score += 1
  score_list.append(score)
print(min(score_list))
import itertools
N,M,K = map(int,input().split())
A = [0]+list(map(int,input().split()))
B = [0]+list(map(int,input().split()))
SA = list(itertools.accumulate(A))
SB = list(itertools.accumulate(B))
ans = 0
j = len(B)-1
for i in range(len(SA)):
    while(pt>=0):
        if SA[i] + SB[j] <= K:
            ans = max(ans,i+j)
            break
        j-=1
print (ans)





### FIXED CODE ###

import itertools
N,M,K = map(int,input().split())
A = [0]+list(map(int,input().split()))
B = [0]+list(map(int,input().split()))
SA = list(itertools.accumulate(A))
SB = list(itertools.accumulate(B))

ans = 0
pt = len(B)-1
for i,sa in enumerate(SA):
    while(pt>=0):
        if sa + SB[pt] <= K:
            ans = max(ans,i+pt)
            break
        pt-=1
print (ans)
n = int(input())
x = []
u = []

total = 0
for i in range(n):
    x_tmp, u_tmp = map(int(input))
    if u_tmp == 'JPY':
        total += x_tmp
    elif u_tmp == 'BTC':
        total += x_tmp * 380000

print(total)


### FIXED CODE ###

n = int(input())
x = []
u = []

total = 0
for i in range(n):
    x_tmp, u_tmp = input().split()
    if u_tmp == 'JPY':
        total += int(x_tmp)
    elif u_tmp == 'BTC':
        total += float(x_tmp) * 380000

print(total)
import math
import sys
sys.setrecursionlimit(10000000)

n = int(input())
s = int(input())

up = math.sqrt(n)

def colsum(num, base):
    if num < base:
        return num
    else:
        return num%base + colsum(num//base,base)

#s = n(n<b)
if s == n:
    print(n+1)
    exit()


#sqrt(n)まで探索
for i in range(2,int(up)+1):
    if s == colsum(n,i):
        print(i)
        exit()

#2桁しかあり得ない場合(sqrt(n)<b<n)
for j in range(1,int(up)+1):
    if (n-s)%j == 0:
        b = (n-s)/j + 1
        if s == colsum(n,b) and b > 1:
            print(i)
            exit()

print(-1)

### FIXED CODE ###

n = int(input())
k = int(input())
x = int(input())
y = int(input())
if n > k:
    print(k*x+(n-k)*y)
else:
    print(n*x)
s = input()
 
for i in range(int(input())):
    cmd = input().split()
          s = s[:a] + cmd[3] + s[b+1:]

### FIXED CODE ###

s = input()
 
for i in range(int(input())):
    cmd = input().split()
    a, b = int(cmd[1]), int(cmd[2])
 
    if cmd[0] == 'print':
        print(s[a:b+1])
    elif cmd[0] == 'reverse':
        s = s[:a] + s[a:b+1][::-1] + s[b+1:]
    elif cmd[0] == 'replace':
        s = s[:a] + cmd[3] + s[b+1:]
N = int(input())

nodes = []
edge = []
for i in range(N):
    nodes.append([])

for i in range(N-1):
    a, b = [int(v) - 1 for v in input().split(' ')]
    nodes[a].append((b, i))
    nodes[b].append((a, i))
    edge.append(0)

max_l = 0
max_i = 0
for i, links in enumerate(nodes):
    l = len(links)
    if max_l < l:
        max_l = l
        max_i = i

def fill(nodes, links, edge, pc):
    c = 1
    if pc == c:
        c += 1

    next_fills = []
    for n, i in links:
        if edge[i] != 0:
            continue
        edge[i] = c
        fill(nodes, nodes[n], edge, c)

        c += 1
        if pc == c:
            c += 1

    
fill(nodes, nodes[max_i], edge, 0)

print(max_l)
for e in edge:
    print(e)

### FIXED CODE ###

N = int(input())

nodes = []
edge = []
for i in range(N):
    nodes.append([])

for i in range(N-1):
    a, b = [int(v) - 1 for v in input().split(' ')]
    if a >= len(nodes):
        exit()
    if b >= len(nodes):
        exit()
    nodes[a].append((b, i))
    nodes[b].append((a, i))
    edge.append(0)

max_l = 0
max_i = 0
if nodes is None:
    exit()

for i, links in enumerate(nodes):
    if links is None:
        exit()
    l = len(links)
    if max_l < l:
        max_l = l
        max_i = i

def fill(nodes, edge, queue):
    while len(queue) > 0:
        ni, pc = queue.pop(0)
        links = nodes[ni]

        c = 1
        if pc == c:
            c += 1

        if links is None:
            exit()

        next_links = []
        for n, i in links:
            if n < 0 or i < 0:
                exit()
            if n >= len(nodes) or i >= len(edge):
                exit()

            if edge[i] != 0:
                continue
            edge[i] = c
            queue.append((n, c))

            c += 1
            if pc == c:
                c += 1

queue = [(max_i, 0)]    
fill(nodes, edge, queue)

print(max_l)
for e in edge:
    print(e)
n,m = map(int,input().split())
a_n = list(map(int,input(.split())))
b_and_c = []
for i in range(m):
    b_and_c.append(list(map(int,input().split())))

for i in range(b_and_c):
    sort(a_n)
    for j in range(b_and_c[i][0]):
        if a_n[j] < b_and_c[i][1]:
            a_n[j] = b_and_c[i][1]
        else:
            break

print(sum(a_n)

### FIXED CODE ###

n,m = map(int,input().split())
a_n = list(map(int,input().split()))
b_and_c = []
for i in range(m):
    b_and_c.append(list(map(int,input().split())))

a_n.sort()

b_and_c.sort(key = lambda x : x[1], reverse = True)
index = 0
for i in range(m):
    if index >= n:
        break
    elif a_n[index] >= b_and_c[i][1]:
        break
    for j in range(index, n):
        if a_n[j] < b_and_c[i][1]:
            for k in range(j, min(j + b_and_c[i][0], n)):
                if a_n[k] < b_and_c[i][1]:
                    a_n[k] = b_and_c[i][1]
                else:
                    break
            index = k + 1
            break

print(sum(a_n))
def mina(t, i, L):
  t -= i
  if t == 0:
    return True
  elif t < 0:
    return False
  else:
    for i in L:
      if mina(t, i, L) == True:
        return True
    return False

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

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

t = [2, 5, 5, 4, 5, 6, 3, 7, 6]

A.sort(reverse = True)
D = {}
L = []
X = []
for i in A:
  if t[i - 1] not in D:
    D[t[i - 1]] = i
    L.append(t[i - 1])
    X.append([i, t[i - 1]])

L.sort()

Lmin = N // L[0]
Lmod = N % L[0]

F = True
if Lmod != 0:
  while F:
    Lmin -= 1
    Lmod += L[0]
    t = Lmod
    for i in L[1:]:
      if mina(t, i, L[1:]) == True:
        F = False
        break
  
  X.sort(reverse = True)
  for i in X:
    k = t - i[1]
    if k == 0:
      List = [i[0]]
      break
    elif k > 0:
      for j in X:
        if k - j[1] == 0:
          List = [i[0], j[0]]

Ans = [str(D[L[0]]) for i in range(Lmin)]
if Lmod != 0:
  if len(List) == 1:
    if L[0] < List[0]:
      Ans = [str(List[0])] + Ans
    else:
      Ans = Ans + [str(List[0])]
  else:
    List.sort(reverse = True)
    if L[0] > List[0]:
      Ans += [str(List[0]), str(List[1])]
    elif L[0] < List[1]:
      Ans = [str(List[0]), str(List[1])] + Ans
    else:
      Ans = [str(List[0])] + Ans + [str(List[1])]

print("".join(Ans))

### FIXED CODE ###

import copy

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

t = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
L = {}
for i in A:
  if t[i] in L:
    if L[t[i]] < i:
      L[t[i]] = i
  else:
    L[t[i]] = i

dp = [[0 for j in range(10)] for i in range(N)]
for i in L.items():
  if i[0] - 1 < N:
    dp[i[0] - 1][i[1]] = 1
for i in range(N):
  if max(dp[i]) == 0:
    continue
  for j in L.items():
    k = i + j[0]
    if k < N:
      t = copy.deepcopy(dp[i])
      t[j[1]] += 1
      if sum(t) > sum(dp[k]):
        dp[k] = t
      else:
        for ii in range(9, 0, -1):
          if t[ii] > dp[k][ii]:
            dp[k] = t
            break
          elif t[ii] < dp[k][ii]:
            break
          
t = dp[-1]
Ans = ""
for i in range(9, 0, -1):
  for j in range(t[i]):
    Ans += str(i)
    
print(Ans)
#!/usr/bin/env python3

import math
import sys


def dist():
    coordinates = [int(num) for num in sys.stdin.readline().split()]
    return math.hypot(coordinates[2]-coordinates[0],
                      coordinates[3]-coordinates[1])


def main():
    print(dist())


if __name__ == '__main__':
    main()

### FIXED CODE ###

#!/usr/bin/env python3

import math
import sys


def dist():
    coordinates = [float(num) for num in sys.stdin.readline().split()]
    return math.hypot(coordinates[2]-coordinates[0],
                      coordinates[3]-coordinates[1])


def main():
    print(dist())


if __name__ == '__main__':
    main()
n,k = [int(x) for x in input().split()]
p = [int(x) for x in input().split()]
max_t = 0
ans = 0
for i in range(n - k +1):
  buf = sum(p(i:i+k))
  if max_t < buf:
  	max_t = buf
    ans = 0
    for j in range(k):
      ans += (1+p[i+j]) * p[i+j] / 2
print(ans)

### FIXED CODE ###

n, k = [int(x) for x in input().split()]
p = [1/2 + int(x)/2 for x in input().split()]
sum_p =[]
buf = 0
for i in p:
    buf += i
    sum_p.append(buf)
max_t = 0
for i in range(n - k + 1):
    buf = sum_p[i+k-1]
    if i > 0:
        buf -= sum_p[i-1]
    if max_t < buf:
        max_t = buf
print(max_t)
import cython
import bisect
n=int(input())
lists=list(map(int,input().split()))
listss=sorted(lists)
count=0
for i in range(n):
    for j in range(n):
        if i!=j:
            index1=bisect.bisect_left(listss, abs(listss[j]-listss[i])+1)
            index2=bisect.bisect_right(listss,listss[i]+listss[j]-1)
            count+=(index2-index1)
            x=abs(listss[j]-listss[i])
            if  x+1<=listss[i]:
                count-=1
            if x+1<=listss[j]:
                count-=1
print(count//6)

### FIXED CODE ###

import bisect
n=int(input())
lists=list(map(int,input().split()))
lists=sorted(lists)

cnt=0
import math
for i in range(n):
    for j in range(i+1,n):
        #i<j 
        x=lists[i]
        y=lists[j]
        left=i 
        right=j 
        index=bisect.bisect_right(lists,y-x)
        cnt+=min(j-i-1,j-index)

print(cnt)
# m-solutions2019C - Best-of-(2n-1) (292 ms)
def get_inv(lim: int) -> list:
    # compute a table of inverse factorials (1-idx)
    inv = [0] * (lim + 1)
    inv[:2] = 1, 1
    for i in range(2, lim + 1):
        inv[i] = (-(MOD // i) * inv[MOD % i]) % MOD
    return inv


def main():
    global MOD
    N, A, B, C = tuple(map(int, input().split()))
    MOD = 10 ** 9 + 7
    inv = get_inv(100)
    pa, pb = [1] * (N + 1), [1] * (N + 1)  # power of a, b
    a, b = A * inv[A + B], B * inv[A + B]
    for i in range(1, N + 1):
        pa[i] = pa[i - 1] * a % MOD
        pb[i] = pb[i - 1] * b % MOD
    ans, comb = (pa[N] + pb[N]) * N, 1
    for m in range(N + 1, 2 * N):
        comb = (comb * (m - 1) * inv[m - N]) % MOD
        x = comb * (pa[N] * pb[m - N] + pa[m - N] * pb[N]) * m
        ans = (ans + x) % MOD
    ans = ans * 100 * inv[100 - C] % MOD
    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

# m-solutions2019C - Best-of-(2n-1) (292 ms)
def get_inv(lim: int) -> list:
    # compute a table of inverse factorials (1-idx)
    inv = [0] * (lim + 1)
    inv[:2] = 1, 1
    for i in range(2, lim + 1):
        inv[i] = (-(MOD // i) * inv[MOD % i]) % MOD
    return inv


def main():
    global MOD
    N, A, B, C = tuple(map(int, input().split()))
    MOD = 10 ** 9 + 7
    inv = get_inv(max(100, 2 * N))
    pa, pb = [1] * (N + 1), [1] * (N + 1)  # power of a, b
    a, b = A * inv[A + B], B * inv[A + B]
    for i in range(1, N + 1):
        pa[i] = pa[i - 1] * a % MOD
        pb[i] = pb[i - 1] * b % MOD
    ans, comb = (pa[N] + pb[N]) * N, 1
    for m in range(N + 1, 2 * N):
        comb = (comb * (m - 1) * inv[m - N]) % MOD
        x = comb * (pa[N] * pb[m - N] + pa[m - N] * pb[N]) * m
        ans = (ans + x) % MOD
    ans = ans * 100 * inv[100 - C] % MOD
    print(ans)


if __name__ == "__main__":
    main()
def judge(z):
    if z >= 0:
        remain = n - z
        pay = [[i, remain - i] for i in range(remain + 1)]

        for i in range(remain + 1):
            if 10 * pay[i][0] + 5 * pay[i][1] + z == m:
                print(pay[i][0], pay[i][1], z)
                exit()

        judge(z - 1)

    else:
        print(-1, -1, -1)


n, M = list(map(int, input().split(" ")))
m = int(M / 1000)

judge(n)


### FIXED CODE ###

def pay(i: int, remain: int, z: int):
    for i in range(0, (n - z) + 1):
        if 10 * i + 5 * (remain - i) + z == m:
            print(i, remain - i, z)
            exit()

    return


n, M = list(map(int, input().split(" ")))
m = int(M / 1000)

for z in range(n, -1, -1):
    pay(0, n - z, z)

print(-1, -1, -1)
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, gcd
from itertools import accumulate, permutations, combinations, product, groupby, combinations_with_replacement
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()
A, B = ZIP(N)
A.sort()
B.sort()
if N%2 == 0:
	l = (A[N//2]+A[N//2-1])
	r = (B[N//2]+B[N//2-1])
	print(r-l+1)
else:
	print(B[N//2]-A[N//2]+1)


### FIXED CODE ###

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, gcd
from itertools import accumulate, permutations, combinations, product, groupby, combinations_with_replacement
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()
A, B = ZIP(N)
A = sorted(A)
B = sorted(B)
if N%2 == 0:
	l = (A[N//2]+A[N//2-1])
	r = (B[N//2]+B[N//2-1])
	print(r-l+1)
else:
	print(B[N//2]-A[N//2]+1)
n,m,k=map(int,input().split())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
a.insert(0,0)
b.insert(0,0)
j=1
while j<=m and b[j]+b[j-1]<=k:
  b[j]+=b[j-1]
  j+=1
  

j-=1
books=j
i=1
while i<n+1:
  while j>0 and a[i]+b[j]>k:
    j-=1
  if(j>=0) and a[i]+b[j]<=k:
    books=max(books,j+i)
    a[i]+=a[i-1]
    i+=1
  else:
    break
print(books)
  


### FIXED CODE ###

a=int(input())
print(a+(a**2)+(a**3))
def memolize(f):
    cache = {}

    def helper(x):
        if x not in cache:
            cache[x] = f(x)
         return cache[x]
    return helper

@memolize
def fib(n):
    if n == 0:
        return 1
    elif n == 1:
        return 1

    return fib(n - 1) + fib(n - 2)

n = int(input())
print(fib(n))



### FIXED CODE ###

def memolize(f):
    cache = {}

    def helper(x):
        if x not in cache:
            cache[x] = f(x)
        return cache[x]
    return helper

@memolize
def fib(n):
    if n == 0:
        return 1
    elif n == 1:
        return 1

    return fib(n - 1) + fib(n - 2)

n = int(input())
print(fib(n))
def mySort(arg1):
    if 'a' not in S:
        return 'No'
    elif 'b' not in S:
        return 'No'
    elif 'c' not in S:
        return 'No'
    else:
        return 'Yes'
    
mySort(S)

### FIXED CODE ###

S = input()

def mySort(S):
    if 'a' not in S:
        return 'No'
    elif 'b' not in S:
        return 'No'
    elif 'c' not in S:
        return 'No'
    else:
        return 'Yes'
    
print(mySort(S))
N, M = map( int, input().split() )
A = list( map( int, input().split() ) )


# 桁数の一番大きいものが最大。そのあと数を大きい順に並べればいい
dp = [0]*(N+1)       # dp[i]: i 本のマッチで条件を満たす整数の最大桁数
cost = [ 0, 2, 5, 5, 4, 5, 6, 3, 7, 6 ]  # 各数字に必要なマッチ棒の数(逆順)

for num_match in range( 2, N+1 ):
    for Aj in A:
        if num_match >= cost[Aj]:
            dp[num_match] = max( dp[num_match], dp[num_match-cost[Aj]]+1 )


# 求めた桁数 dp[N] を用いて順序を求める
ans = ""
digit = dp[N]

A.sort( reverse=True )
while N > 0:
    for Ai in A:
        if N-cost[Ai] >=0 and dp[N-cost[Ai]] == digit-1:
            ans += str(Ai)
            N -= cost[Ai]
            digit -= 1
            break

print( ans )

### FIXED CODE ###

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

if B % A == 0: print( A+B )
else: print( B-A )
import bisect

n, d, a = map(int, input().split())
xh = []
x_list = []
for i in range(n):
    x, h = map(int, input().split())
    xh.append([x, h])
    x_list.append(x)
xh.sort()
x.sort()
count = 0
min_x = 0
sum_h = sum([xh[i][1] for i in range(n)])
while sum_h > 0:
    flag = True
    place = xh[min_x][0] + d
    num = (xh[min_x][1] - 1) // a + 1
    count += num
    for i in range(min_x, bisect.bisect(x_list, place + d)):
        new_h = max(0, xh[i][1] - a * num)
        sum_h -= (xh[i][1] - new_h)
        if new_h == 0:
            if flag == True:
                min_x += 1
        else:
            flag = False
        xh[i][1] = new_h
print(count)

### FIXED CODE ###

import bisect

n, d, a = map(int, input().split())
xh = []
for i in range(n):
    xh.append(list(map(int, input().split())))
xh.sort()
x = [xh[i][0] for i in range(n)]
h = [xh[i][1] for i in range(n)]
count = 0
min_x = 0
acm = [0] * (n + 1)
dif = [0] * (n + 1)
while min_x < n:
    place = x[min_x] + d
    num = (h[min_x] - acm[min_x + 1] - 1) // a + 1
    count += num
    dif[min_x] += num
    dif[bisect.bisect(x, place + d)] -= num
    for i in range(min_x, bisect.bisect(x, place + d)):
        acm[i + 1] = acm[i] + dif[i] * a
        if acm[i + 1] >= h[i]:
            min_x += 1
            continue
        else:
            break
print(count)
import math
from fractions import Fraction
a,b,x=map(int,input().split())
if b*(a**2)<=x*2:
    print(90-math.degrees(math.atan(Fraction(a**3,2*(a*a*b-x)))))
else:
    print(math.degrees(math.atan(Fraction(a*b*b,2*x))))

### FIXED CODE ###

import math
from fractions import Fraction
a,b,x=map(int,input().split())
if b*(a**2)<=x*2:
    print(math.degrees(math.atan(Fraction(2*(a*a*b-x),a**3))))
else:
    print(math.degrees(math.atan(Fraction(a*b*b,2*x))))
n,m = map(int, input().split())
s_and_c = []
for i in range(m):
    s_and_c.append(list(map(int, input().split())))

ans = ["-1" for i in range(n)]
s_and_c.sort()


if m == 0:
    if n == 1:
        ans = ["0"ß]
    else:
        ans[0] = "1"

elif n != 1 and s_and_c[0][0] == 1 and s_and_c[0][1] == 0:
    ans = -1
else:
    for i in range(m):
        if ans[s_and_c[i][0] - 1] == "-1":
            ans[s_and_c[i][0] - 1] = str(s_and_c[i][1])
        elif ans[s_and_c[i][0] - 1] == str(s_and_c[i][1]):
            continue
        else:
            ans = -1


if ans != -1:
    for i in range(n):
        if ans[i] == "-1":
            ans[i] = "0"
    ans = "".join(ans)

print(ans)


### FIXED CODE ###

n,m = map(int, input().split())
s_and_c = []
for i in range(m):
    s_and_c.append(list(map(int, input().split())))

ans = ["-1" for i in range(n)]
s_and_c.sort()


if m == 0:
    if n == 1:
        ans = ["0"]
    else:
        ans[0] = "1"

elif n != 1 and s_and_c[0][0] == 1 and s_and_c[0][1] == 0:
    ans = -1
else:
    for i in range(m):
        if ans[s_and_c[i][0] - 1] == "-1":
            ans[s_and_c[i][0] - 1] = str(s_and_c[i][1])
        elif ans[s_and_c[i][0] - 1] == str(s_and_c[i][1]):
            continue
        else:
            ans = -1


if ans != -1:
    for i in range(n):
        if ans[i] == "-1":
            if i == 0:
                ans[i] = "1"
            else:
                ans[i] = "0"
    ans = "".join(ans)

print(ans)