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

import bisect
def main():
    n,k=map(int,input().split())
    a=list(map(int,input().split()))
    a.sort()
    l=0
    r=n
    if sum(a)<k:
        print(n)
    else:
        while l!=r:
            i=(l+r)//2
            ta = a[i]
            if ta>=k:flag=True
            else:
                flag = False
                na = a[:i]+a[i+1:]
                dp = [False for _ in range(k+1)]
                dp[0]=True
                for j in range(n-1):
                    for m in range(k,0,-1):
                        if m-na[j]>=0:
                            dp[m]=dp[m] or dp[m-na[j]]
                        if m != k and m>=k-ta and dp[m]:
                            flag = True
                            break
                    if flag:break
            if flag:
                r=i
            else:
                l=i+1
        print(l)

main()

### FIXED CODE ###

import bisect
def main():
    n,k=map(int,input().split())
    a=list(map(int,input().split()))
    a.sort()
    l=0
    r=n
    d = {}
    if sum(a)<k:
        print(n)
    else:
        while l!=r:
            i=(l+r)//2
            ta = a[i]
            if ta in d.keys():
                flag = d[ta]
            elif ta>=k:flag=True
            else:
                flag = False
                na = a[:i]+a[i+1:]
                dp = [False for _ in range(k+1)]
                dp[0]=True
                for j in range(n-1):
                    for m in range(k,0,-1):
                        if m-na[j]>=0:
                            dp[m]=dp[m] or dp[m-na[j]]
                        if m != k and m>=k-ta and dp[m]:
                            flag = True
                            break
                    if flag:break
                d[ta] = flag
            
            if flag:
                r=i
            else:
                l=i+1
        print(l)

main()
### BUGGY CODE ###

import sys
sys.setrecursionlimit(1000000000)

n = int(input())
h= list(map(int, input().split())) 

count = 0
ans = 0
def dfs(s):
    if s + 1 < len(h):
        if h[s] >= h[s+1]:
            global count 
            count = count + 1
            dfs(s+1)
    

for i in range(len(h)):
    count = 0
    dfs(i)
    if count > ans :
        ans = count
        
print(ans)
    

### FIXED CODE ###

n = int(input())
h= list(map(int, input().split())) 

count = 0
ans = 0

for i in range(len(h)):
    if i + 1 < len(h):
        if h[i] >= h[i+1]:
            count = count + 1
        else:
            count = 0
    if count > ans :
        ans = count
        
print(ans)
### BUGGY CODE ###

h,w = map(int,input().split())
matrix = [["a" for _ in range(w+2)]] + [list("a" + input() + "a") for _ in range(h)] + [["a" for _ in range(w+2)]]

matrix_list1 = []
matrix_list2 = []
cnt = 0

for i in range(1,h+1):
    for j in range(1,w+1):
        if matrix[i][j] == "#":
            matrix_list1.append([i,j])

while len(matrix_list1) != 0:     
    for x,y in matrix_list1:
        if matrix[x+1][y] == ".":
            matrix[x+1][y] = "#"
            matrix_list2.append([x+1,y])
        if matrix[x-1][y] == ".":
            matrix[x-1][y] = "#"
            matrix_list2.append([x-1,y])
        if matrix[x][y+1] == ".":
            matrix[x][y+1] = "#"
            matrix_list2.append([x,y+1])
        if matrix[x][y-1] == ".":
            matrix[x][y-1] = "#"
            matrix_list2.append([x,y-1])
    else:
        matrix_list1 = matrix_list2.copy()
        matrix_list2 = []
        if len(matrix_list1) > 0:
            cnt += 1
    
print(cnt)

### FIXED CODE ###

from collections import deque

h,w = map(int,input().split())
matrix = [["a" for _ in range(w+2)]] + [list("a" + input() + "a") for _ in range(h)] + [["a" for _ in range(w+2)]]

matrix_list1 = deque()
cnt = 0

for i in range(1,h+1):
    for j in range(1,w+1):
        if matrix[i][j] == "#":
            matrix_list1.append([i,j])

while len(matrix_list1) != 0:     
    for _ in range(len(matrix_list1)):
        x,y = matrix_list1.popleft()
        if matrix[x+1][y] == ".":
            matrix[x+1][y] = "#"
            matrix_list1.append([x+1,y])
        if matrix[x-1][y] == ".":
            matrix[x-1][y] = "#"
            matrix_list1.append([x-1,y])
        if matrix[x][y+1] == ".":
            matrix[x][y+1] = "#"
            matrix_list1.append([x,y+1])
        if matrix[x][y-1] == ".":
            matrix[x][y-1] = "#"
            matrix_list1.append([x,y-1])
    else:
        if len(matrix_list1) > 0:
            cnt += 1
    
print(cnt)
### BUGGY CODE ###

# coding: utf-8
# Your code here!
import math
n,K=map(int,input().split())
h=list(map(int,input().split()))
dp=[math.inf for _ in range(n)]
dp[0]=0
for i in range(1,n):
    for k in range(1,K+1):
        if i-k<0:
            continue
        else:
            dp[i]=min(dp[i],dp[i-k]+abs(h[i]-h[i-k]))
print(dp[n-1])

### FIXED CODE ###

import math
n,k=map(int,input().split())
h=list(map(int,input().split()))
dp=[math.inf for i in range(n)]
dp[0]=0
for i in range(1,n):
    for j in range(1,k+1):
        if i-j<0:
            continue
        dp[i]=min(dp[i-j]+abs(h[i]-h[i-j]),dp[i])
print(dp[n-1])
### BUGGY CODE ###

R, G, B, N = map(int, input().split())

ans = 0
for r in range(N//R + 1):
    for g in range((N - r*R)//G + 1):
        for b in range((N - r*R - g*G)//B + 1):
            if r*R + g*G + b*B == N:
                ans += 1
print(ans)

### FIXED CODE ###

R, G, B, N = map(int, input().split())

ans = 0
for r in range(N//R + 1):
    for g in range((N - r*R)//G + 1):
        if (N - r*R - g*G)%B == 0:
                ans += 1
print(ans)
### BUGGY CODE ###

n = str(input().rstrip())

def solve1(n):
    ans = 0

    a = list(map(int, list(n)))
    a = a[::-1]
    a.append(0)
    for i in range(len(a) - 1):
        c = a[i]
        if c < 5:
            ans += c
        else:
            if c == 5 and a[i+1] < 5:
                ans += 5
            else:
                a[i+1] += 1
                ans += 10 - c
    ans += n_list[-1]

    print(ans)

def solve2(n):
    INF = 10**9
    n = n[::-1]
    n += '0'
    n_len = len(n)
    dp = [[INF for _ in range(2)] for _ in range(n_len+1)]
    dp[0][0] = 0

    for i in range(n_len):
        for j in range(2):
            x = int(n[i])
            x += j
            if x < 10:
                dp[i+1][0] = min(dp[i+1][0], dp[i][j]+x)
            if x > 0:
                dp[i+1][1] = min(dp[i+1][1], dp[i][j]+(10-x))

    print(dp[n_len][0])
solve2(n)

### FIXED CODE ###

n = str(input().rstrip())

ans = 0

a = list(map(int, list(n)))
a = a[::-1]
a.append(0)
for i in range(len(a) - 1):
    c = a[i]
    if c < 5:
        ans += c
    else:
        if c == 5 and a[i+1] < 5:
            ans += 5
        else:
            a[i+1] += 1
            ans += 10 - c
ans += a[-1]

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

n=int(input())
x=0
for i in range(n):
  x=x+i
print(x)

### FIXED CODE ###

n=int(input())
print(n*(n-1)//2)
### BUGGY CODE ###

import copy
import collections
def kaijyou(k):
  N=1
  for i in range(k,0,-1):
    N*=i
  return N

def combinations(n,r):
  return int(kaijyou(n)/(kaijyou(r)*kaijyou(n-r)))

N=int(input())
A=list(map(int,input().split()))
B=sorted(set(A))
d=[]
dp=[]

for i in B:
  C=copy.copy(A)
  C.remove(i)
  c=collections.Counter(C)
  d.append(c)

for i in d:
  e=i.values()
  f=0
  for k in e:
    f+=combinations(k,2)
  dp.append(f)
for i in A:
  print(dp[B.index(i)])

### FIXED CODE ###

import collections
N=int(input())
A=list(map(int,input().split()))
c=collections.Counter(A)

#全体の数列について答えを求めるnC2=n(n-1)/2
ALL=0
for i in c.values():
  if i>1:
    ALL += i*(i-1)//2

#各要素が影響する分を求める
for i in A:
  if c[i]>2:
    print(ALL-c[i]+1)
  elif c[i]==2:
    print(ALL-1)
  else:
    print(ALL)
### BUGGY CODE ###

X,Y,Z,K = map(int, input().split())
cakes = [list(map(int, input().split())) for _ in range(3)]
 
cakes = list(map(lambda x : sorted(x, reverse=True), cakes))
ans = list()
for i in range(X):
    if X>K:
        break
    for j in range(Y):
        for k in range(Z):
            ans.append(cakes[0][i] + cakes[1][j] + cakes[2][k])
ans.sort(reverse=True)
print("\n".join(map(str, ans[:K])))


### FIXED CODE ###

X,Y,Z,K = map(int, input().split())
cakes = [list(map(int, input().split())) for _ in range(3)]
 
cakes = list(map(lambda x : sorted(x, reverse=True), cakes))
ans = list()
for i in range(X):
    for j in range(Y):
        for k in range(Z):
            if (i+1)*(j+1)*(k+1)>K:
                break
            ans.append(cakes[0][i] + cakes[1][j] + cakes[2][k])
ans.sort(reverse=True)
print("\n".join(map(str, ans[:K])))
### BUGGY CODE ###

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


n, m = map(int, input().split())
uf = UnionFind(n)
for i in range(m):
    a, b = map(int, input().split())
    uf.union(a-1, b-1)

ans = 0
for y in uf.all_group_members().values():
    ans = max(ans, len(y))

print(ans)

### FIXED CODE ###

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

from collections import defaultdict
n, m = map(int, input().split())
uf = UnionFind(n)
for i in range(m):
    a, b = map(int, input().split())
    uf.union(a-1, b-1)

ans = defaultdict(int)
for i in range(n):
    ans[uf.find(i)] += 1

print(max(ans.values()))
### BUGGY CODE ###

h, w, d = [int(i) for i in input().split()]
a = [[int(j)-1 for j in input().split()] for i in range(h)]

q = int(input())#moving num
l = [0 for i in range(q)]#start number
r = [0 for i in range(q)]#finish number

for i in range(q):
    tmp = input().split()
    l[i]=int(tmp[0])-1
    r[i]=int(tmp[1])-1
loc = [[0, 0] for i in range(h*w)]
for i in range(h):
    for j in range(w):
        loc[a[i][j]][0] = i
        loc[a[i][j]][1] = j
#print(loc)
cost = 0
index = 0
for i in range(q):
    cost = 0
    for j in range(int((r[i]-l[i])/d)):
        #print("{}->{}:{}+{}".format(l[i]+j*d,l[i]+(j+1)*d,
            #abs(loc[l[i]+(j+1)*d][0]-loc[l[i]+j*d][0]),
            #abs(loc[l[i]+(j+1)*d][1]-loc[l[i]+j*d][1])))
        index = l[i]+j*d
        cost += abs(loc[index+d][0]-loc[index][0])
        cost += abs(loc[index+d][1]-loc[index][1])
    print(cost)



### FIXED CODE ###

import math
def func(h, w, d, a, query):
    imos = [0 for _ in range(h*w)]
    pos = [[0, 0] for _ in range(h*w)]
    for i in range(h):
        for j in range(w):
            pos[a[i][j]] = [i, j]
    for i in range(d):
        for j in range(math.ceil((h*w-i)/d)):
            if j == 0:
                continue
            else:
                imos[i + d * j] = imos[i + d * (j-1)]\
                                  + abs(pos[i + d * j][0] - pos[i + d * (j-1)][0])\
                                  + abs(pos[i + d * j][1] - pos[i + d * (j-1)][1])
    for i in range(len(query)):
        print(imos[query[i][1]] - imos[query[i][0]])
    return
h, w, d = [int(i) for i in input().split()]
a = [[0 for _ in range(w)] for _ in range(h)]
for i in range(h):
    a[i] = [int(i) - 1 for i in input().split()]
q = int(input())
query = [[0, 0] for _ in range(q)]
for i in range(q):
    query[i] = [int(i) - 1 for i in input().split()]
func(h, w, d, a, query)
"""
func(3, 3, 2, [[0, 3, 2], [1, 4, 6], [7, 8, 5]], [[3, 7]])
print("ans: 5\n")
func(4, 2, 3, [[2, 6], [0, 3], [4, 1], [5, 7]], [[1, 1], [1, 1]])
print("ans: 0, 0\n")
func(5, 5, 4, [[12, 24, 6, 14, 16], [15, 21, 19, 1, 8], [13, 10, 11, 0, 18], [9, 5, 22, 7, 17], [2, 20, 4, 23, 3]], [[12, 12], [1, 9], [12, 12]])
print("ans: 0, 5, 0")
"""
# print("func({}, {}, {}, {}, {})".format(h, w, d, a, query))
### BUGGY CODE ###

import collections
import sys
input = sys.stdin.readline
N = int(input())
ab = [list(map(int, input().split())) for i in range(N-1)]
eda = [set() for i in range(N)]
for a, b in ab:
    eda[a-1].add(b)
    eda[b-1].add(a)
max_e = 0
for i in range(N-1):
    max_e = max(max_e, len(eda[i]))
id = 0
for i in range(N):
    if len(eda[i]) == max_e:
        id = i

ans = [1]*(N-1)
q = collections.deque([(id, 0)])
print(max_e)
ans = [[0]*N for i in range(N)]
eda2 = [set() for j in range(N)]

g = [set() for i in range(N)]

for a, b in ab:
    g[a-1].add(b-1)
    g[b-1].add(a-1)


while(q):
    x, color = q.popleft()
    i = 1
    for y in g[x]:
        if i == color:
            i += 1
        ans[x][y] = i
        ans[y][x] = i
        g[y].remove(x)
        q.append((y, i))
        i += 1

for a, b in ab:
    print(ans[a-1][b-1])


### FIXED CODE ###

import collections
import sys
input = sys.stdin.readline
N = int(input())
ab = [list(map(int, input().split())) for i in range(N-1)]
eda = [set() for i in range(N)]
for a, b in ab:
    eda[a-1].add(b)
    eda[b-1].add(a)
max_e = 0
for i in range(N-1):
    max_e = max(max_e, len(eda[i]))
id = 0
for i in range(N):
    if len(eda[i]) == max_e:
        id = i

q = collections.deque([(id, 0)])
print(max_e)
d = dict()
for a, b in ab:
    d[(a-1, b-1)] = 0
    d[(b-1, a-1)] = 0
eda2 = [set() for j in range(N)]

g = [set() for i in range(N)]

for a, b in ab:
    g[a-1].add(b-1)
    g[b-1].add(a-1)


while(q):
    x, color = q.popleft()
    i = 1
    for y in g[x]:
        if i == color:
            i += 1
        d[(x, y)] = i
        d[(y, x)] = i
        g[y].remove(x)
        q.append((y, i))
        i += 1

for a, b in ab:
    print(d[(a-1, b-1)])
### BUGGY CODE ###

n, m = list(map(int, input().split()))
a = list(map(int, input().split()))
bc = [[0] * 2] * m

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

a.sort()
bc = sorted(bc, key=lambda x: -x[1])
new = []

for e in bc:
    new.extend([e[1]] * e[0])

for i in range(min(n, len(new))):
    a[i] = max(a[i], new[i])

print(sum(a))


### FIXED CODE ###

n, m = list(map(int, input().split()))
a = list(map(int, input().split()))
bc = [[0] * 2] * m

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

a.sort()
bc = sorted(bc, key=lambda x: -x[1])
new = []

cnt = 0

for e in bc:
    new += [e[1]] * e[0]
    cnt += e[0]

    if (n <= cnt):
        break

for i in range(min(n, cnt)):
    a[i] = max(a[i], new[i])

print(sum(a))
### BUGGY CODE ###

n=int(input())
s=[]
for i in range(n):
    s.append(int(input()))
s.sort(reverse=True)
S=sum(s)

while S % 10 == 0:
    for j in s:
        S=sum(s)-j
print(S)

    

### FIXED CODE ###

n=int(input())
s=[]
for i in range(n):
    s.append(int(input()))
s.sort()
S=sum(s)
ans=S
min=-1
if S % 10 == 0:
    for i in s:
        if i % 10 != 0:
            min=i
            break
else:
  min=0
  
if min >= 0:
    print(ans-min)
else:
    print(0)
### BUGGY CODE ###

#!/usr/bin/python3
def left(i):
    return i * 2

def right(i):
    return i * 2 + 1

def parent(i):
    return i // 2

def heap_increase_key(A, key):
    i = len(A) - 1
    A[i] = key
    while i > 1 and A[parent(i)] < A[i]:
        A[i], A[parent(i)] = A[parent(i)], A[i]
        i = parent(i)

def insert(A, key):
    A.append(-float('inf'))
    heap_increase_key(A, key)

def max_heapify(A, i):
    H = len(A) - 1
    if H == 0:
        return
    l = left(i)
    r = right(i)

    child = {}
    child[i] = A[i] 
    if l <= H:
        child[l] = A[l]
    if r <= H:
        child[r] = A[r]
    largest = max(child.items(), key=lambda x:x[1])[0]

    if largest != i:
        A[i], A[largest] = A[largest], A[i]
        max_heapify(A, largest)

def heap_extract_max(A):
    H = len(A) - 1
    m = A[1]
    A[1] = A[H]
    del A[H]
    max_heapify(A, 1)
    return m

# main
A = [0]
while True:
    s = input().split()
    if s[0].startswith('i'):
        insert(A, int(s[1]))
    elif s[0].startswith('ex'):
        print(heap_extract_max(A))
    if s[0] == 'end':
        exit()

### FIXED CODE ###

#!/usr/bin/python3
import sys
import heapq

# main
q = []
S = sys.stdin.readlines()
for line in S:
    if line[0].startswith('i'):
        heapq.heappush(q, -int(line.split()[1]))
    elif line[1] == 'x':
        print(-heapq.heappop(q))
    else:
        exit()
### BUGGY CODE ###

N = int(input())
boss = input().split(" ")
for i in range(1,N+1):
  print(boss.count(str(i)))
 	

### FIXED CODE ###

N = int(input())
l = [0]*N
boss = input().split(" ")
for i in range(N-1):
  l[int(boss[i])-1]+=1
for j in range(N):
  print(l[j])
### BUGGY CODE ###

import collections
import sys

input = sys.stdin.readline

ri = lambda: int(input())
rs = lambda: input().rstrip()
ril = lambda: list(map(int, input().split()))
rsl = lambda: input().rstrip().split()
ris = lambda n: [ri() for _ in range(n)]
rss = lambda n: [rs() for _ in range(n)]
rils = lambda n: [ril() for _ in range(n)]
rsls = lambda n: [rsl() for _ in range(n)]


def eratosthenes(n):
    sieve = [True for _ in range(n + 1)]
    sieve[0] = False
    sieve[1] = False

    def _update(p):
        if sieve[p]:
            for i in range(p * 2, n + 1, p):
                sieve[i] = False

    if n > 1:
        _update(2)
    p = 3
    while p * p <= n:
        _update(p)
        p += 2
    return sieve


def factorize(n, primes):
    import collections
    if n < 2:
        return dict()
    counter = collections.Counter()
    for p in primes:
        while n % p == 0:
            counter[p] += 1
            n //= p
        if n == 1:
            break
    if n != 1:
        counter[n] = 1
    return counter


sieve = eratosthenes(10**3)
primes = [i for i, b in enumerate(sieve) if b]

MOD = 10**9 + 7

n = ri()
ls = ril()
if n == 1:
    print(1)
    exit()

factorizations = []
for x in ls:
    factorizations.append(factorize(x, primes))
lcm = collections.Counter()
for counter in factorizations:
    for p, k in counter.items():
        lcm[p] = max(lcm[p], k)

res = 0
for counter in factorizations:
    s = 1
    for p, k in lcm.items():
        s *= p**(k - counter[p])
        s %= MOD
    res += s
    res %= MOD
print(res)

### FIXED CODE ###

import sys

input = sys.stdin.readline

ri = lambda: int(input())
rs = lambda: input().rstrip()
ril = lambda: list(map(int, input().split()))
rsl = lambda: input().rstrip().split()
ris = lambda n: [ri() for _ in range(n)]
rss = lambda n: [rs() for _ in range(n)]
rils = lambda n: [ril() for _ in range(n)]
rsls = lambda n: [rsl() for _ in range(n)]


def gcd(a, b):
    while True:
        a, b = b, a % b
        if b == 0:
            break
    return a


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


MOD = 10**9 + 7

n = ri()
ls = ril()
if n == 1:
    print(1)
    exit()

x = ls[0]
for i in range(1, n):
    x = lcm(x, ls[i])
ds = [x // y for y in ls]
print(sum(ds) % MOD)
### BUGGY CODE ###

N,M=map(int,input().split())
A=list(map(int,input().split()))
num=[0,2,5,5,4,5,6,3,7,6]
dp=[[1,0,0,0,0,0,0,0,0,0]]
tmp=0
tmp1=0
tmp2=0
for i in range(0,N+1):
    dp.append([0,0,0,0,0,0,0,0,0,0])
    tmp=0
    for j in A:
        if(i-num[j]>=0):
            tmp1=dp[i-num[j]].copy()
            #存在しないなら不可
            if(tmp1[0]==0):
                continue
            tmp1[j]+=1
            tmp2=int("9"*tmp1[9]+"8"*tmp1[8]+"7"*tmp1[7]+"6"*tmp1[6]+"5"*tmp1[5]+"4"*tmp1[4]+"3"*tmp1[3]+"2"*tmp1[2]+"1"*tmp1[1])
            if(tmp2>tmp):
                tmp=tmp2
                dp[i]=tmp1
ans=0
for k in range(1,10):
    if(dp[N][10-k]!=0):
        ans*=10**dp[N][10-k]
        ans+=(10-k)*int("1"*dp[N][10-k])
print(int(ans))
    

### FIXED CODE ###

N,M=map(int,input().split())
A=list(map(int,input().split()))
if(1 in A):
    if(4 in A):
        A.remove(4)
    if(9 in A):
        A.remove(9)
    if(6 in A):
        A.remove(6)
if(5 in A):
    if(3 in A):
        A.remove(3)
    if(2 in A):
        A.remove(2)
if(3 in A):
    if(2 in A):
        A.remove(2)
if(9 in A):
    if(6 in A):
        A.remove(6)
if(7 in A):
    if(9 in A):
        A.remove(9)
    if(6 in A):
        A.remove(6)
num=[0,2,5,5,4,5,6,3,7,6]
dp=[0]
keta=[0]
tmp=0
tmp1=0
tmp_keta=-1
tmp1_keta=-1
for i in range(1,N+1):
    tmp=-1
    tmp_keta=-1
    for j in A:
        tmp1=-1
        tmp1_keta=-1
        if(i-num[j]>=0):
            if(dp[i-num[j]]>0):
                tmp1=dp[i-num[j]]+j*(10**keta[i-num[j]])
                tmp1_keta=keta[i-num[j]]+1
            elif(dp[i-num[j]]==0):
                tmp1=j
                tmp1_keta=1

            if(tmp1>tmp):
                tmp=tmp1
                tmp_keta=tmp1_keta
                
    dp.append(tmp)
    keta.append(tmp_keta)
print(dp[N])
### BUGGY CODE ###

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

max_val = -1
max_pairs = None
for i in range(N-K+1):
    if sum(P[i:i+K]) > max_val:
        max_val = sum(P[i:i+K])
        max_pairs = P[i:i+K]

print(sum([(1+p)/2 for p in max_pairs]))

### FIXED CODE ###

def main():
    N, K = map(int, input().split())
    P = list(map(int, input().split()))

    P = [(1+p)/2 for p in P]
    p_sum = [sum(P[:K])]
    for i in range(K, N):
        p_sum.append(p_sum[-1] - P[i-K] + P[i])
    print(max(p_sum))

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

from itertools import combinations

n = int(input())
l = list(map(int, input().split()))
cnt = 0
for i in combinations(range(n), 3):
    a,b,c = i
    if (l[a] < l[b] + l[c]) and (l[b] < l[c] + l[a]) and (l[c] < l[b] + l[a]):
        cnt += 1
print(cnt)

### FIXED CODE ###

from bisect import bisect_left

n = int(input())
l = sorted(list(map(int, input().split())))

#aを1番短い辺、bを2番めに短い辺とする
cnt = 0
for i in range(n-2):
    for j in range(i+1, n-1):
        c_i = bisect_left(l, l[i] + l[j])
        cnt += c_i - (j+1)

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

n, k = map(int, input().split())
*A, = map(int, input().split())
A = [0] + A
DP = [[None for j in range(100)] for i in range(n + 1)]
for i in range(n + 1):
    DP[i][0] = A[i]
for j in range(1, 100):
    for i in range(n + 1):
        DP[i][j] = DP[DP[i][j - 1]][j - 1]
K = list(bin(k)[2:][::-1])
i = 1
for j, b in enumerate(K):
    if b == '1':
        i = DP[i][j]
print(i)


### FIXED CODE ###

n, k = map(int, input().split())
*A, = map(int, input().split())
# n, k = 6, 727202214173249351
# A = [6, 5, 2, 5, 3, 2]
# n, k = 2, 1
# A = [1, 3]
# n, k = 3, 3
# A = [2, 3, 3]
A = [a - 1 for a in A]
now = 0
V = [False for i in range(n)]
V[0] = 0
L = [now]
cnt = 0
while not V[A[now]]:
    cnt += 1
    now = A[now]
    L.append(now)
    V[now] = cnt
a = V[A[now]]
b = cnt - a + 1
if k < cnt:
    print(L[k] + 1)
    exit()
print(L[(k - a) % b + a] + 1)