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

#!/usr/bin/env python3
import sys
import functools
from math import factorial
from operator import mul

MOD = 10**9 + 7  # type: int

def solve(N: int, K: int):
    def C(n: int, r: int):
        fact1 = functools.reduce(mul, range(n-r+1, n+1), 1)
        fact2 = functools.reduce(mul, range(1, r+1), 1)
        return (fact1 // fact2) % MOD

    for i in range(1, K+1):
        a = C(N-K+1, i)
        b = C(K-1, i-1)
        print((a*b) % MOD)
    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    solve(N, K)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
import functools
from math import factorial
from operator import mul

MOD = 10**9 + 7  # type: int

def solve(N: int, K: int):
    facts = [1] * (N+1)
    for i in range(2, N+1):
        facts[i] = facts[i-1] * (i)

    def C(n: int, r: int):
        upper = facts[n]
        lower = facts[r] * facts[n-r]
        return (upper // lower) % MOD

    for i in range(1, K+1):
        a = C(N-K+1, i)
        b = C(K-1, i-1)
        print((a*b) % MOD)
    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    solve(N, K)

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

import copy

n = int(input())
s = []
for _ in range(n):
    s.append(input())

s2 = copy.copy(s)
i = n
j = 0#何個かぶったか
sum2 = 0
sum1 = 0

for k in range(i):
    for l in range(k,i):
        if s[k] == s[l]:
            
            j += 1
            s2.remove(s[k])
        
    if j == 1:
      j = 0
      s2 = [s[k]] + s2
      sum2 += 1
      sum1 += 1
    else:
      temp = s[k]
      s = [temp]  + copy.copy(s2)
      s2 = copy.copy(s)
      i -= (j-1)
      sum2 += j
      sum1 += 1
      j = 0

    if sum2 == n:
      break
          
#sum1 = len(s)
print(sum1)


### FIXED CODE ###

n = int(input())
s = []
for _ in range(n):
    s.append(input())

s2 = list(set(s))


print(len(s2))
### BUGGY CODE ###

from collections import defaultdict
import sys
input = sys.stdin.readline

N = int(input())
S = [input().rstrip() for _ in range(N)]
S.sort(key=lambda s: -len(s))
dic = [defaultdict(int) for _ in range(26)]
cnt1 = [0] * 26
ans = 0
for s in S:
    if len(s) == 1:
        ans += cnt1[ord(s[0]) - ord('a')]
    else:
        ans += dic[ord(s[0]) - ord('a')][s[1:][::-1]]
    cnt = [0] * 26
    for c in s:
        cnt[ord(c) - ord('a')] += 1
    for c in range(26):
        if cnt[c] > 0:
            cnt1[c] += 1
    t = ''
    for i in range(len(s) - 1, -1, -1):
        t += s[i]
        cnt[ord(s[i]) - ord('a')] -= 1
        for c in range(26):
            if cnt[c] > 0:
                dic[c][t] += 1
print(ans)


### FIXED CODE ###

import sys
input = sys.stdin.readline

base = 1999849216943526259
mod = (1 << 61) - 1

N = int(input())
S = [input().rstrip()[::-1] for _ in range(N)]
S.sort(key=lambda s: -len(s))
cnt = {}
ans = 0
one = [0] * 26
for s in S:
    n = len(s)
    if n == 1:
        ans += one[ord(s[0]) - ord('a')]
        continue
    hashes = [0] * (n - 1)
    hashes[0] = ord(s[0])
    for i in range(1, n - 1):
        hashes[i] = (hashes[i-1] * base + ord(s[i])) % mod
    if hashes[-1] in cnt:
        ans += cnt[hashes[-1]][ord(s[-1]) - ord('a')]
    found = [0] * 26
    found[ord(s[-1]) - ord('a')] = 1
    for i in range(n - 2, 0, -1):
        found[ord(s[i]) - ord('a')] = 1
        if hashes[i-1] not in cnt:
            cnt[hashes[i-1]] = [0] * 26
        for c in range(26):
            cnt[hashes[i-1]][c] += found[c]
    found[ord(s[0]) - ord('a')] = 1
    for c in range(26):
        one[c] += found[c]
print(ans)
### BUGGY CODE ###

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

times = 1
for i in range(K):
    times *= A[i]
# print(times)

for i in range(K , N):
    pre_times = times
    # print(i)
    # print(i)
    # print(A[i - K])
    # print(A[i])
    times = times // A[i - K ]
    times *= A[i]
    # print(times)
    if pre_times < times:
        print("Yes")
    else:
        print("No")

### FIXED CODE ###

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

for i in range(K, N):
    if A[i - K] < A[i]:
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

# -*- coding:utf-8 -*-
import sys


def search(x, y):
    x_length = len(x)
    y_length = len(y)
    memo = [[0] * y_length for i in range(x_length)]
    for i in range(x_length):
        for j in range(y_length):
            if i == 0 or j == 0:
                if x[i] == y[j]:
                    memo[i][j] = 1
                else:
                    memo[i][j] = 0
            elif x[i] == y[j]:
                memo[i][j] = memo[i-1][j-1] + 1
            else:
                memo[i][j] = max(memo[i-1][j], memo[i][j-1])
    return memo[i][j]


if __name__ == "__main__":
    n = int(input())
    strs = [list(val) for val in sys.stdin.read().splitlines()]
    for i in range(n):
        print(search(strs[i*2], strs[i*2+1]))


### FIXED CODE ###

# -*- coding:utf-8 -*-
import sys


def search(x, y):
    x_length = len(x)
    y_length = len(y)
    memo = [[0] * (y_length + 1) for i in range(x_length + 1)]
    for i, ch_x in enumerate(x, 1):
        row = memo[i]
        pre_row = memo[i-1]
        for j, ch_y in enumerate(y, 1):
            if ch_x == ch_y:
                row[j] = pre_row[j-1] + 1
            elif pre_row[j] < row[j-1]:
                row[j] = row[j-1]
            else:
                row[j] = pre_row[j]
    return memo[-1][-1]


if __name__ == "__main__":
    n = int(input())
    strs = [list(val) for val in sys.stdin.read().splitlines()]
    result = [search(strs[i*2], strs[i*2+1]) for i in range(n)]
    print(*result, sep="\n")
### BUGGY CODE ###

n,k = map(int,input().split())
p = list(map(int,input().split()))

e_p = []
for i in range(n):
    e_p.append(0.5*p[i]+0.5)

max = 0
for i in range(n-k+1):
    s=sum(p[i:i+k])
    if s > max:
        max = s
        max_id = i

print(sum(e_p[max_id:max_id+k]))



### FIXED CODE ###

n,k = map(int,input().split())
p = list(map(int,input().split()))

e_p = []
for i in range(n):
    e_p.append(0.5*p[i]+0.5)


ans = []
s = sum(e_p[:k])
ans.append(s)
for i in range(1,n-k+1):
    s -= e_p[i-1]
    s += e_p[i+k-1]
    ans.append(s)
print(max(ans))
### BUGGY CODE ###

S = input().split()

A = abs(int(S[0]) - int(S[1]))
frag = 0
for i in range(A):
  if abs(int(S[0]) - i) == abs(int(S[1]) -i):
    print(i)
    frag = 1
  
if frag == 0:
  print('IMPOSSIBLE')

### FIXED CODE ###

S = input().split()

A = abs(int(S[0]) - int(S[1]))
ans = 0
if A % 2 == 0:
  ans = int(A / 2) 
  if int(S[0]) > int(S[1]):
    print(ans + int(S[1]))
  else:
    print(ans + int(S[0]))
else:
  print('IMPOSSIBLE')
### BUGGY CODE ###

# -*- coding: utf-8 -*-
"""
Created on Sun Feb 24 16:22:35 2019
 
@author: Owner
"""
 
N, K = map(int, input().split())
 
h = list(map(int, input().split()))
 
dp = []
 
for n in range(N):
    if n == 0:
        dp.append(0)
        continue
    temp = float("inf")
    for k in range(1,K+1):
        if n-k < 0:
            break
        temp = min(temp, dp[n-k] + abs(h[n]-h[n-k]))
    dp.append(temp)
#print(dp)
print(dp[N-1])

### FIXED CODE ###

# -*- coding: utf-8 -*-

import numpy as np

N, K = map(int, input().split())
 
h = np.array(list(map(int, input().split())))
 
dp = np.zeros(N)
 
for n in range(1, N):
    k = min(K, n)
    temp = np.min(dp[n-k:n] + np.abs(h[n]-h[n-k:n]))
    dp[n] = temp
print(int(dp[-1]))
### BUGGY CODE ###

import numpy as np
n, a, b = map(int, input().split())


def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n - r] % p


p = 10 ** 9 + 7
fact = [1, 1]
factinv = [1, 1]
inv = [0, 1]

for i in range(2, n + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)

print(2**n%p-cmb(n, a, p)-cmb(n, b, p)-1)

### FIXED CODE ###

k = 2 *10**5
mod = 10**9+7

n, a, b = map(int,input().split())

modinv_table = [-1]*(k+1)
for i in range(1,k+1):
    modinv_table[i] = pow(i,-1,mod)

def binomial_coefficients(n,k):
    ans = 1
    for i in range(k):
        ans *= n-i
        ans *= modinv_table[i+1]
        ans %= mod
    return ans
print((pow(2,n,mod)-binomial_coefficients(n,a)-binomial_coefficients(n,b)-1)%mod)
### BUGGY CODE ###

n, w = [int(e) for e in input().split()]
d = [[int(e) for e in input().split()] for i in range(n)]
t = {}
t[w] = 0
for i in range(n):
  keys = list(sorted(t.keys())) # sort しないと品物iを複数回ナップサックに詰める可能性がある
  tw, tv = d[i]
  for j in keys:
    nw = j - tw
    if nw < 0:
      continue
    nv = t[j] + tv
    if nw in t:
      if nv > t[nw]:
        for k in list(t.keys()):
          if k <= nw and t[k] < nv:
            del t[k]
        t[nw] = nv
    else:
      Flag = False
      for k in t:
        if nw <= k and nv <= t[k]:
          Flag = True
          break
      if Flag:
        continue
      for k in list(t.keys()):
        if k <= nw and t[k] < nv:
          del t[k]
      t[nw] = nv
        
print(max(t.values()))


### FIXED CODE ###

n, w = [int(e) for e in input().split()]
d = [[int(e) for e in input().split()] for i in range(n)]
t = {}
t[w] = 0
for i in range(n):
  keys = list(sorted(t.keys()))
  tw, tv = d[i]
  for j in keys:
    nw = j - tw
    if nw < 0:
      continue
    nv = t[j] + tv
    if nw in t:
      if nv > t[nw]:
        t[nw] = nv
    else:
      t[nw] = nv
print(max(t.values()))
### BUGGY CODE ###

from collections import deque

Height, Width = map(int, input().split())
Map = [input() for _ in range(Height)]
min_step_map = [[10**6]*Width for _ in range(Height)]

# Find the minimum number of steps from all blacks.
# The maximum number of the obtained minimum steps is the answer.
def search_min_step(y_start, x_start):
    compare_step_map = [[0]*Width for _ in range(Height)]
    compare_step_map[y_start][x_start] = 0
    min_step_map[y_start][x_start] = 0

    research_point = deque()
    research_point.append([y_start, x_start])
    while len(research_point) > 0:
        y_now, x_now = research_point.popleft()
        
        for dy, dx in [(-1,0), (0,-1), (1,0), (0,1)]:
            y_next, x_next = y_now+dy, x_now+dx
            if (y_next <= -1 or Height <= y_next) or \
                                              (x_next <= -1 or Width <= x_next):
                continue

            compare_step_map[y_next][x_next] = compare_step_map[y_now][x_now]+1
            if min_step_map[y_next][x_next] <= compare_step_map[y_next][x_next]:
                continue
            else:
                min_step_map[y_next][x_next] = compare_step_map[y_next][x_next]
                research_point.append([y_next, x_next])

for y in range(Height):
    for x in range(Width):
        if Map[y][x] == '#':
            search_min_step(y, x)

max_step = 0
for y in range(Height):
    max_step = max(max_step, max(min_step_map[y]))

print(max_step)

### FIXED CODE ###

from collections import deque

Height, Width = map(int, input().split())
Map = [input() for _ in range(Height)]
min_step_map = [[10**6]*Width for _ in range(Height)]
research_point = deque()

# Find the minimum number of steps from all blacks.
# The maximum number of the obtained minimum steps is the answer.
def search_min_step():
    while len(research_point) > 0:
        y_now, x_now = research_point.popleft()
        
        for dy, dx in [(-1,0), (0,-1), (1,0), (0,1)]:
            y_next, x_next = y_now+dy, x_now+dx
            if (y_next <= -1 or Height <= y_next) or \
                                              (x_next <= -1 or Width <= x_next):
                continue
            
            if Map[y_next][x_next] == '#' or \
                 min_step_map[y_next][x_next] <= min_step_map[y_now][x_now] + 1:
                continue
            else:
                min_step_map[y_next][x_next] = min_step_map[y_now][x_now] + 1
                research_point.append([y_next, x_next])

for y in range(Height):
    for x in range(Width):
        if Map[y][x] == '#':
            min_step_map[y][x] = 0
            research_point.append([y, x])

search_min_step()

max_step = 0
for y in range(Height):
    max_step = max(max_step, max(min_step_map[y]))

print(max_step)
### BUGGY CODE ###

import numpy as np

N, M = map(int, input().split())
A = np.array(list(map(int, input().split())), dtype=np.int64)
A.sort()
BC = [list(map(int, input().split())) for i in range(M)]

for B, C in BC:
    A[0:B][A[0:B] < C] = C
    A.sort()
print(A.sum())


### FIXED CODE ###

N, M = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
BC = [list(map(int, input().split())) for i in range(M)]
BC = sorted(BC, key=lambda x: -x[1])
i = 0
for B, C in BC:
    for _ in range(B):
        if i < N and A[i] < C:
            A[i] = C
            i += 1
        else:
            print(sum(A))
            exit()
print(sum(A))
### BUGGY CODE ###

from collections import deque
import sys
input = sys.stdin.readline

H, W = list(map(int, input().split()))
S = [input() for _ in range(H)]

ans = 0

d = ([0, 1], [0, -1], [1, 0], [-1, 0])


def bfs(x, y):
    m = [[-1] * W for _ in range(H)]

    q = deque()
    q.append([y, x, 0])
    global ans

    while q:
        j, i, v = q.popleft()
        m[j][i] = v
        for dd in d:
            dj = j + dd[0]
            di = i + dd[1]
            if 0 <= dj < H and 0 <= di < W and m[dj][di] == -1 and S[dj][di] == ".":
                q.append([dj, di, v+1])
                if ans < v+1:
                    ans = v+1


for j in range(H):
    for i in range(W):
        if S[j][i] != ".":
            continue
        bfs(i, j)
print(ans)


### FIXED CODE ###

from collections import deque
import sys
input = sys.stdin.readline

H, W = list(map(int, input().split()))
S = ["#" * (W+2)] + ["#" + input().strip() +
                     "#" for _ in range(H)] + ["#" * (W+2)]

ans = 0

for j in range(1, H+1):
    for i in range(1, W+1):
        if S[j][i] != ".":
            continue
        m = [[-1] * (W+2) for _ in range(H+2)]

        q = deque()
        q.append((j, i, 0))
        m[j][i] = 0

        while q:
            y, x, v = q.popleft()
            if ans < v:
                ans = v
            for dj, di in ((y, x+1), (y, x-1), (y+1, x), (y-1, x)):
                if S[dj][di] == "#" or m[dj][di] != -1:
                    continue
                q.append((dj, di, v+1))
                m[dj][di] = v+1
print(ans)
### BUGGY CODE ###

import itertools
from collections import Counter


def main():
    N, M = map(int, input().split())
    LR = []
    for _ in range(M):
        L, R = map(int, input().split())
        LR.append(list(range(L, R + 1)))
    LR = list(itertools.chain.from_iterable(LR))
    C = Counter(LR)

    ans = 0
    for c in C.values():
        if c == M:
            ans += 1
    print(ans)


if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
    N, M = map(int, input().split())
    L = 0
    R = N
    for _ in range(M):
        l, r = map(int, input().split())
        if L < l:
            L = l
        if R > r:
            R = r
    ans = 0
    if L <= R:
        ans = R - L + 1
    print(ans)


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

N = int(input())  # 個数
A = [int(i) for i in input().split()]  # 整数

sum = 0
for i in range(N-1):
    sum_j = 0
    for j in range(i+1, N):
        sum_j += A[j]
    sum += A[i] * sum_j

print(sum % 1000000007)


### FIXED CODE ###

N = int(input())  # 個数
A = [int(i) for i in input().split()]  # 整数

sum_Aij = 0
sum_j = [0] * (N - 1)
for i in range(N - 1, 0, -1):
    sum_j[i - 1] = (A[i] + (0 if i == N - 1 else sum_j[i])) % 1000000007
    sum_Aij += sum_j[i - 1] * A[i - 1] % 1000000007

print(sum_Aij % 1000000007)
### BUGGY CODE ###

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

def f(i):
    total = 0
    for j in range(N):
        total += A[(i + j) % N] * (1 if j % 2 == 0 else -1)
    return str(total)

B = [f(i) for i in range(N)]

print(*B)

# A[0] = B[0] // 2 + B[1] // 2
# A[1] = B[1] // 2 + B[2] // 2
# A[2] = B[2] // 2 + B[0] // 2

# 2 * A[0] = B[0] + B[1]
# 2 * A[1] = B[1] + B[2]
# 2 * A[2] = B[2] + B[0]

# 2 * A[2] - 2 * A[1] = B[0] - B[1]
# 2 * A[0] - 2 * A[2] = B[1] - B[2]
# 2 * A[1] - 2 * A[0] = B[0] - B[2]

# A[0] - A[2] + A[1] = B[1]

# B[i] = A[i] + A[i - 1] - A[i + 1]

# A[0] = B[0] // 2 + B[1] // 2
# A[1] = B[1] // 2 + B[2] // 2
# A[2] = B[2] // 2 + B[3] // 2
# A[3] = B[3] // 2 + B[4] // 2
# A[4] = B[4] // 2 + B[0] // 2

# A[0] - A[1] = B[0] - B[2]
# A[1] - A[2] = B[1] - B[3]
# A[2] - A[3] = B[2] - B[4]
# A[3] - A[4] = B[3] - B[0]
# A[4] - A[0] - B[4] - B[1]

# A[0] - A[1] + A[2] - A[3] + A[4] = B[0]
# A[1] - A[2] + A[3] - A[4] + A[0] = B[1]
# A[2] - A[3] + A[4] - A[0] + A[1] = B[2]
# A[3] - A[4] + A[0] - A[1] + A[2] = B[3]


### FIXED CODE ###

from functools import lru_cache
N = int(input())
A = list(map(int, input().split()))

@lru_cache(maxsize=N)
def f(i):
    if i >= 2:
        return f(i - 2) + 2 * A[i - 1] - 2 * A[i - 2]
    total = 0
    for j in range(N):
        if j % 2 == 0:
            total += A[(i + j) % N]
        else:
            total -= A[(i + j) % N]
    return total

B = (f(i) for i in range(N))

print(*B)
### BUGGY CODE ###

n,k = map(int,input().split())
flg = True

while flg:
    tmp = abs(n-k)
    n = tmp
    tmp2 = abs(n-k)
    if tmp2 > tmp:
        flg = False
    
print(tmp)

### FIXED CODE ###

n,k = map(int,input().split())

t = n % k
print(min(t,k-t))
### BUGGY CODE ###

N=int(input())
S=input()
cnt=[]
for i in range(N):
    count=0
    for j in range(N):
        if j<i and S[j]=='W':
            count+=1
        elif j>i and S[j]=='E':
            count+=1
    cnt.append(count)
print(min(cnt))


### FIXED CODE ###

N=int(input())
S=input()
num=S[1:].count('E')
ans=num
for i in range(1,N):
    if S[i-1]=='W':
        num+=1
    if S[i]=='E':
        num-=1
    ans=min(num,ans)
print(ans)
### BUGGY CODE ###

N,W = map(int,input().split())
dp = [[0 for i in range(W+1)] for j in range(N+1)]
for i in range(1,N+1):
    w,v = map(int,input().split())
    for j in range(W+1):
        if j < w:
            dp[i][j] = dp[i-1][j]
        else:
            dp[i][j] = max(dp[i-1][j],dp[i-1][j-w]+v)
print(dp[N][W])

### FIXED CODE ###

N,W = map(int,input().split())
dp = [[0 for i in range(W+1)] for j in range(N+1)]
for i in range(1,N+1):
    w,v = map(int,input().split())
    for j in range(W+1):
        if j < w:
            dp[i][j] = dp[i-1][j]
        else:
            dp[i][j] = max(dp[i-1][j],dp[i-1][j-w]+v)
print(dp[N][W])
### BUGGY CODE ###

import sys
sys.setrecursionlimit(100000)

def ins(): return input().split()
def ii(): return int(input())
def iil(): return list(map(int,ins()))
def lin(): return list(input())
def iin(): return map(int,ins())

class heapx:
    def __init__(self, array):
        self.array = array[:]
        self.heapify()

    def _down_value(self, index):
        try:
            return self.array[2*index+1],self.array[2*index+2]
        except:
            try:
                return self.array[2*index+1],float('inf')
            except:
                return float('inf'),float('inf')

    def _up_value(self, index):
        return self.array[(index-1)//2] if index>0 else -float('inf')

    def _shift(self, i1, i2):
        self.array[i1],self.array[i2]=self.array[i2],self.array[i1]

    def _down_heap(self, index):
        if index > self.leng()-1:
            return False
        i = self.array[index]
        j,k = self._down_value(index)
        if i<j and i<k:
            return
        else:
            if j<k:
                self._shift(index,2*index+1)
                self._down_heap(2*index+1)
            else:
                self._shift(index,2*index+2)
                self._down_heap(2 * index + 2)

    def heapify(self):
        for i in range(-len(self.array)//2-1,1):
            self._down_heap(-i)

    def pop(self):
        self._shift(0,-1)
        tmp = self.array.pop()
        if self.leng() > 0:
            self._down_heap(0)
        return tmp

    def leng(self):
        return len(self.array)

    def _up_heap(self, index):
        i = self.array[index]
        j = self._up_value(index)
        if i<j:
            self._shift(index,(index-1)//2)
            self._up_heap((index-1)//2)

    def push(self, item):
        self.array.append(item)
        self._up_heap(self.leng()-1)

    def poppush(self, item):
        tmp, self.array[0] = self.array[0], item
        self._down_heap(0)
        return tmp

    def pushpop(self, item):
        self.push(item)
        return self.pop()

#t = [5645425,5631,14536,5632,564,151635,563,561415,14563,3131]
#heap = heapx(t)
import math
n,m=iin()
a=heapx(list(map(lambda x:-int(x),ins())))
tmp = a.pop()
for i in range(m):
    tmp = a.pushpop(math.ceil(tmp/2))
print(-(sum(a.array)+tmp))

### FIXED CODE ###

import sys,heapq,math
sys.setrecursionlimit(100000)

def ins(): return input().split()
def ii(): return int(input())
def iil(): return list(map(int,ins()))
def lin(): return list(input())
def iin(): return map(int,ins())

n,m=iin()
a=list(map(lambda x:-int(x),ins()))
heapq.heapify(a)
tmp = heapq.heappop(a)
for i in range(m):
    tmp = heapq.heappushpop(a,math.ceil(tmp/2))
print(-(sum(a)+tmp))
### BUGGY CODE ###

import sys
input = sys.stdin.readline

from heapq import heappush, heappop

INF = float('inf')

# 単一始点最短経路を求める（Dijkstra法）
def Dijkstra(adjList, vSt, vEn):
    numV = len(adjList)
    numUsed = 0
    costs = [INF] * numV
    costs[vSt] = 0
    PQ = []
    heappush(PQ, (0, vSt))
    while PQ:
        cNow, vNow = heappop(PQ)
        if vNow == vEn: break
        if cNow > costs[vNow]: continue
        numUsed += 1
        if numUsed == numV: break
        for v2, wt in adjList[vNow]:
            c2 = cNow + wt
            if c2 < costs[v2]:
                costs[v2] = c2
                heappush(PQ, (c2, v2))
    return costs


N, M = map(int, input().split())
edges = []
v0s = [[] for _ in range(N)]
v2s = [[] for _ in range(N)]
for _ in range(M):
    u, v = map(int, input().split())
    u, v = u-1, v-1
    edges.append((u, v))
    v0s[v].append(u)
    v2s[u].append(v)

S, T = map(int, input().split())
S, T = S-1, T-1

adjL = [[] for _ in range(N)]
for u, v in edges:
    for v0 in v0s[u]:
        for v2 in v2s[v]:
            adjL[v0].append((v2, 1))

costs = Dijkstra(adjL, S, T)

if costs[T] == INF:
    print(-1)
else:
    print(costs[T])


### FIXED CODE ###

from collections import deque
import sys
input = sys.stdin.readline

INF = float('inf')

def bfsMinCosts(adjList, vSt):
    numV = len(adjList)
    costs = [INF] * numV
    costs[vSt] = 0
    Q = deque([vSt])
    while Q:
        vNow = Q.popleft()
        cNow = costs[vNow]
        for v2 in adjList[vNow]:
            if costs[v2] == INF:
                costs[v2] = cNow + 1
                Q.append(v2)
    return costs

N, M = map(int, input().split())
adjL = [[] for _ in range(3*N)]
for _ in range(M):
    u, v = map(int, input().split())
    u, v = u-1, v-1
    adjL[3*u+0].append(3*v+1)
    adjL[3*u+1].append(3*v+2)
    adjL[3*u+2].append(3*v+0)

S, T = map(int, input().split())
S, T = S-1, T-1

costs = bfsMinCosts(adjL, 3*S+0)

if costs[3*T+0] == INF:
    print(-1)
else:
    print(costs[3*T+0]//3)