Our Algorithm

n, k = map(int,input().split())
a = []
for i in range(n):
    a.append(int(input()))
D = [0 for _ in range(k+1)]
for i in range(1, k+1):
    c = []
    for j in a:
        if j <= i and D[i-j] != -1:
            c.append(D[i-j])
        if not a:
            D[i] = -1
        else:
            D[i] = min(c)+1
print(D[k])

def P(m, n):
    result = 1
    for i in range(n, n-m, -1):
        result *= i
    for j in range(m,0,-1):
        result /= j
    return int(result)
T = int(input())
N = []
M = []
arr = []
for _ in range(T):
    a, b = map(int, input().split(" "))
    N.append(a)
    M.append(b)
    arr.append(P(a, b))
for a in arr:
    print(a)

N = int(input())
T = [0]
P = [0]
D = [0] * (N+2)     #D[0]~D[8]까지
for i in range(N):
    a, b = map(int, input().split(" "))
    T.append(a)
    P.append(b)
for i in range(2, N+2):
    for j in range(1, i):
        D[i] = max(D[i], D[j])
        if i == j + T[j]:
            D[i] = max(D[i], D[j] + P[j])
print(max(D))

#1463 1로 만들기
X = int(input())  #1이상의 숫자만 입력
D = [0 for _ in range(X+1)]
D[0] = -1
D[1] = 0
D[2] = 1
for i in range(3, X+1):
    if i % 3 == 0:
        D[i] = min(D[i // 3] + 1, D[i - 1] + 1)
    elif i % 2 == 0:
        D[i] = min(D[i // 2] + 1, D[i - 1] + 1)
    else:
        D[i] = D[i-1]+1
print(D[X])

def EditDistance(source, target):   #source에서 target으로의 편집거리를 구하는 함수
    D = [[0]*(len(target)+1) for _ in range(len(source)+1)] #2차원배열을 0으로 초기화
    for i in range(len(source) + 1):
        D[i][0] = i                     #target의 길이가 0이므로 편집거리를 0으로 초기화
    for j in range(len(target) + 1):
        D[0][j] = j                     #source의 길이가 0이므로 편집거리를 0으로 초기화
    for i in range(1, len(source) + 1):
        for j in range(1, len(target) + 1):
            if source[i-1] == target[j-1]:  #마지막 글자가 같으면 a는 0
                a = 0
            else:                           #마지막 글자가 다르면 a는 1
                a = 1
            D[i][j] = min(D[i][j-1] + 1, D[i-1][j] + 1, D[i-1][j-1] + a)
    return D[len(source)][len(target)]
def TextTolist(Text):               #Text를 단어별로 나눠서 리스트로 만드는 함수
    f = open(Text, 'r', encoding='UTF8')
    text = f.read()
    f.close()
    text = text.replace("\n", " ")  # 줄바꿈을 공백으로 바꿈
    text = text.replace(".", "")  # .을 지워버림
    TextToList = text.split(" ")
    return TextToList
def ListToDic(Text_List, ED_List):      #TextList와 E_D_list를 합쳐서 딕셔너리로 만드는 함수
    dic = dict()
    for i in range(len(Text_List)):
        dic[Text_List[i]] = ED_List[i]
    return dic
Target = input("단어를 입력하세요 : ")
TextList = TextTolist("text.txt")
E_D_list = []
for k in range(len(TextList)):
    E_D = EditDistance(TextList[k], Target)
    E_D_list.append(E_D)
E_D_Dic = ListToDic(TextList, E_D_list)
E_D_Dic = sorted(E_D_Dic.items(), key=lambda x: x[1])
for i in range(5):
    print("{0}번째로 유사한 단어는 {1}이고 편집횟수는 {2}회".format(i+1, E_D_Dic[i][0], E_D_Dic[i][1]))