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

from functools import lru_cache
 
def sub():
    import sys
    sys.setrecursionlimit(10000)

    N, M = [int(e) for e in input().split()]
    
    class ListDict(dict):
        def __missing__(self, key):
            self[key] = []
            return self[key]
 
    d_edge = ListDict()
    for _ in range(M):
        h, t = [int(e) for e in input().split()]
        d_edge[h].append(t)
 
    # for k, v in d_edge.items():
    #     print(k,v)
    
    @lru_cache(maxsize=None)
    def dp(a_head):
        tails = d_edge[a_head]
        if len(tails) == 0:
            return 0
        tmps = [dp(t) for t in tails]
        return max(tmps) + 1
    
    heads = list(d_edge.keys())
    rr = [dp(h) for h in heads]
    print(max(rr))
 
 
if __name__ == "__main__":
    sub()


### FIXED CODE ###

from collections import defaultdict, deque
def sub():

    N, M = [int(e) for e in input().split()]
    es = [[int(x) for x in input().split()] for _ in range(M)]

    outs = defaultdict(list)
    ins = defaultdict(int)
    for v1, v2 in es:
        outs[v1].append(v2)
        ins[v2] += 1

    q = deque(v1 for v1 in range(1, N+1) if ins[v1] == 0)
    dp_table = [0 for i in range(N+1)]
    res = []
    while q:
        v1 = q.popleft()
        res.append(v1)
        for v2 in outs[v1]:
            ins[v2] -= 1
            if ins[v2] == 0:
                q.append(v2)
                dp_table[v2] = max(dp_table[v2], dp_table[v1] + 1)
    print(max(dp_table))

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

N,Q = map(int,input().split())
c = list(map(int,input().split()))
q = list(list(map(int,input().split()))+[i] for i in range(Q))

BIT = [0]*N

def add(ind,value):
    while ind <= N:
        BIT[ind-1] += value
        ind += ind & -ind
def sum(x):
    out = 0
    while x > 0:
        out += BIT[x-1]
        x -= x & -x
    return out

rbi= {}
ans = [0]*Q
q.sort(key= lambda x:x[1])
R = 0
for l,r,ind in q:
    for i in range(R,r):
        if c[i] in rbi:
            add(rbi[c[i]],-1)
        rbi[c[i]] = i+1
        add(rbi[c[i]],1)
    ans[ind] = sum(r)-sum(l-1)
    R = r

for i in ans:
    print(i)
            

### FIXED CODE ###

class BIT: # 1Indexed
    def __init__(self,size):
        self.array = [0]*size
        self.size  = size
    def add(self,ind,value):
        while ind <= self.size:
            self.array[ind-1] += value
            ind += ind & -ind
    def sum(self,x):
        out = 0
        while x > 0:
            out += self.array[x-1]
            x -= x & -x
        return out

################### ABC174F ###################

import sys
input = sys.stdin.readline

def main(N,Q,c,q):
    bit = BIT(N)
    rbi= {}
    ans = [0]*Q
    q.sort(key= lambda x:x[1])
    R = 0
    for l,r,ind in q:
        for i in range(R,r):
            if c[i] in rbi:
                bit.add(rbi[c[i]],-1)
            rbi[c[i]] = i+1
            bit.add(rbi[c[i]],1)
        ans[ind] = bit.sum(r)-bit.sum(l-1)
        R = r
    return ans

if __name__ == "__main__":
    N,Q = map(int,input().split())
    c = list(map(int,input().split()))
    q = list( list(map(int,input().split()))+[i] for i in range(Q))
    ans = main(N,Q,c,q)
    for i in ans:
        print(i)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    n,m=map(int,input().split())
    E=[[] for _ in range(3*n)]
    for _ in range(m):
        u,v=map(int,input().split())
        u-=1; v-=1
        E[3*u].append(3*v+1)
        E[3*u+1].append(3*v+2)
        E[3*u+2].append(3*v)
    s,t=map(int,input().split())
    s-=1; t-=1

    # DFS
    from collections import deque
    d=[INF]*(3*n)
    d[3*s]=0

    def dfs(v):
        for nv in E[v]:
            if(d[nv]>d[v]+1):
                d[nv]=d[v]+1
                dfs(nv)

    dfs(3*s)
    ans=d[3*t]
    print(ans//3 if(ans!=INF) else -1)
resolve()

### FIXED CODE ###

import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    n,m=map(int,input().split())
    E=[[] for _ in range(3*n)]
    for _ in range(m):
        u,v=map(int,input().split())
        u-=1; v-=1
        E[3*u].append(3*v+1)
        E[3*u+1].append(3*v+2)
        E[3*u+2].append(3*v)
    s,t=map(int,input().split())
    s-=1; t-=1

    # BFS (startは0、goalは3n-3)
    from collections import deque
    d=[-1]*(3*n)
    d[3*s]=0
    Q=deque()
    Q.append(3*s)
    while(Q):
        v=Q.popleft()
        for nv in E[v]:
            if(d[nv]!=-1): continue
            d[nv]=d[v]+1
            Q.append(nv)
    ans=d[3*t]
    print(ans//3 if(ans!=-1) else -1)
resolve()
### BUGGY CODE ###

n,m,Q = map(int, input().split())
train = []
for i in range(n):
  a = []
  for j in range(n):
    a.append(0)
  train.append(a)
  
for i in range(m):
  l,r = map(int, input().split())
  train[l-1][r-1] += 1

for i in range(n):
  lst = [0,train[i][0]]
  for j in range(1,n):
    lst.append(lst[j]+train[i][j])
  train[i] = lst 
pq = []
for i in range(Q):
  p,q = map(int, input().split())
  ans = 0
  for i in range(p-1,q):
      ans += train[i][q]

  print(ans)


### FIXED CODE ###

n,m,Q = map(int, input().split())
train = []
for i in range(n):
  a = []
  for j in range(n):
    a.append(0)
  train.append(a)
  
for i in range(m):
  l,r = map(int, input().split())
  train[l-1][r-1] += 1
cumsum = []
list1 = []
for i in range(n+1):
  list1.append(0)
cumsum.append(list1)
for i in range(n):
  lst = [0,cumsum[i][1]+train[i][0]]
  for j in range(1,n):
    lst.append(lst[j]+train[i][j]+(cumsum[i][j+1]-cumsum[i][j]))
  cumsum.append(lst)
for i in range(Q):
  p,q = map(int, input().split())
  print(cumsum[q][q]-cumsum[p-1][q]-cumsum[q][p-1]+cumsum[p-1][p-1])
### BUGGY CODE ###

from random import randint
from collections import defaultdict
from numba import njit
import numpy as np


def f(h,w,m,ins):
    yp = np.zeros((h,2),dtype=np.int)
    xp = np.zeros((w,2),dtype=np.int)
    yp[:,1] = np.arange(h)
    xp[:,1] = np.arange(w)
    ans = 0
    s = set()
    for hi,wi in ins:
        s.add((hi-1,wi-1))
        yp[hi-1,0] += 1
        xp[wi-1,0] += 1
    ypm = yp[:,0].max()
    xpm = xp[:,0].max()
    yps = yp[yp[:,0] == ypm][:,1]
    xps = xp[xp[:,0] == xpm][:,1]
    #y = yp[yps]
    for ypsi in yps:
        for xpsi in xps:
            a = yp[ypsi,0]+xp[xpsi,0]
            a -= (ypsi,xpsi) in s
            ans = max(ans,a)
    return ans


if False:
    while True:
        h,w = randint(1,10**5*3),randint(1,10**5*3)
        m = randint(1,min(h*w,10**5*3))
        ins = [(randint(1,h),randint(1,w)) for i in range(m)]
        ans1 = f1(h,w,m,ins)
        ans2 = f2(h,w,m,ins)
        if ans1 != ans2:
            print("!!!!")
            print(h,w,m)
            print(ins)
else:
    h,w,m = map(int,input().split())
    ans = f(h,w,m,[tuple(map(int,input().split())) for i in range(m)])
    print(ans)


### FIXED CODE ###

from random import randint
import numpy as np
from numba import njit


#@njit
def f(h,w,m,ins):
    yp = np.zeros((h,2),dtype=np.int)
    xp = np.zeros((w,2),dtype=np.int)
    yp[:,1] = np.arange(h)
    xp[:,1] = np.arange(w)
    ans = 0
    s = set()
    for hi,wi in ins:
        s.add((hi-1,wi-1))
        yp[hi-1,0] += 1
        xp[wi-1,0] += 1
    ypm = yp[:,0].max()
    xpm = xp[:,0].max()
    yps = yp[yp[:,0] == ypm][:,1]
    xps = xp[xp[:,0] == xpm][:,1]
    #y = yp[yps]
    for ypsi in yps:
        for xpsi in xps:
            a = yp[ypsi,0]+xp[xpsi,0]
            if (ypsi,xpsi) in s:
                a -= 1
                ans = max(ans,a)
            else:
                return a
    return ans


if False:
    while True:
        h,w = randint(1,10**5*3),randint(1,10**5*3)
        m = randint(1,min(h*w,10**5*3))
        ins = [(randint(1,h),randint(1,w)) for i in range(m)]
        ans1 = f1(h,w,m,ins)
        ans2 = f2(h,w,m,ins)
        if ans1 != ans2:
            print("!!!!")
            print(h,w,m)
            print(ins)
else:
    h,w,m = map(int,input().split())
    ans = f(h,w,m,[tuple(map(int,input().split())) for i in range(m)])
    print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**6)

readline = sys.stdin.readline

N, M = map(int, readline().split())
G = [[] for i in range(N)]
for i in range(N-1):
    x, y = map(int, readline().split())
    G[x-1].append((y-1, 2*i))
    G[y-1].append((x-1, 2*i+1))

memo = [0]*(2*N+1)
def dfs0(v, p, e):
    r = 1
    for w, d in G[v]:
        if w == p:
            continue
        r = r * (1 + dfs0(w, v, d)) % M
    memo[e] = r
    return r


lv = [0]*(2*N); rv = [0]*(2*N)
def dfs1(v, p, par):
    s = 1 + par
    for w, d in G[v]:
        if w == p:
            continue
        lv[d] = s
        s = s * (1 + memo[d]) % M
    s = 1
    for w, d in reversed(G[v]):
        if w == p:
            continue
        rv[d] = s
        s = s * (1 + memo[d]) % M
    for w, d in G[v]:
        if w == p:
            continue
        memo[d ^ 1] = x = lv[d] * rv[d] % M
        dfs1(w, v, x)


dfs0(0, -1, 2*N)
dfs1(0, -1, 0)
ans = []
for v in range(N):
    r = 1
    for w, d in G[v]:
        r = r * (1 + memo[d]) % M
    ans.append("%d\n" % r)
sys.stdout.writelines(ans)

### FIXED CODE ###

import sys
from collections import deque

readline = sys.stdin.readline

N, M = map(int, readline().split())
G = [[] for i in range(N)]
for i in range(N-1):
    x, y = map(int, readline().split())
    G[x-1].append((y-1, 2*i))
    G[y-1].append((x-1, 2*i+1))

G0 = [None]*N
V = [(0, -1)]
used = [0]*N
used[0] = 1
que = deque([0])
while que:
    v = que.popleft()
    g = []
    for e in G[v]:
        w, d = e
        if used[w]:
            continue
        g.append(e)
        V.append(e)
        used[w] = 1
        que.append(w)
    G0[v] = g

memo = [0]*(2*N+1)
for v, e in reversed(V):
    r = 1
    for w, d in G0[v]:
        r = r * (1 + memo[d]) % M
    memo[e] = r

lv = [0]*(2*N); rv = [0]*(2*N)
for v, e in V:
    s = 1 + memo[e ^ 1]
    for w, d in G0[v]:
        lv[d] = s
        s = s * (1 + memo[d]) % M
    s = 1
    for w, d in reversed(G0[v]):
        rv[d] = s
        s = s * (1 + memo[d]) % M
    for w, d in G0[v]:
        memo[d ^ 1] = lv[d] * rv[d] % M

ans = []
for v in range(N):
    r = 1
    for w, d in G[v]:
        r = r * (1 + memo[d]) % M
    ans.append("%d\n" % r)
sys.stdout.writelines(ans)
### BUGGY CODE ###

import sys
import math
from copy import deepcopy
from collections import deque
sys.setrecursionlimit(20000000)


def main():
    N = int(input())
    nums = [int(input()) for _ in range(N)]

    for i in range(len(nums)):
        t = deepcopy(nums)
        t.pop(i)

        print(max(t))


if __name__ == '__main__':
    main()



### FIXED CODE ###

import sys
import math
from copy import deepcopy
from collections import deque
sys.setrecursionlimit(20000000)


def main():
    N = int(input())
    nums = [int(input()) for _ in range(N)]
    a = deepcopy(nums)
    a.sort(reverse=True)

    for i in range(len(nums)):
        if a[0] == nums[i]:
            print(a[1])
        else:
            print(a[0])


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

n = int(input())
a = list()
for i in range(n):
    x = input()
    a.append(int(x))
for i in range(n):
    if max(a) == a[i] and a.count(a[i]) == 1:
        print(sorted(a)[-2])
    else:
        print(max(a))

### FIXED CODE ###

n = int(input())
a = list()
for i in range(n):
    x = input()
    a.append(int(x))
second = sorted(a)[-2]
m = max(a)
for i in range(n):
    if m == a[i]:
        print(second)
    else:
        print(m)
### BUGGY CODE ###

def main():
    N = int(input())
    A = list(map(int,input().split()))
    Q = int(input())
    B = [0 for i in range(Q)]
    C = [0 for i in range(Q)]
    
    for q in range(Q):
        b,c = map(int,input().split())
        A = [c if a == b else a for a in A]
        print(sum(A))
    
if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    N = int(input())
    A = list(map(int,input().split()))
    Q = int(input())
    B = [0 for i in range(Q)]
    C = [0 for i in range(Q)]
    
    A_num = [0 for i in range(10**5+1)]
    ans = 0
    for a in A:
        ans += a
        A_num[a] += 1
    
    for q in range(Q):
        b,c = map(int,input().split())
        if A_num[b] != 0:
            ans += (c-b)*A_num[b]
            A_num[c] += A_num[b]
            A_num[b] = 0
            
        print(ans)
    
if __name__ == '__main__':
    main()
### BUGGY CODE ###

# D
s = input()
q = int(input())
for i in range(q):
    try:
        n, f, c = map(str, input().split())
    except ValueError:
        s = s[::-1]
        n = '1'
    if int(n) == 2:
        if int(f) == 1:
            s = c + s
        elif int(f) == 2:
            s = s + c
            
print(s)

### FIXED CODE ###

# D
# maspyの解答
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
from collections import deque
 
S = deque(readline().rstrip().decode())
Q = int(readline())
query = readlines()
 
rev = False
for q in query:
    if q[0] == ord('1'):
        rev = not rev
    else:
        _, f, c = q.decode().split()
        f = int(f)
        if rev ^ (f == 1):
            S.appendleft(c)
        else:
            S.append(c)
 
T = ''.join(S)
if rev:
    T = T[::-1]
print(T)
### BUGGY CODE ###

s=list(input())

a=[1 for _ in [0]*(len(s))]
b=[1 for _ in [0]*(len(s))]
j=0
while(1):
    j+=1
    c=[0 for _ in [0]*len(s)]
    for i,S in enumerate(s):
        if S=="R":
            c[i+1]+=b[i]
        else:
            c[i-1]+=b[i]
    if a==c and j%2==0:
        break
    a=b
    b=c
print(*c)

### FIXED CODE ###

s=list(input())

cnt=1
a=[]
for i in range(len(s)-1):
    if s[i]!=s[i+1]:
        a.append(cnt)
        cnt=1
    else:
        cnt+=1
a.append(cnt)

ans=[]
for j in range(len(a)//2):
    p=a[2*j]
    q=a[2*j+1]
    r=p+q
    s=r//2
    if s==r-s:
        ans+=([0]*(p-1))+[s,r-s]+([0]*(q-1))
    elif p>q:
        if p%2==1:
            ans+=([0]*(p-1))+[r-s,s]+([0]*(q-1))
        else:
            ans+=([0]*(p-1))+[s,r-s]+([0]*(q-1))
    else:
        if q%2==0:
            ans+=([0]*(p-1))+[r-s,s]+([0]*(q-1))
        else:
            ans+=([0]*(p-1))+[s,r-s]+([0]*(q-1))
print(*ans)
### BUGGY CODE ###

K=int(input())
def gcd(a,b):
    res=0
    while b!=0:
        res=a%b
        a=b
        b=res
    return a

ans=0
for i in range(1,K+1):
    for j in range(1,K+1):
        for k in range(1,K+1):
            t=gcd(i,gcd(j,k))
            ans+=t
print(ans)

### FIXED CODE ###

K=int(input())
def gcd(a,b):
    res=0
    while b!=0:
        res=a%b
        a=b
        b=res
    return a

ans=0
for i in range(1,K+1):
    for j in range(1,K+1):
        for k in range(1,K+1):
            t=gcd(i,gcd(j,k))
            ans+=t
print(ans)
### BUGGY CODE ###

def expectation(n):
    return (n + 1) / 2


def main():
    n, k = map(int, input().split())
    p = list(map(int, input().split()))
    answer = 0
    for i in range(n - k + 1):
        tmp = 0
        for j in range(k):
            tmp += expectation(p[i + j])
        answer = max(answer, tmp)
    print(answer)


if __name__ == '__main__':
    main()



### FIXED CODE ###

def main():
    # 差分だけ微調整する解法
    N, K = map(int, input().split(" "))
    p = list(map(int, input().split(" ")))
    answer = sum(p[:K])
    tmp = sum(p[:K])
    for i in range(N - K):
        tmp = tmp + p[i+K] - p[i]
        answer = max(answer, tmp)
    print((answer + K) / 2)


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

import sys
input = sys.stdin.readline
#import numpy as np
from scipy.sparse import csr_matrix, coo_matrix
from scipy.sparse.csgraph import dijkstra, depth_first_tree

#sys.setrecursionlimit(10000)

N = int(input())

rows = []
cols = []
weights = []

for _ in range(N-1):
    # u v 間のコスト
    u, v, a = [int(i) for i in input().split()]
    rows.append(u-1)
    cols.append(v-1)
    weights.append(a)

Q, K = [int(i) for i in input().split()]

graph = coo_matrix((weights, (rows, cols)), shape=(N, N)).tocsr()
d1 = dijkstra(graph, indices = K-1, directed=False)

for i in range(Q):
    x, y = [int(i) for i in input().split()]
    print(int(d1[x-1]+d1[y-1]))


### FIXED CODE ###

from collections import defaultdict
from heapq import heappop, heappush


class Graph(object):
    """
    隣接リストによる有向グラフ
    """

    def __init__(self):
        self.graph = defaultdict(list)

    def __len__(self):
        return len(self.graph)

    def add_edge(self, src, dst, weight=1):
        self.graph[src].append((dst, weight))

    def get_nodes(self):
        return self.graph.keys()


class Dijkstra(object):
    """
    ダイクストラ法（二分ヒープ）による最短経路探索
    計算量: O((E+V)logV)
    """

    def __init__(self, graph, start):
        self.g = graph.graph

        # startノードからの最短距離
        # startノードは0, それ以外は無限大で初期化
        self.dist = defaultdict(lambda: float('inf'))
        self.dist[start] = 0

        # 最短経路での1つ前のノード
        self.prev = defaultdict(lambda: None)

        # startノードをキューに入れる
        self.Q = []
        heappush(self.Q, (self.dist[start], start))

        while self.Q:
            # 優先度（距離）が最小であるキューを取り出す
            dist_u, u = heappop(self.Q)
            if self.dist[u] < dist_u:
                continue
            for v, weight in self.g[u]:
                alt = dist_u + weight
                if self.dist[v] > alt:
                    self.dist[v] = alt
                    self.prev[v] = u
                    heappush(self.Q, (alt, v))

    def shortest_distance(self, goal):
        """
        startノードからgoalノードまでの最短距離
        """
        return self.dist[goal]

    def shortest_path(self, goal):
        """
        startノードからgoalノードまでの最短経路
        """
        path = []
        node = goal
        while node is not None:
            path.append(node)
            node = self.prev[node]
        return path[::-1]


g = Graph()

N = int(input())

rows = []
cols = []
weights = []

for _ in range(N-1):
    # u v 間のコスト
    u, v, a = [int(i) for i in input().split()]
    g.add_edge(u-1, v-1, a)
    g.add_edge(v-1, u-1, a)

Q, K = [int(i) for i in input().split()]
d = Dijkstra(g, K-1)

#print(g)
#print(d.dist)
for i in range(Q):
    x, y = [int(i) for i in input().split()]
    print(d.dist[x-1]+d.dist[y-1])
### BUGGY CODE ###

line1 = input()
line2 = input()

aryLine1 = line1.split()
aryLine2 = line2.split()

K = int(aryLine1[0]);
N = int(aryLine1[1]);

ans = 0

for i in range(0, N):
    temp1 = int(aryLine2[i])
    for j in range(0, N):
        temp2 = int(aryLine2[j])

        if temp1 > temp2:
            ans1 = temp1 - temp2
            ans2 = temp2 - temp1 + K
        else:
            ans1 = temp2 - temp1
            ans2 = temp1 - temp2 + K

        if ans1 > ans2:
            tempans = ans2
        else:
            tempans = ans1

        if tempans > ans:
            ans = tempans

print(ans)

### FIXED CODE ###

line1 = input()
line2 = input()

aryLine1 = line1.split()
arystrLine2 = line2.split()

K = int(aryLine1[0]);
N = int(aryLine1[1]);

aryLine2 = [int(s) for s in arystrLine2]
#print(aryLine2)

aryLine2.sort()
#print(aryLine2)

ans = K

for i in range(0, N):
    temp1 = int(aryLine2[i])
    if i == N - 1:
        temp2 = int(aryLine2[0]) + K
    else:
        temp2 = int(aryLine2[i + 1])

    temp = temp1 - temp2 + K

    if temp < ans:
        ans = temp

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

s = input()
N = len(s)
x,y = map(int, input().split())
ls = s.split('T')
A = []
B = []
dpx = [0]*(2*N+1)
dpy = [0]*(2*N+1)
for i,c in enumerate(ls):
  if i%2==0:
    A += [len(c)]
  else:
    B += [len(c)]
x -= A[0]
A = A[1:]
dpx[N] = 1
dpy[N] = 1
for a in A:
  dpx = [1 if (i>=a and dpx[i-a]) or (i<=2*N-a and dpx[i+a]) else 0 for i in range(2*N+1)]
for b in B:
  dpy = [1 if (i>=b and dpy[i-b]) or (i<=2*N-b and dpy[i+b]) else 0 for i in range(2*N+1)]
if x>N or y>N:
  print('No')
elif dpx[x+N] and dpy[y+N]:
  print('Yes')
else:
  print('No')

### FIXED CODE ###

s = input()
x, y = map(int, input().split())
a = []
b = []
c = 0
n = 0
for i in range(len(s)):
  if s[i]=='F':
    n += 1
  else:
    if c%2==0:
      a += [n]
    else:
      b += [n]
    c += 1
    n = 0
if s[-1]=='F':
  if c%2==0:
    a += [n]
  else:
    b += [n]
sa = sum(a)
sb = sum(b)
dpa1 = [0]*(2*sa+1)
dpa2 = [0]*(2*sa+1)
dpb1= [0]*(2*sb+1)
dpb2 = [0]*(2*sb+1)
dpa1[sa] = 1
dpb1[sb] = 1
if len(a)>0:
  if sa-a[0]<abs(x-a[0]) or sb<abs(y):
    print('No')
    import sys
    sys.exit()
else:
  if sa<abs(x) or sb<abs(y):
    print('No')
    import sys
    sys.exit()

if len(a)%2==0:
  A = dpa1
else:
  A = dpa2
if len(b)%2==0:
  B = dpb1
else:
  B = dpb2

for i in range(len(a)):
  c = a[i]
  if i%2==0:
    for j in range(2*sa+1):
      if dpa1[j]==1:
        dpa1[j] = 0
        dpa2[j-c] = 1
        dpa2[j+c] = 1
  else:
    for j in range(2*sa+1):
      if dpa2[j]==1:
        dpa2[j] = 0
        dpa1[j-c] = 1
        dpa1[j+c] = 1
for i in range(len(b)):
  c = b[i]
  if i%2==0:
    for j in range(2*sb+1):
      if dpb1[j]==1:
        dpb1[j] = 0
        dpb2[j-c] = 1
        dpb2[j+c] = 1
  else:
    for j in range(2*sb+1):
      if dpb2[j]==1:
        dpb2[j] = 0
        dpb1[j-c] = 1
        dpb1[j+c] = 1

if A[x+sa]==1 and B[y+sb]==1:
  print('Yes')
else:
  print('No')
### BUGGY CODE ###

N,M = map(int,input().split())
lst = list(map(int,input().split()))

for i in range(M):
    lst[lst.index(max(lst))] = max(lst) // 2 

print (sum(lst))



### FIXED CODE ###

import heapq

N,M = map(int,input().split())
#lst = list(map(int,input().split()))
lst = [-int(x) for x in input().split()]

heapq.heapify(lst)
 
for i in range(M):
    lstmin = heapq.heappop(lst)
    b = (-(lstmin) // 2)
    heapq.heappush(lst,-b)
    
print (-sum(lst))
### BUGGY CODE ###

N = int(input())
L = list(map(int,input().split()))
count = 0
n = 0
for l in L:
    L_s = L.copy()
    L_s.pop(n)
    n += 1
    for l_s in L_s:
        if l%l_s == 0:
            break
    else:
        count += 1

print(count)

### FIXED CODE ###

n = int(input())
data = list(map(int, input().split()))
mx = max(data)
marked = [0]*(mx + 1)
for a in data:
    for x in range(a, mx+1, a):
        marked[x] += 1
ans = 0
for a in data:
    if marked[a] == 1:
        ans += 1
print(ans)
### BUGGY CODE ###

# coding: utf-8

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

# from random import randint
# n = 10000
# k = 100
w = [0 for _ in range(n)]
for i in range(n):
    w[i] = int(input())
    # w[i] = randint(1, 10000)
# print(w)
P = max(sum(w)//k, max(w))
count = 0
while True:
    m = 0
    ik = 1
    loss = max(w)
    for i in range(n):
        count += 1
        new = m + w[i]
        if new <= P:
            m = new
        else:
            loss = new - P if new - P < loss else loss
            m = w[i]
            ik += 1
            if ik > k:
                break
    if ik > k:
        # print("loss:", loss)
        P += loss
    else:
        break
            
        
print(P)
# print(count)

### FIXED CODE ###

# coding: utf-8

n, k = map(int, input().rstrip().split())
w = [0 for _ in range(n)]
for i in range(n):
    w[i] = int(input())
    
# from random import randint
# n = 100000
# k = 10000
# w = [0 for _ in range(n)]
# for i in range(n):
#     w[i] = randint(1, 10000)
# print(w)
count = 0

def check(P):
    m = 0
    ik = 1
    for i in range(n):
        global count
        count += 1
        new = m + w[i]
        if new > P:
            m = w[i]
            ik += 1
            if ik > k:
                return False
        else:
            m = new
    return True

s = max(sum(w)//k, max(w))
e = sum(w)

while True:
    P = (s + e)//2
    # print("s:{}, e:{}, P:{}".format(s, e, P))
    if s == e:
        break
    if check(P):
        e = P
    else:
        s = P + 1
            
        
print(P)
# print(count)