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

#!/usr/bin/env python3
# vim: set fileencoding=utf-8

# pylint: disable=unused-import, invalid-name, missing-docstring, bad-continuation


"""Module docstring
"""

import sys


def solve(s, t):
    v = [0] * (len(s) + 1)
    dp = [v]
    for ti in t:
        u, v = v, v.copy()
        dp.append(v)
        ll, ul = 0, 0
        for j, sj in enumerate(s):
            uj = u[j + 1]
            if sj == ti:
                v[j + 1] = 1 + ul
                ll = 1 + ul
            else:
                if ll > uj:
                    v[j + 1] = ll
                else:
                    ll = uj
            ul = uj
    i = len(t)
    j = len(s)
    k = dp[i][j]
    selected = []
    while k > 0:
        if t[i - 1] == s[j - 1]:
            selected.append(t[i - 1])
            k -= 1
            i -= 1
            j -= 1
        elif dp[i - 1][j] > dp[i][j - 1]:
            i -= 1
        else:
            j -= 1
    return "".join(selected[::-1])


def do_job():
    "Do the work"
    s = input()
    t = input()
    result = solve(s, t)
    print(result)


def print_output(testcase, result) -> None:
    "Formats and print result"
    if result is None:
        result = "IMPOSSIBLE"
    print("Case #{}: {}".format(testcase + 1, result))


def main(argv=None):
    "Program wrapper."
    if argv is None:
        argv = sys.argv[1:]
    do_job()
    return 0


if __name__ == "__main__":
    import doctest

    doctest.testmod()
    sys.exit(main())


### FIXED CODE ###

#!/usr/bin/env python3
# vim: set fileencoding=utf-8

# pylint: disable=unused-import, invalid-name, missing-docstring, bad-continuation


"""Module docstring
"""

import sys


def solve(s, t):
    v = [0] * (len(s) + 1)
    dp = [v]
    for _, ti in enumerate(t, 1):
        u, v = v, v.copy()
        dp.append(v)
        ll, ul = 0, 0
        for j, sj in enumerate(s, 1):
            uj = u[j]
            if sj == ti:
                v[j] = 1 + ul
                ll = 1 + ul
            else:
                if ll > uj:
                    v[j] = ll
                else:
                    ll = uj
            ul = uj
    i = len(t)
    j = len(s)
    k = dp[i][j]
    selected = []
    while k > 0:
        if dp[i - 1][j] == k:
            i -= 1
        elif dp[i][j - 1] == k:
            j -= 1
        else:
            selected.append(t[i - 1])
            k -= 1
            i -= 1
            j -= 1
    return "".join(selected[::-1])


def do_job():
    "Do the work"
    s = input()
    t = input()
    result = solve(s, t)
    print(result)


def print_output(testcase, result) -> None:
    "Formats and print result"
    if result is None:
        result = "IMPOSSIBLE"
    print("Case #{}: {}".format(testcase + 1, result))


def main(argv=None):
    "Program wrapper."
    if argv is None:
        argv = sys.argv[1:]
    do_job()
    return 0


if __name__ == "__main__":
    import doctest

    doctest.testmod()
    sys.exit(main())
### BUGGY CODE ###

N, M = list(map(int, input().split()))
sigma = list(map(int, input().split()))
gokans = []

for i in range(M):
    pair = list(map(int, input().split()))
    gokans.append(pair)

def connected(i, j, paths):
    if [pair for pair in paths if i in pair] and [pair for pair in paths if j in pair]:
        i_start = [pair for pair in paths if i in pair]
        chain = i_start
        old_chain = []
        for pair in chain:
            paths.remove(pair)

        while chain != old_chain:
            old_chain = chain
            for pair in chain:
                new_chain = [couple for couple in paths if set(couple) & set(pair) != set()]
                chain += new_chain
                for pair in new_chain:
                    paths.remove(pair)
            narabi = [couple[0] for couple in chain] + [couple[1] for couple in chain]
            if j in narabi:
                return True
        return False
    else:
        return False

table1 = [[] for _ in range(N)]
for i in range(1, N+1):
    for j in range(i+1, N+1):
        gokans1 = gokans.copy()
        if connected(i, j, gokans1):
            table1[i-1].append(j)

count = 0
for i in range(1, N+1):
    if i < sigma[i-1]:
        if sigma[i-1] in table1[i-1]:
            count += 1
    elif i > sigma[i-1]:
        if i in table1[sigma[i-1]-1]:
            count += 1
    else:
        count += 1

print(count)

### FIXED CODE ###

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

par = [i for i in range(n)]
#rootの計算量は、parが最初の状態に近いほど値は小さくて、高々O(n)
def root(x):
	tmp = par[x]
	if tmp == x:
		return x
	else:
		a = root(tmp)
		par[x] = a
		return a

def merge(x, y):
	x = root(x)
	y = root(y)
	if x != y:
		par[x] = y
		return

for i in range(m):
	x, y = map(int, input().split())
	merge(x-1, y-1)
	#print(par)

ans = 0

for i in range(n):
	if p[i]-1 == i:
		ans += 1
	elif root(p[i]-1) == root(i):
		ans += 1
print(ans)
### BUGGY CODE ###

S = input()
N = len(S)
l = [0]*2019
l[0] = 1
n = 0
out = 0
for i in range(N-1, -1, -1):
    n += int(S[i]) * (10**(N-1 - i))
    r = n % 2019
    l[r] += 1
for m in l:
    out += (m*(m-1))//2 
print(out)

### FIXED CODE ###

S = input()[::-1]
N = len(S)
l = [0]*2019
l[0] = 1
n = 0
d = 1

for i in range(N):
    n += int(S[i]) * d
    r = n % 2019
    l[r] += 1
    d = 10*d % 2019
    
out = 0    
for m in l:
    out += (m*(m-1))//2 
print(out)
### 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()}

N=int(input())
A=list(map(int,input().split()))
Q=int(input())
List=[i for i in range(10**5+1)]
Uf=UnionFind(10**5+1)
for i in range(Q):
    B,C=map(int,input().split())
    List[B]=C
    Uf.union(B,C)
    for i in Uf.members(B):
        index=i
        while index!=List[index]:
            index=List[index]
            if index==i:
                break
            # print(index)
            # print(List)
        List[i]=index
    ChangedA=[List[a] for a in A]
    print(sum(ChangedA))

### FIXED CODE ###

import numpy as np
N=int(input())
A=list(map(int,input().split()))
SUM=sum(A)
Q=int(input())
List=np.array([0 for _ in range(10**5+1)])
for a in A:
    List[a]+=1
for q in range(Q):
    B,C=map(int,input().split())
    SUM-=B*List[B]
    SUM+=C*List[B]
    List[C]+=List[B]
    List[B]=0
    print(SUM)
### BUGGY CODE ###

from collections import deque

H, W = map(int, input().split())
G = [[i for i in input()] for j in range(H)]

dp = [[-1 for i in range(W)] for j in range(H)]
dir = [[1,0], [-1,0], [0,1], [0,-1]]
for h in range(H):
    for w in range(W):
        if G[h][w] == "#":
            dp[h][w] = 0
            data = deque([[h,w]])
            while len(data) > 0:
                i, j = data.popleft()

                for dx, dy in dir:
                    if i+dx < 0 or H-1 < i+dx or j+dy < 0 or W-1 < j+dy:
                        continue
                    if G[i+dx][j+dy] == "#":
                        continue
                    if dp[i+dx][j+dy] != -1 and dp[i+dx][j+dy] < dp[i][j] + 1:
                        continue
                    dp[i+dx][j+dy] = dp[i][j] + 1
                    data.append([i+dx,j+dy])

ans = 0
for i in range(H):
    for j in range(W):
        ans = max(ans, dp[i][j])

print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline

H, W = map(int, input().split())
G = [[i for i in input()] for j in range(H)]

ls = []
dp = [[-1 for i in range(W)] for j in range(H)]
for h in range(H):
    for w in range(W):
        if G[h][w] == "#":
            ls.append([h,w])
            dp[h][w] = 1

ans = -1
while len(ls) > 0:
    ans += 1
    temp = []
    for h, w in ls:
        if 0 <= h+1 <= H-1 and dp[h+1][w] == -1:
            dp[h+1][w] = 1
            temp.append([h+1,w])
        if 0 <= h-1 <= H-1 and dp[h-1][w] == -1:
            dp[h-1][w] = 1
            temp.append([h-1,w])
        if 0 <= w+1 <= W-1 and dp[h][w+1] == -1:
            dp[h][w+1] = 1
            temp.append([h,w+1])
        if 0 <= w-1 <= W-1 and dp[h][w-1] == -1:
            dp[h][w-1] = 1
            temp.append([h,w-1])
    ls = temp

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

n=int(input())
s=input()
b=''
c=[]
d=[]
cnt=0
for i in range(n):
  if s[i] in b:continue
  b+=s[i]
  for j in range(i+1,n):
    if s[i]+s[j] in c:continue
    c+=s[i]+s[j]
    for k in range(j+1,n):
      if s[i]+s[j]+s[k] not in d:
        cnt+=1
        d.append(s[i]+s[j]+s[k])
print(cnt)

### FIXED CODE ###

n=int(input())
s=input()
cnt=0
for m in range(1000):
  m=str(m).zfill(3)
  j=0
  for i in m:
    if i not in s[j:]:break
    j+=s[j:].index(i)+1
  else:cnt+=1
print(cnt)
### BUGGY CODE ###

a,b,c,k=map(int,input().split())
if k<=a+b:
    print(a)
for i in range(1,c):
    if k==a+b+i:
        print(a-i)

### FIXED CODE ###

a,b,c,k=map(int,input().split())
 
def calc(a,b,c,k):
    if k<a:
        return k
    elif k<=a+b:
      return a
    else:
        return a-(k-a-b)
print(calc(a,b,c,k))
### BUGGY CODE ###

MOD = 10**9 + 7
memo = None


def rec(S, k, total):
    if k == len(S)//3:
        # print(total)
        fixed_total = total + 5 if k % 2 == 0 else total - 5
        # fixed_total = abs(total) + 5
        memo[k][total % 13] = int((fixed_total) % 13 == 0)
        return int((fixed_total) % 13 == 0)

    if memo[k][total % 13] is not None:
        return memo[k][total % 13]

    s = S[k*3:k*3+3]
    d1 = [str(i) for i in range(10)] if s[0] == '?' else [s[0]]
    d2 = [str(i) for i in range(10)] if s[1] == '?' else [s[1]]
    d3 = [str(i) for i in range(10)] if s[2] == '?' else [s[2]]
    ret = 0

    for i1 in d1:
        for i2 in d2:
            for i3 in d3:
                num = int(i1 + i2 + i3)
                if k % 2 == 0:
                    ret += rec(S, k+1, total + num)
                else:
                    ret += rec(S, k+1, total - num)

    memo[k][total % 13] = ret
    return ret

S = input()

# if len(S) % 3 == 1:
#     S = '00' + S
# elif len(S) % 3 == 2:
#     S = '0' + S

# L = (len(S) // 3)
# dp = [[0 for i in range(14)] for j in range(L + 1)]
# # print(rec(S, 0, 0) % MOD)
# # print(memo)

# dp[0][0] = 1

# for k in range(L):
#     for m in range(13):
#         s = S[k*3:k*3+3]
#         d1 = [str(i) for i in range(10)] if s[0] == '?' else [s[0]]
#         d2 = [str(i) for i in range(10)] if s[1] == '?' else [s[1]]
#         d3 = [str(i) for i in range(10)] if s[2] == '?' else [s[2]]

#         for i1 in d1:
#             for i2 in d2:
#                 for i3 in d3:
#                     num = int(i1 + i2 + i3)
#                     dp[k + 1][(13 + num - m) % 13] += dp[k][m]

#         for i in range(13):
#             dp[k][m] %= MOD

# print(dp[L][5] % MOD)

L = len(S)
memo = [[0 for i in range(14)] for j in range(L + 1)]
dp = [[0 for i in range(14)] for j in range(L + 1)]
# print(rec(S, 0, 0) % MOD)
# print(memo)

dp[0][0] = 1

for k in range(L):
    for m in range(13):
        if S[k] == '?':
            for i in range(10):
                dp[k + 1][(m * 10 + i) % 13] += dp[k][m]
        else:
            dp[k + 1][(m * 10 + int(S[k])) % 13] += dp[k][m]

print(dp[L][5] % MOD)


### FIXED CODE ###

MOD = 10**9 + 7

S = input()
L = len(S)
memo = [[0 for i in range(14)] for j in range(L + 1)]
dp = [[0 for i in range(14)] for j in range(L + 1)]

dp[0][0] = 1

for k in range(L):
    for m in range(13):
        if S[k] == '?':
            for i in range(10):
                dp[k + 1][(m * 10 + i) % 13] += dp[k][m]
        else:
            dp[k + 1][(m * 10 + int(S[k])) % 13] += dp[k][m]

        for i in range(13):
            dp[k+1][i] %= MOD

print(dp[L][5])
### BUGGY CODE ###

n = int(input())
s = [int(input()) for i in range(n)]

ans = 0
for i in range(2 ** n):
    switch = [0] * n
    for j in range(n):
        if((i >> j) & 1):
            switch[j] = 1
    
    sub = 0
    for k in range(n):
        if switch[k] == 1:
            sub += s[k]
    if sub % 10 != 0:
        ans = max(ans, sub)

print(ans)

### FIXED CODE ###

n = int(input())
s = [int(input()) for i in range(n)]

ans = 0
sub = sum(s)
if sub % 10 != 0:
    print(sub)
else:
    l = []
    for i in range(n):
        if s[i] % 10 != 0:
            l.append(s[i])
    l.sort()
    for j in l:
        sub -= j
        if sub % 10 != 0:
            break
    
    if sub % 10 == 0:
        print("0")
    else:
        print(sub)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**7)
n, q = map(int, input().split(' '))
inf = [[] for _ in range(n)]
ab = [[x for x in map(int, input().split(' '))] for _ in range(n-1)]
for a,b in ab:
    inf[a-1].append(b-1)
    inf[b-1].append(a-1)
point = [0 for _ in range(n)]
px = [[x for x in map(int, input().split(' '))] for _ in range(q)]
for p,x in px:
    point[p-1] += x
def add_p(num, oya):
    for k in inf[num]:
        if k != oya:
            point[k] += point[num]
            add_p(k, num)  
for i in inf[0]:
    point[i] += point[0]
    add_p(i,0)
print(*point)

### FIXED CODE ###

def main():
    n, q = map(int, input().split(' '))
    import sys
    from collections import deque
    sys.setrecursionlimit(10**7)

    visit = [True for _ in range(n)]
    point = [0 for _ in range(n)]
    dic = [[] for _ in range(n)]
    for _ in range(n-1):
        a, b = map(int, input().split(' '))
        dic[a-1].append(b-1)
        dic[b-1].append(a-1)
    for _ in range(q):
        p, x = map(int, input().split(' '))
        point[p-1] += x
    next_visit = deque()
    next_visit.append(0)
    visit[0] = False
    counter = 1
    while counter < n:
        t = next_visit.pop()
        for s in dic[t]:
            if visit[s]:
                point[s] += point[t]
                visit[s] = False
                counter += 1
                next_visit.append(s)
    print(*point)
if __name__ == '__main__':
    main()
### BUGGY CODE ###

n,m=map(int,input().split())
A=[int(input()) for _ in range(m)]
mod=10**9+7

dp=[0]*(n+1)
dp[0]=1
if 1 not in A:
   dp[1]=1

for i in range(2,n+1):
   if i not in A:
      dp[i]=dp[i-1]+dp[i-2]
print(dp[-1]%mod)

### FIXED CODE ###

n,m=map(int,input().split())
A=[int(input()) for i in range(m)]

ai=0
n1,n2=0,1
for i in range(1,n+1):
      if ai<m and i==A[ai]:
            ai+=1
            n1=n2
            n2=0
      else:
            tmp=n2
            n2=(n1+n2)%1000000007
            n1=tmp
print(n2)
### BUGGY CODE ###

import sys
n,k = map(int,input().split())
ls = list(map(int,input().split()))
def sub(k,s):
    return k-s
p = [1]
i = 0
a = 0
t = 0
ans1 = 0
ans2 = 0
e = 3
while i<k-1:
    if i ==0:
        a = ls[i]
        p.append(a)
        if len(p) != len(list(set(p))):
            q = [p[-1]]*(len(p))
            p.pop()
            new = list(map(sub,p,q))
            t = new.index(0)
            ans1 = len(p[:t])
            ans2 = len(p[t:])
            print(p[((k+1-ans1)%ans2)-1])
            sys.exit()
        b = ls[a-1]
        p.append(b)
        if len(p) != len(list(set(p))):
            q = [p[-1]]*(len(p))
            p.pop()
            new = list(map(sub,p,q))
            t = new.index(0)
            ans1 = len(p[:t])
            ans2 = len(p[t:])
            print(p[((k+1-ans1)%ans2)-1])
            sys.exit()
        i += 1
    else:
        a = b
        b = ls[a-1]
        p.append(b)
        e += 1
        f = len(list(set(p)))
        if e != f:
            q = [p[-1]]*(e)
            p.pop()
            new = list(map(sub,p,q))
            t = new.index(0)
            ans1 = len(p[:t])
            ans2 = e-1 - ans1
            ansl = p[t:]
            print(ansl[((k+1-ans1)%ans2)-1])
            sys.exit()
        i += 1
print(b)




### FIXED CODE ###

n,k = map(int,input().split())
ls = list(map(int,input().split()))
fi = [-1]*(n+1)
fi[1] = 0
a = 0
aa = 0
for i in range(k):
    if fi[ls[a]] == -1:
        fi[ls[a]] = i + 1
        aa = a
        a = ls[a] - 1
    else:
        ind = fi[ls[a]]
        t = (k - ind) % (max(fi) + 1 - ind)
        t += ind
        print(fi.index(t))
        break
else:
    print(ls[aa])
### BUGGY CODE ###

def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]
  
a=int(input())
ans=0
for i in range(1,a+1):
  ans=ans+i*len(make_divisors(i))
print(ans)


### FIXED CODE ###

n=int(input())
ans=0

for i in range(1,n+1):
  k=n//i
  ans=ans+i*k*(k+1)//2

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

from collections import deque

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

dxdy = [(-1,0), (1,0), (0,-1), (0,1)]
INF = 999999
que = deque()

dist = [[INF] * W for _ in range(H)]
for i in range(H):
    for j in range(W):
        if grid[i][j] == "#":
            dist[i][j] = 0
            que.append((i,j))

ans = 0
while len(que) > 0:
    h, w = que.popleft()
    for dx, dy in dxdy:
        nx = w + dx
        ny = h + dy
        if ny<0 or ny>=H or nx<0 or nx>=W or dist[ny][nx] < INF:
            continue
        dist[ny][nx] = min(dist[ny][nx], dist[h][w]+1)
        ans = max(ans, dist[ny][nx])
        que.append((ny,nx))

print(ans)

### FIXED CODE ###

from collections import deque

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

dxdy = [(-1,0), (1,0), (0,-1), (0,1)]
INF = 999999
que = deque()

dist = [[INF] * W for _ in range(H)]
for i, row in enumerate(grid):
    for j, s in enumerate(row):
        if s == "#":
            dist[i][j] = 0
            que.append(i*W + j)

ans = 0
while len(que) > 0:
    num = que.popleft()
    h = num // W
    w = num % W
    for dx, dy in dxdy:
        nx = w + dx
        ny = h + dy
        if ny<0 or ny>=H or nx<0 or nx>=W:
            continue
        if dist[ny][nx] == INF:
            que.append(ny * W + nx)
        dist[ny][nx] = min(dist[ny][nx], dist[h][w]+1)
        ans = max(ans, dist[ny][nx])

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

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

rgb = 'RGB'
ans = 0
for i in range(0, n-2):
    for j in range(i+1,n-1):
        if s[i] == s[j]: continue
        k = rgb[:rgb.find(s[i])] + rgb[rgb.find(s[i])+1:]
        k = k[:k.find(s[j])] + k[k.find(s[j])+1:]
        r = s[j+1:2*j-i] + s[2*j-i+1:]
        ans += r.count(k)
print(ans)

### FIXED CODE ###

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

r = s.count('R')
g = s.count('G')
b = s.count('B')

count = 0
#count second conditions satisfied
for i in range(n):
    for j in range(i+1,n):
        #search j - i = k - j ⇔ k = 2 * j - i
        k = 2 * j - i
        if k >= n: break
        if s[i] != s[j] and s[j] != s[k] and s[i] != s[k]: count += 1
print((r * g * b) - count)
### BUGGY CODE ###

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

from itertools import combinations
ans=set()
for i in combinations(s,3):
    ss="".join(i)
    ans.add(ss)
print(len(ans))

### FIXED CODE ###

def main():
    n=int(input())
    s=input()
    ans=0
    f00=[False if str(i) in set(str(s)) else True for i in range(10)]
    f0=f00.copy()
    for i0 in range(n-2):
        if all(f0):
            break
        if not f0[int(s[i0])]:
            f1=f00.copy()
            for i1 in range(i0+1,n-1):
                if all(f1):
                    break
                if not f1[int(s[i1])]:
                    ans+=len( set( s[i1+1:] ) )
                    f1[int(s[i1])]=True
        f0[int(s[i0])]=True
    print(ans)
if __name__ == '__main__':
    main()
### BUGGY CODE ###

import sys
from collections import Counter
import copy
n = int(sys.stdin.readline())
battle_dict = dict()
cur_stage = Counter([])
new_ls = []
for i in range(n):
    inp = [int(i) for i in sys.stdin.readline().split()]
    battle_dict[i+1] = inp
    new_ls.append(tuple(sorted([i+1, inp[0]])))
cur_stage.update(new_ls)

cnt = 0
while True:
    new_cur_stage = copy.deepcopy(cur_stage)
    new_ls = []
    flg = 0
    for v, c in cur_stage.items():
        if c > 1:
            i, j = v
            if len(battle_dict[i]) > 0:
                battle_dict[i].pop(0)
            if len(battle_dict[j]) > 0:
                battle_dict[j].pop(0)
            cur_stage[v] = 0
            new_cur_stage.pop(v)
            if len(battle_dict[i]) > 0:
                new_ls.append(tuple(sorted([i, battle_dict[i][0]])))
            if len(battle_dict[j]) > 0:
                new_ls.append(tuple(sorted([j, battle_dict[j][0]])))
            flg = 1
    if flg == 0:
        break
    else:
        cnt += 1
    new_cur_stage.update(new_ls)
    cur_stage = copy.deepcopy(new_cur_stage)
    """
    cur_stage.clear()
    new_ls = []
    for i, j in battle_dict.items():
        if len(j) > 0:
            new_ls.append(tuple(sorted([i, j[0]])))
    cur_stage.update(new_ls)
    """
if len(cur_stage) > 0:
    print(-1)
else:
    print(cnt)

### FIXED CODE ###

import sys
from collections import Counter
import copy

n = int(sys.stdin.readline())
ct = Counter()
a_ls = dict()
for i in range(n):
    inp = [int(i) - 1 for i in sys.stdin.readline().split()]
    a_ls[i] = inp
cnt = 0
candidate = list(range(n))
rest = n * (n - 1) / 2
combis = set()
while rest:
    no_ls = []
    next_candidate = []
    flg = False
    for i in candidate:
        if len(a_ls[i]) == 0:
            continue
        target = a_ls[i][0]
        if (i, target) in combis or (target, i) in combis:
            next_candidate.append(i)
            next_candidate.append(target)
            rest -= 1
            if len(a_ls[i]) > 0:
                a_ls[i].pop(0)
            if len(a_ls[target]) > 0:
                a_ls[target].pop(0)
            flg = True
        else:
            combis.add((i, target))
    candidate = next_candidate
    if not flg:
        cnt = -1
        break
    cnt += 1
print(cnt)
### BUGGY CODE ###

import re
S = input()
N1 = S.replace('A','0').replace('BC','1')
S_li = re.split('B|C',N1)

count = 0
for l in S_li:
    a = l.find('0')
    bc = l.rfind('1')
    if 0 <= a < bc:
        count += (bc-a)
        while True:
            i = a+1
            a = l[:bc].find('0',i)
            bc = l[:bc].rfind('1',i)
            if 0 <= a < bc:
                count += (bc-a)
            else:
                break
print(str(count))

### FIXED CODE ###

import re
S = input()
N1 = S.replace('A','0').replace('BC','1')
S_li = re.split('B|C',N1)
 
count = 0
for l in S_li:
    a = sum([i for i,x in enumerate(l) if '1' in x])
    su=sum([x for x in range(l.count('1'))])
    count += (a-su)
print(str(count))
### BUGGY CODE ###

import numpy as np
N, M = map(int, input().split())
As = list(map(int, input().split()))

mvals = list(np.array(As) * (-1))
import heapq
heapq.heapify(mvals)

for _ in range(M):
    price = heapq.heappop(mvals)
    heapq.heappush(mvals, price / 2)

res = (np.array(mvals) * (-1)).astype(int).sum()
print(res)

### FIXED CODE ###

N, M = map(int, input().split())
mvals = list(map(lambda x: -int(x), input().split()))

import heapq
heapq.heapify(mvals)

for _ in range(M):
    price = heapq.heappop(mvals)
    heapq.heappush(mvals, price / 2)

res = sum(map(lambda x:int(-x), mvals))
print(res)