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

import heapq
import os
from collections import defaultdict

import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353


N, M, S = list(map(int, sys.stdin.buffer.readline().split()))
UVAB = [list(map(int, sys.stdin.buffer.readline().split())) for _ in range(M)]
CD = [list(map(int, sys.stdin.buffer.readline().split())) for _ in range(N)]
CD = [(0, 0)] + CD

graph = [[] for _ in range(N + 1)]
for u, v, a, b in UVAB:
    graph[u].append((a, b, v))
    graph[v].append((a, b, u))
for vs in graph:
    vs.sort()

mada = set(list(range(2, N + 1)))
heap = [(0, 1, S)]
# dp[v, s]: v にお金を s 持ってる状態で来たときの最小値
dp = defaultdict(lambda: INF)
dp[1, S] = 0
while heap and mada:
    d, v, s = heapq.heappop(heap)
    if d > dp[v, s]:
        continue
    if v in mada:
        mada.remove(v)
    for a, b, u in graph[v]:
        if s - a < 0:
            break
        if d + b < dp[u, s - a]:
            dp[u, s - a] = d + b
            heapq.heappush(heap, (d + b, u, s - a))
    c, dd = CD[v]
    if d + dd < dp[v, s + c]:
        dp[v, s + c] = d + dd
        heapq.heappush(heap, (d + dd, v, s + c))

ans = [INF] * (N + 1)
ans[1] = 0
for (v, s), d in dp.items():
    ans[v] = min(ans[v], d)
print(*ans[2:], sep='\n')


### FIXED CODE ###

import heapq
import os
from collections import defaultdict

import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353


N, M, S = list(map(int, sys.stdin.buffer.readline().split()))
UVAB = [list(map(int, sys.stdin.buffer.readline().split())) for _ in range(M)]
CD = [list(map(int, sys.stdin.buffer.readline().split())) for _ in range(N)]
CD = [(0, 0)] + CD

graph = [[] for _ in range(N + 1)]
for u, v, a, b in UVAB:
    graph[u].append((a, b, v))
    graph[v].append((a, b, u))
for vs in graph:
    vs.sort()

mada = set(list(range(2, N + 1)))
heap = [(0, 1, S)]
ans = [INF] * (N + 1)
ans[1] = 0
# dp[v, s]: v にお金を s 持ってる状態で来たときの最小値
dp = defaultdict(lambda: INF)
dp[1, S] = 0
while heap and mada:
    d, v, s = heapq.heappop(heap)
    if d > dp[v, s]:
        continue
    if v in mada:
        mada.remove(v)

    ans[v] = min(ans[v], d)
    for a, b, u in graph[v]:
        if s - a < 0:
            break
        if d + b < dp[u, s - a]:
            dp[u, s - a] = d + b
            heapq.heappush(heap, (d + b, u, s - a))
    c, dd = CD[v]
    sc = min(s + c, 50 * N + 10)
    if d + dd < dp[v, sc]:
        dp[v, sc] = d + dd
        heapq.heappush(heap, (d + dd, v, sc))

print(*ans[2:], sep='\n')
### BUGGY CODE ###

N, S = map(int, input().split())
A = list(map(int, input().split()))
mod = 998244353
dp = [[0 for _ in range(S+1)] for _ in range(N)]

for i in range(0, S+1):
    if i == A[0]:
        dp[0][i] = 1

for i in range(1, N):
    for j in range(0, S+1):
        if j > A[i]:
            dp[i][j] = (dp[i-1][j]+dp[i-1][j-A[i]])%mod
        elif j == A[i]:
            dp[i][j] = (dp[i-1][j]+(i+1))%mod
        else:
            dp[i][j] = dp[i-1][j]
            
ans = 0
for i in range(0, N):
    ans = (ans+dp[i][S])%mod

print (ans)

### FIXED CODE ###

N, S = map(int, input().split())
A = list(map(int, input().split()))
mod = 998244353
dp = [[0 for _ in range(S+1)] for _ in range(N)]

for j in range(0, S+1):
    if j == A[0]:
        dp[0][j] = 1
        break

for i in range(1, N):
    for j in range(0, S+1):
        if j > A[i]:
            dp[i][j] = (dp[i-1][j]+dp[i-1][j-A[i]])%mod
        elif j == A[i]:
            dp[i][j] = (dp[i-1][j]+(i+1))%mod
        else:
            dp[i][j] = dp[i-1][j]
            
ans = 0
for i in range(0, N):
    ans = (ans+dp[i][S])%mod
    
print (ans)
### BUGGY CODE ###

class Combination:
    def __init__(self, N, MOD=10 ** 9 + 7):
        self.MOD = MOD
        self.fact, self.inv = self._make_factorial_list(N)

    def __call__(self, n, k):
        if k < 0 or k > n:
            return 0
        res = self.fact[n] * self.inv[k] % self.MOD
        res = res * self.inv[n - k] % self.MOD
        return res

    def _make_factorial_list(self, N):
        fact = [1] * (N + 1)
        inv = [1] * (N + 1)
        MOD = self.MOD
        for i in range(1, N + 1):
            fact[i] = (fact[i - 1] * i) % MOD
        inv[N] = pow(fact[N], MOD - 2, MOD)
        for i in range(N, 0, -1):
            inv[i - 1] = (inv[i] * i) % MOD
        return fact, inv


if __name__ == "__main__":
    N = int(input())
    A = tuple(map(int, input().split()))
    mod = 10 ** 9 + 7

    X = max(set(A), key=A.count)
    left = A.index(X)
    right = A[::-1].index(X)
    LR = left + right

    comb = Combination(10 ** 5 + 10)
    ans = [-1] * (N + 1)
    for i in range(1, N + 2):
        ans[i - 1] = (comb(N + 1, i) - comb(LR, i - 1) + mod) % mod

    print(*ans, sep="\n")


### FIXED CODE ###

from collections import Counter

N = int(input())
A = tuple(map(int, input().split()))
mod = 10 ** 9 + 7

U = N + 10
fact = [1] * (U + 1)
inv = [1] * (U + 1)

for i in range(1, U + 1):
    fact[i] = fact[i - 1] * i % mod

inv[U] = pow(fact[i], mod - 2, mod)
for i in range(U, 0, -1):
    inv[i - 1] = inv[i] * i % mod


def comb(N, r):
    if r < 0 or r > N:
        return 0
    res = fact[N] * inv[r] % mod
    res = res * inv[N - r] % mod
    return res


X = Counter(A).most_common()[0][0]
left = A.index(X)
right = A[::-1].index(X)
LR = left + right

for i in range(1, N + 2):
    ans = comb(N+1, i)-comb(LR, i-1)
    ans = (ans + mod) % mod
    print(ans)
### BUGGY CODE ###

H, W = map(int, input().split())

S = []
for i in range(H):
    S.append(input())

b = [[[0, 0, 0, 0] for w in range(W)] for h in range(H)]
m = [[0]*W for i in range(H)]
for h in range(H):
    for w in range(W):
        if S[h][w] == '#':
            m[h][w] = 1

for h in range(H):
    for w in range(W):
        if m[h][w] == 1:
            continue
        # up
        if h-1 < 0 or m[h-1][w] == 1:
            b[h][w][0] = 0
        else:
            b[h][w][0] = b[h-1][w][0] + 1
        # left
        if w-1 < 0 or m[h][w-1] == 1:
            b[h][w][1] = 0
        else:
            b[h][w][1] = b[h][w-1][1] + 1

for h in range(H-1, -1, -1):
    for w in range(W-1, -1, -1):
        if m[h][w] == 1:
            continue
        # down
        if h+1 >= H or m[h+1][w] == 1:
            b[h][w][2] = 0
        else:
            b[h][w][2] = b[h+1][w][2] + 1
        # right
        if w+1 >= W or m[h][w+1] == 1:
            b[h][w][3] = 0
        else:
            b[h][w][3] = b[h][w+1][3] + 1

#for h in range(H):
#    print(b[h])
ans = 0
for h in range(H):
    for w in range(W):
        if m[h][w] == 1:
            continue
        tmp = sum(b[h][w]) + 1
        if tmp > ans:
            ans = tmp

print(ans)


### FIXED CODE ###

H, W = map(int, input().split())

S = []
for i in range(H):
    S.append(input())

U = [[0] * W for h in range(H)]
D = [[0] * W for h in range(H)]
L = [[0] * W for h in range(H)]
R = [[0] * W for h in range(H)]

for h in range(H):
    for w in range(W):
        if S[h][w] == 1:
            continue
        # up
        if h-1 < 0 or S[h-1][w] == '#':
            U[h][w] = 0
        else:
            U[h][w] = U[h-1][w] + 1
        # left
        if w-1 < 0 or S[h][w-1] == '#':
            L[h][w] = 0
        else:
            L[h][w] = L[h][w-1] + 1

for h in range(H-1, -1, -1):
    for w in range(W-1, -1, -1):
        if S[h][w] == 1:
            continue
        # down
        if h+1 >= H or S[h+1][w] == '#':
            D[h][w] = 0
        else:
            D[h][w] = D[h+1][w] + 1
        # right
        if w+1 >= W or S[h][w+1] == '#':
            R[h][w] = 0
        else:
            R[h][w] = R[h][w+1] + 1

ans = 0
for h in range(H):
    for w in range(W):
        if S[h][w] == '#':
            continue
        cnt = U[h][w] + L[h][w] + D[h][w] + R[h][w] + 1
        if cnt > ans:
            ans = cnt

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

s = input()
q = int(input())
rev = 0
mae = ""
usiro = ""

for i in range(q):
    a = input()
    
    if a[0] == '1':
        rev += 1
    else:
        if (int(a[2]) + rev) % 2 == 1:
            mae += a[4]
        else:
            usiro += a[4]

mae = list(reversed(mae))
mae2 = "".join(mae)
s = mae2 + s + usiro
if rev%2 == 0:
    print(s)
else:
    s = list(reversed(s))
    ans = "".join(s)
    print(ans)

### FIXED CODE ###

s = input()
q = int(input())
rev = 0
mae = []
usiro = []

for i in range(q):
    a = input()
    
    if a[0] == '1':
        rev += 1
    else:
        if (int(a[2]) + rev) % 2 == 1:
            mae.append(a[4])
        else:
            usiro.append(a[4])
            
mae = mae[::-1]
mae2 = "".join(mae)
usiro2 = "".join(usiro)
if rev%2 == 0:
    print(mae2 + s + usiro2)
else:
    ans = mae2 + s + usiro2
    print(ans[::-1])
### BUGGY CODE ###

S = list(map(int, list(input())))

mods = [0 for _ in range(2019)]
mods[0] = 1

num = 0
for itr, s in enumerate(S[::-1]):
  num = s * 10 ** itr + num
  mo = num % 2019
  mods[mo] += 1

#  print(itr, s, num, mo)
  
ans = 0
for m in mods:
  ans += m * (m - 1) // 2

print(ans)


### FIXED CODE ###

S = list(map(int, list(input())))

MOD = 2019

mods = [0 for _ in range(2019)]
mods[0] = 1

num = 0
digit = 1
for s in S[::-1]:
  num = s * digit + num
  num %= MOD
  mods[num] += 1
  digit = (digit * 10) % MOD
  
ans = 0
for m in mods:
  ans += m * (m - 1) // 2

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

N=int(input())

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

B=[]
count=0
for i in range(N):
  print(A.index(min(A))+1, end=' ')
  A[A.index(min(A))]=N+1

### FIXED CODE ###

import numpy as np


N=int(input())

A=np.array([list(map(int, input().split()))])


B=np.argsort(A[0,:])
for b in B:
  print(b+1, end=' ')
### BUGGY CODE ###

S = list(input())
con = 1
max = 0
while con != 0 :
    con = 0
    if (len(S) <= 1):
        break
    x = 0
    while True :
        if (x >= len(S)-1):
             break
        if(x <= len(S)-1 and 
            S[x] == '0' and S[x+1] == '1' or
            S[x] == '1' and S[x+1] == '0' ):
            max += 2
            del S[x:x+1+1]
            con = 1
        x += 1

print(max)

### FIXED CODE ###

S = list(input())
R = S.count('0')
B = S.count('1')

if(len(S) <= 1):
    print(0)
else:
    print(len(S) - abs(R-B))
### BUGGY CODE ###

h,w=map(int,input().split())
Ch,Cw=map(int,input().split())
Dh,Dw=map(int,input().split())
s=[list(input()) for _ in range(h)]

Ch,Cw=Ch-1,Cw-1
Dh,Dw=Dh-1,Dw-1
from heapq import heappop,heappush
todo=[[0,Ch,Cw]]
d=[[-1]*w for _ in range(h)]
d[Ch][Cw]=0
toho=[[0,1],[0,-1],[1,0],[-1,0]]
wiz=[[2,2],[2,1],[2,0],[2,-1],[2,-2],[1,2],[1,1],[1,-1],[1,-2],[0,2],[0,-2],[-1,2],[-1,1],[-1,-1],[-1,-2],[-2,2],[-2,1],[-2,0],[-2,-1],[-2,-2]]
while todo:
  cnt,nh,nw=heappop(todo)
  if d[nh][nw]<cnt:continue
  if [nh,nw]==[Dh,Dw]:
    print(cnt)
    exit()
  for dh,dw in toho:
    if 0<=nh+dh<h and 0<=nw+dw<w and s[nh+dh][nw+dw]!='#':
      if d[nh+dh][nw+dw]==-1 or d[nh+dh][nw+dw]>cnt:
        d[nh+dh][nw+dw]=cnt
        heappush(todo,[cnt,nh+dh,nw+dw])
  for dh,dw in wiz:
    if 0<=nh+dh<h and 0<=nw+dw<w and s[nh+dh][nw+dw]!='#':
      if d[nh+dh][nw+dw]==-1 or d[nh+dh][nw+dw]>cnt+1:
        d[nh+dh][nw+dw]=cnt+1
        heappush(todo,[cnt+1,nh+dh,nw+dw])
print(d[Dh][Dw])


### FIXED CODE ###

h,w=map(int,input().split())
Ch,Cw=map(int,input().split())
Dh,Dw=map(int,input().split())
s=[list(input()) for _ in range(h)]

Ch,Cw=Ch-1,Cw-1
Dh,Dw=Dh-1,Dw-1
todo=[[0,Ch,Cw]]
ntodo=[]
d=[[-1]*w for _ in range(h)]
d[Ch][Cw]=0
toho=[[0,1],[0,-1],[1,0],[-1,0]]
wiz=[[2,2],[2,1],[2,0],[2,-1],[2,-2],[1,2],[1,1],[1,-1],[1,-2],[0,2],[0,-2],[-1,2],[-1,1],[-1,-1],[-1,-2],[-2,2],[-2,1],[-2,0],[-2,-1],[-2,-2]]
while todo or ntodo:
  if not todo:
    todo=ntodo
    ntodo=[]
  cnt,nh,nw=todo.pop()
  if d[nh][nw]<cnt:continue
  for dh,dw in toho:
    if 0<=nh+dh<h and 0<=nw+dw<w and s[nh+dh][nw+dw]!='#':
      if d[nh+dh][nw+dw]==-1 or d[nh+dh][nw+dw]>cnt:
        d[nh+dh][nw+dw]=cnt
        todo.append([cnt,nh+dh,nw+dw])
  for dh,dw in wiz:
    if 0<=nh+dh<h and 0<=nw+dw<w and s[nh+dh][nw+dw]!='#':
      if d[nh+dh][nw+dw]==-1 or d[nh+dh][nw+dw]>cnt+1:
        d[nh+dh][nw+dw]=cnt+1
        ntodo.append([cnt+1,nh+dh,nw+dw])
print(d[Dh][Dw])
### BUGGY CODE ###

MOD=998244353
N=int(input())
A=[int(input()) for _ in range(N)]

TOTAL=pow(3,N,MOD)
ASum=sum(A)

dp=[[0 for _ in range(ASum+1)] for _ in range(2)]
dp[0][0] = 2
dp[0][A[0]] = 1

dpOther=[[0 for _ in range(ASum+1)] for _ in range(2)]
dpOther[0][0] = 1
dpOther[0][A[0]] = 1

prev=0
current=1
curMax=A[0]
for n in range(1,N):
	curMax += A[n]
	current = n % 2
	prev = (n+1) % 2
	for e in range(curMax+1):
		dp[current][e] = dp[prev][e]*2
		if A[n] <= e:
			dp[current][e] += dp[prev][e-A[n]]
		dp[current][e] %= MOD

		if ASum %2 == 0:
			dpOther[current][e] = dpOther[prev][e]
			if A[n] <= e:
				dpOther[current][e] += dpOther[prev][e-A[n]]
			dpOther[current][e] %= MOD

sumStart = 0
plus = 0

if ASum % 2 == 0:
	# 合計が偶数
	sumStart=ASum//2
	plus = (dpOther[current][ASum//2]*3) % MOD
else:
	# 合計が奇数の場合、ceil
	sumStart=ASum//2+1

exceptCnt=0
for s in range(sumStart,ASum+1):
	exceptCnt = (exceptCnt + dp[current][s]*3) % MOD

exceptCnt -= plus

print((TOTAL - exceptCnt) % MOD )



### FIXED CODE ###

import numpy as np

MOD=998244353
N=int(input())
A=np.array([int(input()) for _ in range(N)])
TOTAL=pow(3,N,MOD)
ASum=sum(A)
sumEnd=0
sumEnd=ASum//2+1

dp=np.array([0 for _ in range(sumEnd)],dtype=np.int64)
dp[0] = 1

for n in range(N):
	dp[A[n]:] += dp[:-A[n]]*2 % MOD

plus = 0
if ASum % 2 == 0:
	# 合計が偶数
	dpOther=np.array([0 for _ in range(sumEnd+1)],dtype=np.int64)
	dpOther[0] = 1
	for n in range(N):
		dpOther[A[n]:] += dpOther[:-A[n]] % MOD
	plus = (dpOther[ASum//2]*3) % MOD

exceptCnt=0
for s in range(0,sumEnd):
	exceptCnt = (exceptCnt + dp[s]*3) % MOD

exceptCnt -= plus
print((TOTAL - exceptCnt) % MOD )
### BUGGY CODE ###

def main():
    s = input()
    q = int(input())

    for i in range(q):
        tfc = input().split()

        if tfc[0] == '1':
            s = s[::-1]
        else:
            f = tfc[1]
            c = tfc[2]
            if f == '1':
                s = c + s
            else:
                s = s + c

    print(s)

if __name__ == "__main__":
    main()


### FIXED CODE ###

from collections import deque

def main():
    s = input()
    q = int(input())

    Q = deque(s)
    rev = False
    for i in range(q):
        tfc = input().split()

        if tfc[0] == '1':
            rev = not rev
        else:
            f = tfc[1]
            c = tfc[2]
            if (f == '1' and not rev) or (f != '1' and rev):
                Q.appendleft(c)
            else:
                Q.append(c)

    if rev:
        print(''.join(list(Q)[::-1]))
    else:
        print(''.join(Q))

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

# -*- coding: utf-8 -*-
#import numpy as np
def fnSolv():
  iNum, iK = map(int, input().split())
  lHn  = list(map(int, input().split()))
  lDP  = [0]*iK
  lLen = [0]*iK
  for iI0 in range(1, iNum):
    lRange = range(max([0, iI0 - iK]), iI0)
    iLen = len(lRange)
    for iI2, iI1 in enumerate(lRange):
      lLen[iI2] = lDP[iI1%iK] + abs(lHn[iI0] - lHn[iI1])
    lDP[iI0%iK] = min(lLen[:iLen])
    #print(iI0, lDP, lLen)
  print(lDP[(iNum-1)%iK])

if __name__ == '__main__':
  fnSolv()


### FIXED CODE ###

# -*- coding: utf-8 -*-
import numpy as np
def fnSolv():
  iNum, iK = map(int, input().split())
  naHn  = np.array(list(map(int, input().split())))
  naDP  = np.zeros(iNum, dtype='int64')
  naLen = np.ones(iK) * 10**9
  for iI0 in range(1, iNum):
    iK0 = min([iK, iI0])
    naLen = naDP[iI0-iK0:iI0] + np.abs(- naHn[iI0-iK0:iI0] + naHn[iI0])
    naDP[iI0] = naLen.min()
  print(naDP[iNum-1])

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

import collections
sum = 0
Asum=[]
N = int(input())
A =  [int(N) for N in input().split()]
B = A.copy()
for i in range(N):
    B.pop(i)
    c = collections.Counter(B)
    values, counts = zip(*c.most_common())
    for j in range(len(counts)):
        if counts[j]>1:
            sum+=int(counts[j]*(counts[j]-1)/2)
        else:
            break
    B=A.copy()
    Asum.append(int(sum))
    sum=0
for k in range(N):
    print(Asum[k])

### FIXED CODE ###

from collections import Counter
def choose2(n):
    return n*(n-1)/2
sum1=0
sum2=0
N = int(input())
A = [int(N) for N in input().split()]
S = Counter(A)
for i in  S.values():
    sum1+=int(choose2(i))
for j in range(N):
    sum2+=int(sum1-choose2(S[A[j]])+choose2(S[A[j]]-1))
    print(sum2)
    sum2=0
### BUGGY CODE ###

from fractions import gcd
from math import ceil,floor, sqrt, cos, sin, pi, factorial
from functools import reduce
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10**8)
INF = float('inf')
MOD = 10**9+7
def lcm_base(a, b):
    return (a * b) // gcd(a, b)
 
 
def main():
  k = int(input())
  ans = 0
  for a in range(1, k+1):
    for b in range(a, k+1):
      for c in range(b,k+1):
        if a==b and b==c:
          ans += a
        elif a==b or b==c:
          ans += gcd(gcd(a,b),c) * 3
        else:
          ans += gcd(gcd(a,b),c) * 6
  print(ans)
  
  
if __name__ == '__main__':
  main()

### FIXED CODE ###

from fractions import gcd
 
def main():
  k = int(input())
  ans = 0
  for a in range(1, k+1):
    for b in range(a, k+1):
      x = gcd(a,b)
      for c in range(b,k+1):
        if a==b and b==c:
          ans += a
        elif a==b or b==c:
          ans += gcd(x,c) * 3
        else:
          ans += gcd(x,c) * 6
  print(ans)
  
  
if __name__ == '__main__':
  main()
### BUGGY CODE ###

import sys
input = sys.stdin.readline
from collections import deque
h,w = map(int,input().split())
ch,cw = map(int,input().split())
dh,dw = map(int,input().split())
s = [list(input()) for _ in range(h)]
INF=10**7

queue = deque()

cost = [[INF]*w for _ in range(h)]
cost[ch-1][cw-1]=0

dxdy = [[1,0],[-1,0],[0,1],[0,-1]]
warp = []
for m in range(-2,3):
    for n in range(-2,3):
        if [m,n] not in [[0,0],[1,0],[-1,0],[0,1],[0,-1]]:
            warp += [[m,n]]

queue.append([ch-1,cw-1,0])

while queue:
    x,y,d = queue.popleft()
    for dx,dy in dxdy:
        nx,ny = x+dx,y+dy
        if -1<nx<h and -1<ny<w and s[nx][ny]!="#" and d<cost[nx][ny]:
            cost[nx][ny]=d
            queue.append([nx,ny,d])
            #[print(*cost[l]) for l in range(h)]
            #print("---------------")

    for dx,dy in warp:
        nx,ny = x+dx,y+dy
        if -1<nx<h and -1<ny<w and s[nx][ny]!="#" and d+1<cost[nx][ny]:            
            cost[nx][ny]=d+1
            queue.append([nx,ny,d+1])
            #[print(*cost[l]) for l in range(h)]
            #print("---------------")


if cost[dh-1][dw-1]<INF:
    print(cost[dh-1][dw-1])
else:
    print(-1)



### FIXED CODE ###

from collections import deque
h,w = map(int,input().split())
ch,cw = map(int,input().split())
dh,dw = map(int,input().split())
s = [list(input()) for _ in range(h)]
INF=10**7

queue = deque()

cost = [[INF]*w for _ in range(h)]
cost[ch-1][cw-1]=0

dxdy = [[1,0],[-1,0],[0,1],[0,-1]]
warp = []
for m in range(-2,3):
    for n in range(-2,3):
        if [m,n] not in [[0,0],[1,0],[-1,0],[0,1],[0,-1]]:
            warp += [[m,n]]

queue.append([ch-1,cw-1,0])

while queue:
    x,y,d = queue.popleft()
    for dx,dy in dxdy:
        nx,ny = x+dx,y+dy
        if -1<nx<h and -1<ny<w and s[nx][ny]!="#" and d<cost[nx][ny]:
            cost[nx][ny]=d
            queue.appendleft([nx,ny,d])
            #[print(*cost[l]) for l in range(h)]
            #print("---------------")

    for dx,dy in warp:
        nx,ny = x+dx,y+dy
        if -1<nx<h and -1<ny<w and s[nx][ny]!="#" and d+1<cost[nx][ny]:            
            cost[nx][ny]=d+1
            queue.append([nx,ny,d+1])
            #[print(*cost[l]) for l in range(h)]
            #print("---------------")


if cost[dh-1][dw-1]<INF:
    print(cost[dh-1][dw-1])
else:
    print(-1)
### BUGGY CODE ###

from math import gcd

# = map(int, input().split())
N = int(input())
A = list(map(int, input().split()))
mA = max(A)
counter = [0 for _ in range(mA+1)]

primenum = [2]
sgn = [-1 for _ in range(int(mA**0.5)+1)]
k = 3
while k**2 <= mA:
  if sgn[k] == -1:
    primenum.append(k)
    add = k*k
    ok = k
    while ok**2 <= mA:
      sgn[ok] = 1
      ok += add
  k += 2
#prime_num が用意されているとき
def factorization(n):
  M = n
  for p in primenum:
    if p**2 > M:
      break
    else:
      if M%p == 0:
        if counter[p] == 0:
          counter[p] = 1
        else:
          return False
        while M%p == 0:
          M //= p

  if M > 1:
    if counter[M] == 0:
      counter[M] = 1
    else:
      return False
  return True



g = A[0]
flag = True
for k in range(N):
  a = A[k]
  g = gcd(g, a)
  if flag:
    flag = factorization(a)


if flag:
  print('pairwise coprime')
  exit()
if g == 1:
  print('setwise coprime')
else:
  print('not coprime')


### FIXED CODE ###

from math import gcd

# = map(int, input().split())
N = int(input())
A = list(map(int, input().split()))
mA = max(A)
counter = [0 for _ in range(mA+1)]

primenum = [2]
sgn = [-1 for _ in range(int(mA**0.5)+1)]
k = 3
while k**2 <= mA:
  if sgn[k] == -1:
    primenum.append(k)
    add = k*k
    ok = k
    while ok**2 <= mA:
      sgn[ok] = 1
      ok += add
  k += 2
#prime_num が用意されているとき
def factorization(n):
  M = n
  for p in primenum:
    if p**2 > M:
      break
    else:
      if M%p == 0:
        if counter[p] == 0:
          counter[p] = 1
        else:
          return False
        while M%p == 0:
          M //= p

  if M > 1:
    if counter[M] == 0:
      counter[M] = 1
    else:
      return False
  return True



g = A[0]
flag = True
for k in range(N):
  a = A[k]
  g = gcd(g, a)
  if flag:
    flag = factorization(a)


if flag:
  print('pairwise coprime')
  exit()
if g == 1:
  print('setwise coprime')
else:
  print('not coprime')
### BUGGY CODE ###

import math
K = int(input())
cnt = 0
tmp = 0
for a in range(1, K+1):
    for b in range(1, K+1):
        for c in range(1, K+1):
            tmp = math.gcd(a, b)
            cnt += math.gcd(tmp, c)

print(cnt)

### FIXED CODE ###

import math
K = int(input())
cnt = 0
tmp = 0
for a in range(1, K+1):
    for b in range(1, a+1):
        for c in range(1, b+1):
            if a==b==c:
                tmp = math.gcd(a, b)
                cnt += math.gcd(tmp, c)
            elif a!=b!=c!=a:
                tmp = math.gcd(a, b)
                cnt += 6*math.gcd(tmp, c)
            else:
                tmp = math.gcd(a, b)
                cnt += 3*math.gcd(tmp, c)

print(cnt)
### BUGGY CODE ###

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

dp = [""] * (N+1)
d = {
    1: 2,
    2: 5,
    3: 5,
    4: 4,
    5: 5,
    6: 6,
    7: 3,
    8: 7,
    9: 6
}

c = [(i, d[i]) for i in A]
c.sort(key=lambda x:(-x[1], -x[0]))
minpos = min(c, key=lambda x:x[1])[1]

dp[0] = ""
dp[1] = ""

for i in range(minpos, N+1):
    for n, cost in c:
        if i-cost<0: continue
        if 0<i-cost<minpos: continue
        a = int(dp[i]) if dp[i] else 0
        b = int(str(n) + dp[i-cost])
        if a<b:
            dp[i] = str(n) + dp[i-cost]

print(dp[N])

### FIXED CODE ###

from collections import defaultdict as dd

n,m=map(int,input().split())
*a,=map(int,input().split())
dp=[-1]*(n+1)
ans = [0] * (n + 1)

cost={1:2,2:5,3:5,4:4,5:5,6:6,7:3,8:7,9:6}

d={i:cost[i] for i in a}

dp[0] = 0
for i in range(1,n+1):
    for j in range(10)[::-1]:
        if not j in d:
            continue
        if cost[j] > i:
            continue
        if dp[i] < dp[i - cost[j]] + 1:
            dp[i] = dp[i - cost[j]] + 1
            ans[i] = j

S = ""
pos = n

while pos != 0:
    S += str(ans[pos])
    pos -= cost[ans[pos]]

print(S)