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

N,W = [int(c) for c in input().split()]
wv = [[int(c) for c in input().split()] for d in range(N)]

dp = [[0]*(W+1) for c in range(N)]
#i番目の品物まで候補としたとき(使うかはわからない)、重さj以下のときの価値の総量がdp[i][j]
for i in range(N):
    for j in range(W+1):
        #重さj以下で、iを使うときと使わないときの大きい方
        if j-wv[i][0] >= 0:
            dp[i][j] = max([dp[i-1][j-wv[i][0]]+wv[i][1],dp[i-1][j]])
        else:
            dp[i][j] = dp[i-1][j]

print(dp[-1][-1])

### FIXED CODE ###

N,W = [int(c) for c in input().split()]
wv = [[int(c) for c in input().split()] for d in range(N)]

dp = [[0]*(W+1) for c in range(N)]
#i番目の品物まで候補としたとき(使うかはわからない)、重さj以下のときの価値の総量がdp[i][j]
for i in range(N):
    for j in range(W+1):
        #重さj以下で、iを使うときと使わないときの大きい方
        if j-wv[i][0] >= 0:
            dp[i][j] = max([dp[i-1][j-wv[i][0]]+wv[i][1],dp[i-1][j]])
        else:
            dp[i][j] = dp[i-1][j]

print(dp[-1][-1])
### BUGGY CODE ###

k = int(input())
if(k%2==0):
  print("-1")
else:
  i = 1
  while True:
    m = 7
    if(m%k==0):
      print(i)
      break
    if(i>100000000):
      print("-1")
      break
    m = m*10 + 7
    i += 1

  
  


### FIXED CODE ###

k = int(input())
m = 7
if(k%2==0):
  print("-1")
else:
  i = 1
  while True:
    m = m%k
    if(m==0):
      print(i)
      break  
    if(i>k):
      print("-1")
      break
    m *= 10
    m += 7
    i += 1
### BUGGY CODE ###

import sys
read = sys.stdin.read
readlines = sys.stdin.readlines
def main():
    n = int(input())
    a = tuple(map(int, input().split()))

    r = 0
    for i1 in range(n - 1):
        for i2 in range(1, n - i1):
            r += a[i1+i2] == i2 - a[i1]
    print(r)

if __name__ == '__main__':
    main()


### FIXED CODE ###

from collections import Counter

def main():
    n = int(input())
    a = list(map(int, input().split()))
    cnt = 0
    l1 = []
    for ea in a:
        l1.append(cnt - ea)
        cnt += 1
    l1c = Counter(l1)
    r = 0
    for i2 in range(n):
        r += l1c[i2 + a[i2]]
    print(int(r))

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

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

ans = 1

for i in A:
    ans = ans * i

if ans > 10**18:
    print(-1)
else:
    print(ans)

### FIXED CODE ###

from collections import deque

N = int(input())
A = list(map(int,input().split()))
if 0 in A:
    print(0)
    exit();

A = deque(A)

if N%2 == 1:
    ans_right = A.pop()
else:
    ans_right = 1

ans_left = 1

for i in range(N//2):
    right = A.pop()
    left = A.popleft()
    
    ans_right = ans_right * right
    ans_left = ans_left * left

    if ans_right > 10**18 or ans_left> 10**18 or ans_left*ans_right> 10**18:
        print(-1)
        exit()


else:
    print(ans_right*ans_left)
### BUGGY CODE ###

N = int(input())
T = [[] for i in range(N)]
for i in range(N - 1):
  a, b = map(int, input().split())
  T[a - 1].append(b - 1)
  T[b - 1].append(a - 1)
def dijkstra(N, s0):
  D = [N] * N
  Q = [s0]
  D[s0] = 0
  while Q:
    s = Q[0]
    Q = Q[1:]
    for adj in T[s]:
      if D[s] + 1 < D[adj]:
        D[adj] = D[s] + 1
        Q.append(adj)
  return D
D1 = dijkstra(N, 0)
D2 = dijkstra(N, N - 1)
score = 0
for i in range(N):
  score += 1 if D1[i] <= D2[i] else -1
print('Fennec' if score > 0 else 'Snuke')

### FIXED CODE ###

N = int(input())
T = [[] for i in range(N)]
for i in range(N - 1):
  a, b = map(int, input().split())
  T[a - 1].append(b - 1)
  T[b - 1].append(a - 1)
def dijkstra(N, s0):
  D = [N] * N
  D[s0] = 0
  Q = [N] * N
  Q[0] = s0
  tail = 1
  for i in range(N):
    s = Q[i]
    for adj in T[s]:
      if D[s] + 1 < D[adj]:
        D[adj] = D[s] + 1
        Q[tail] = adj
        tail += 1
  return D
D1 = dijkstra(N, 0)
D2 = dijkstra(N, N - 1)
score = 0
for i in range(N):
  score += 1 if D1[i] <= D2[i] else -1
print('Fennec' if score > 0 else 'Snuke')
### BUGGY CODE ###

s = input()
query = [input().split() for _ in range(int(input()))]
ctn = query.count(["1"]) % 2 == 1

new_query = []
flag = 0
for q in query:
    if len(q) == 1:
        if flag == 0:
            flag = 1
        else:
            flag = 0
    else:
        new_query.append(q + [flag])

for q in new_query:
    if q[-1] == 0:
        if q[1] == "1":
            s = q[2] + s
        else:
            s = s + q[2]
    else:
        if q[1] == "1":
            s = s + q[2]
        else:
            s = q[2] + s

if ctn:
    print(s[::-1])
else:
    print(s)

### FIXED CODE ###

from collections import deque

def main():

    s = deque(input())
    q = int(input())

    flag = 0
    query = []

    for _ in range(q):
        temp = input().split()
        if len(temp) == 1:
            flag += 1
        else:
            query.append(temp + [flag%2])

    for q in query:
        if q[-1] == 0:
            if q[1] == "1":
                s.appendleft(q[2])
            else:
                s.append(q[2])
        else:
            if q[1] == "1":
                s.append(q[2])
            else:
                s.appendleft(q[2])

    if flag % 2 == 1:
        print("".join(list(s)[::-1]))
    else:
        print("".join(s))

main()
### BUGGY CODE ###

from collections import defaultdict, deque, Counter
N, Q = map(int, input().split())

connection = defaultdict(list)
for i in range(N-1):
    a,b =  map(int, input().split())
    connection[a].append(b)

operations = []
for i in range(Q):
    p,q =  map(int, input().split())
    operations.append([p,q])

children = defaultdict(set)
for i in range(1,N+1):
    children[i].add(i)
    d = deque(connection[i])
    checked = set(connection[i])
    while len(d) > 0:
        x = d.popleft()
        children[i].add(x)
        d += connection[x]

c = Counter()
for opr in operations:
    for num in children[opr[0]]:
        c[num-1] += opr[1]

ans = []
for i in range(N):
    ans.append(str(c[i]))
print(' '.join(ans))

### FIXED CODE ###

import sys
sys.setrecursionlimit(200000)
from collections import deque

N, Q = map(int, input().split())

connection = [[] for i in range(N)]
for i in range(N-1):
    a,b =  map(int, input().split())
    connection[a-1].append(b)
    connection[b-1].append(a)

operations = [0] * N
for i in range(Q):
    p,q =  map(int, input().split())
    operations[p-1] += q

ans = [0] * N

stack = deque([1])
while len(stack)>0:
    node = stack.pop()
    ans[node-1] += operations[node-1]
    for node_c in connection[node-1]:
        connection[node_c-1].remove(node)
        ans[node_c-1] += ans[node-1]
        stack.append(node_c)

print(' '.join(map(str, ans)))
### BUGGY CODE ###

from sys import stdin
def solve():
    import collections
    readline = stdin.readline
    h,w = map(int,readline().split())
    si,sj = map(int,readline().split())
    gi,gj = map(int,readline().split())
    si,sj,gi,gj = si-1,sj-1,gi-1,gj-1
    grid = []
    for _ in [0]*h:
        grid.append(readline()[:-1])
    INF = float("inf")
    dist = [[INF]*w for _ in range(h)]
    q = collections.deque([(si,sj)])
    dist[si][sj] = 0
    while q:
        i,j = q.popleft()
        if (i,j) == (gi,gj):
            return dist[i][j]
        for ni,nj in [(i+1,j),(i-1,j),(i,j+1),(i,j-1)]:
            if 0 <= ni and ni < h and 0 <= nj and nj < w and grid[ni][nj] == ".":
                if dist[ni][nj] > dist[i][j]:
                    dist[ni][nj] = dist[i][j]
                    q.appendleft((ni,nj))
        listj = range(j-2,j+3)
        for ni in range(i-2,i+3):
            if not (0 <= ni and ni < h): continue
            for nj in listj:
                if not (0 <= nj and nj < w): continue
                if (ni,nj) not in [(i,j),(i+1,j),(i-1,j),(i,j+1),(i,j-1)] and grid[ni][nj] == ".":
                    if dist[ni][nj] > dist[i][j] + 1:
                        dist[ni][nj] = dist[i][j] + 1
                        q.append((ni,nj))

    return -1

print(solve())

### FIXED CODE ###

from sys import stdin
def solve():
    import collections
    readline = stdin.readline
    h,w = map(int,readline().split())
    si,sj = map(int,readline().split())
    gi,gj = map(int,readline().split())
    si,sj,gi,gj = si-1,sj-1,gi-1,gj-1
    grid = []
    for _ in [0]*h:
        grid.append(readline()[:-1])
    INF = float("inf")
    dist = [[INF]*w for _ in range(h)]
    q = collections.deque([(si,sj)])
    dist[si][sj] = 0
    while q:
        i,j = q.popleft()
        if (i,j) == (gi,gj):
            return dist[i][j]
        for ni,nj in [(i+1,j),(i-1,j),(i,j+1),(i,j-1)]:
            if 0 <= ni and ni < h and 0 <= nj and nj < w and grid[ni][nj] == ".":
                if dist[ni][nj] > dist[i][j]:
                    dist[ni][nj] = dist[i][j]
                    q.appendleft((ni,nj))
        listj = range(j-2,j+3)
        for ni in range(i-2,i+3):
            if not (0 <= ni and ni < h): continue
            for nj in listj:
                if not (0 <= nj and nj < w): continue
                if grid[ni][nj] == "." and dist[ni][nj] > dist[i][j] + 1:
                    dist[ni][nj] = dist[i][j] + 1
                    q.append((ni,nj))

    return -1

print(solve())
### BUGGY CODE ###

import math
import bisect

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

for i in range(M):
    n = A.pop() / 2
    bisect.insort(A, n)
    
for j in range(N):
    A[j] = math.floor(A[j])

print(sum(A))


### FIXED CODE ###

from heapq import heapify, heappop, heappush

N, M = map(int, input().split())
A = list(map(int, input().split()))
A_minus = [-x for x in A]
heapify(A_minus)

for i in range(M):
    n = -heappop(A_minus) // 2
    heappush(A_minus, -n)

print(-sum(A_minus))
### BUGGY CODE ###

#!/usr/bin/env python
# -*- coding: utf-8 -*-
#
# FileName: 	D
# CreatedDate:  2020-06-21 21:56:58 +0900
# LastModified: 2020-06-21 22:06:42 +0900
#


import copy

def main():
    n = int(input())
    a = list(map(int, input().split()))
    q = int(input())
    for _ in range(q):
        b,c = map(int, input().split())
        a = [i if i != b else c for i in a]
        print(sum(a))


if __name__ == "__main__":
    main()


### FIXED CODE ###

#!/usr/bin/env python
# -*- coding: utf-8 -*-
#
# FileName: 	D_fix_2
# CreatedDate:  2020-06-22 17:32:46 +0900
# LastModified: 2020-06-22 17:39:47 +0900
#


import os
import sys
#import numpy as np
#import pandas as pd


def main():
    n = int(input())
    a = list(map(int, input().split()))
    cnt = [0]*100001
    for a_ in a:
        cnt[a_] += 1

    total = sum(a)
    q = int(input())
    for _ in range(q):
        b, c = map(int, input().split())
        total += (c-b)*cnt[b]
        cnt[c] += cnt[b]
        cnt[b] = 0
        print(total)
        




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

n = int(input())
A = list(map(int,input().split()))
l = len(A)
sum = 0
for i in range(l-1):
    for j in range(i+1,l):
        sum += (A[i] ^ A[j])
print(sum%(10**9 +7))

### FIXED CODE ###

import numpy as np
 
 
def solve(string):
    n, *a = map(int, string.split())
    # a = ["{:060b}".format(_a) for _a in a]
    a = np.asarray(a, dtype=np.int64)
    m = 10**9 + 7
    ans = 0
    for i in range(60):
        s = int((a & 1).sum())
        a >>= 1
        # ans += s * (n - s) * pow(2, 59 - i, m)
        ans += s * (n - s) * pow(2, i, m) % m
        ans %= m
    return str(ans)
 
 
if __name__ == '__main__':
    import sys
    print(solve(sys.stdin.read().strip()))
### BUGGY CODE ###

N,K,Q=map(int,input().split(" "))
A=[]
for _ in range(Q):
    A.append(int(input()))

ans=[K for _ in range(N)]
for q in A:
    ans=[i-1 for i in ans]
    ans[q-1]+=1
for a in ans:
    if a>0:
        print("Yes")
    else:
        print("No")


### FIXED CODE ###

N,K,Q=map(int,input().split(" "))
A=[]
for _ in range(Q):
    A.append(int(input()))

ans=[K for _ in range(N)]
for q in A:
    ans[q-1]+=1
for a in ans:
    if a>Q:
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

from collections import deque


N, M = map(int, input().split())
graph = {i: set() for i in range(N)}
for _ in range(M):
    A, B = map(lambda x: int(x) - 1, input().split())
    graph[A].add(B)
    graph[B].add(A)

tokens = [-1] * N
visited = {0}
q = deque([0])
while q:
    v = q.popleft()
    visited.add(v)
    for nv in graph[v] - visited:
        if tokens[nv] < 0:
            tokens[nv] = v
        q.append(nv)
if -1 in tokens[1:]:
    print('No')
else:
    print('Yes')
    [print(t + 1) for t in tokens[1:]]


### FIXED CODE ###

from collections import deque, defaultdict
import sys


def input():
    return sys.stdin.readline().strip()


N, M = map(int, input().split())
graph = defaultdict(set)
for _ in range(M):
    A, B = map(lambda x: int(x) - 1, input().split())
    graph[A].add(B)
    graph[B].add(A)
if len(set(graph.keys())) != N:
    print('No')
    exit()

tokens = [-1] * N
visited = {0}
q = deque([0])
while q:
    v = q.popleft()
    visited.add(v)
    for nv in graph[v]:
        if nv in visited:
            continue
        if tokens[nv] < 0:
            tokens[nv] = v
            q.append(nv)

print('Yes')
[print(t + 1) for t in tokens[1:]]
### BUGGY CODE ###

from collections import defaultdict


def divisor(n):  # nの約数を全て求める
    i = 1
    div_set = set()
    while i * i <= n:
        if n % i == 0:
            div_set.add(i)
            div_set.add(n//i)
        i += 1
    return div_set


def divisor2(n):  # 既存のリストからnの約数だけを返す
    div_set = set()

    for i in kouho:
        if i > n:
            return div_set
        if n % i == 0:
            div_set.add(i)
    return div_set


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

divcount = defaultdict(int)
for n in A_list[:2]:
    for i in divisor(n):
        divcount[i] += 1

kouho = list(divcount.keys())
kouho.sort()
# print(kouho)

for n in A_list[2:]:
    for i in divisor2(n):
        divcount[i] += 1

# print(divcount)
max_divisor = 0
for key, value in divcount.items():
    if value >= N - 1 and key > max_divisor:
        max_divisor = key

print(max_divisor)


### FIXED CODE ###

from collections import defaultdict
import bisect


def divisor(n):  # nの約数を全て求める
    i = 1
    div_set = set()
    while i * i <= n:
        if n % i == 0:
            div_set.add(i)
            div_set.add(n//i)
        i += 1
    return div_set


def divisor2(n):  # 既存のリストからnの約数だけを返す
    div_set = set()

    for i in kouho:
        if i > n:
            return div_set
        if n % i == 0:
            div_set.add(i)
    return div_set


N = int(input())
A_list = list(map(int, input().split()))
A_list.sort()
max_index = bisect.bisect_left(A_list, A_list[-1])
# print(max_index)
times = max_index

divcount = defaultdict(int)
for n in A_list[:2]:
    # print(n)
    for i in divisor(n):
        divcount[i] += 1

kouho = list(divcount.keys())
kouho.sort()
# print(kouho)

for n in A_list[2:max_index+1]:
    # print(n)
    for i in divisor2(n):
        divcount[i] += 1

# print(divcount)
max_divisor = 0
for key, value in divcount.items():
    if value >= max_index and key > max_divisor:
        max_divisor = key

print(max_divisor)
### BUGGY CODE ###

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

import sys
from math import sqrt

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

def divisor_set(N: int) -> set:
    """ 約数の列挙・個数 """
    # 1とその数はデフォで入れとく
    s = {1, N}
    # 終点はルート切り捨て
    for i in range(2, int(sqrt(N))+1):
        # 割り切れるなら、iとN/iを追加
        if N % i == 0:
            s.add(i)
            s.add(N // i)
    return s

N=INT()
A=LIST()

A2=[0]*N
B=[]
for i in range(N-1, -1, -1):
    if A[i]!=A2[i]:
        B.append(i+1)
        div=divisor_set(i+1)
        for num in div:
            A2[num-1]=1-A2[num-1]
        
print(len(B))
print(*B)


### FIXED CODE ###

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

import sys
from math import sqrt

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

def divisor_set(N: int) -> set:
    """ 約数の列挙・個数 """
    # 1とその数はデフォで入れとく
    s = {1, N}
    # 終点はルート切り捨て
    for i in range(2, int(sqrt(N))+1):
        # 割り切れるなら、iとN/iを追加
        if N % i == 0:
            s.add(i)
            s.add(N // i)
    return s

N=INT()
A=LIST()

A2=[0]*N
B=[]
for i in range(N-1, -1, -1):
    if A[i]!=A2[i]:
        B.append(i+1)
        div=divisor_set(i+1)
        for num in div:
            A2[num-1]=1-A2[num-1]
        
print(len(B))
print(*B)
### BUGGY CODE ###

from collections import Counter

num = int(input())

tmp = [input() for i in range(num)]

count = Counter(tmp)

tmp2 = [k for k, v in count.items() if count.most_common(1)[0][1] == v]

for t in sorted(tmp2):
  print(t)

### FIXED CODE ###

def main():
  num = int(input())

  tmp = [input() for i in range(num)]

  tmp2 = {}
  for t in tmp:
    if len(tmp2) == 0:
      tmp2[t] = 1
    else:
      if t in tmp2:
        tmp2[t] += 1
      else:
        tmp2[t] = 1

  _tmp2 = sorted(tmp2.items(), key=lambda x:x[1])
  tmp3 = sorted(tmp2.items())
  for t in tmp3:
    if _tmp2[-1][1] == t[1]:
      print(t[0])

main()
### BUGGY CODE ###

mod, min_value = 2019, 2019
l, r = map(int, input().split())
length = r - l
for i in range(mod):
  for j in range(mod):
    if length - j - i <= 0:
      break
    min_value = min(min_value, (l + i) * (r - j) % mod)
print(min_value)

### FIXED CODE ###

mod, min_value = 2019, 2019
l, r = map(int, input().split())
length = r - l
for i in range(mod):
  for j in range(mod):
    if length - j - i <= 0 or min_value == 0:
      break
    min_value = min(min_value, (l + i) * (r - j) % mod)
print(min_value)
### BUGGY CODE ###

from itertools import combinations
import math
N = int(input())
A = list(map(int, input().split()))
mod = 1000000007

def add(a, b):
    return (a + b) % mod

def mul(a, b):
    return ((a % mod) * (b % mod)) % mod

#N = int(input())
#C = input()
#D, T, S=map(int,input().split())
#C = []
#for i in range(N):
#    C.append(list(map(int,input().split())))
c = 0
for i in range(0,N-1):
    for j in range(i+1, N):
        c = add(c, mul(A[i], A[j]))

print(c)




### FIXED CODE ###

from itertools import combinations
import math
N = int(input())
A = list(map(int, input().split()))
mod = 1000000007

def add(a, b):
    return (a + b) % mod

def mul(a, b):
    return ((a % mod) * (b % mod)) % mod

def cumsum(xs):
    result = [xs[0]]
    for x in xs[1:]:
        result.append(add(result[-1], x))
    return result

#N = int(input())
#C = input()
#D, T, S=map(int,input().split())
#C = []
#for i in range(N):
#    C.append(list(map(int,input().split())))

inv = cumsum(list(reversed(A)))
c = 0
for i in range(0,N-1):
    c = add(c,mul(A[i],inv[N-i-2]))

print(c)
### BUGGY CODE ###

#!/usr/bin/env python
from collections import deque

def main():
    n, q = map(int, input().split())
    link = [[] for _ in range(n+1)]
    for _ in range(n-1):
        a, b = map(int, input().split())
        link[a].append(b)
        link[b].append(a)
    manip = [list(map(int, input().split())) for _ in range(q)]

    child = [[] for _ in range(n+1)]
    unchecked = [True for _ in range(n+1)]
    unchecked[1] = False
    que = deque([1])
    while que:
        parent = que.popleft()
        for l in link[parent]:
            if unchecked[l]:
                unchecked[l] = False
                child[parent].append(l)
                que.append(l)

    cnt = [0 for _ in range(n+1)]
    for m in manip:
        p, x = m
        que = deque([p])
        while que:
            node = que.popleft()
            cnt[node] += x
            for c in child[node]:
                que.append(c)

    print(' '.join(map(str, cnt[1:])))

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python
from collections import deque

def main():
    n, q = map(int, input().split())
    link = [[] for _ in range(n+1)]
    for _ in range(n-1):
        a, b = map(int, input().split())
        link[a].append(b)
        link[b].append(a)
    manip = [list(map(int, input().split())) for _ in range(q)]

    cnt = [0 for _ in range(n+1)]
    for m in manip:
        node, x = m
        cnt[node] += x

    parent = [0 for _ in range(n+1)]
    unchecked = [True for _ in range(n+1)]
    unchecked[1] = False
    que = deque([1])
    while que:
        node = que.pop()
        for l in link[node]:
            if unchecked[l]:
                unchecked[l] = False
                cnt[l] += cnt[node]
                que.append(l)

    print(' '.join(map(str, cnt[1:])))

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

a,b,c,d=map(int,input().split())

ans=0

for i in range(a,b+1):
    if i%c!=0 and i%d!=0:
        ans+=1
    else:
        ans+=0

print(ans)

### FIXED CODE ###

import fractions
a,b,c,d=map(int,input().split())

cc=b//c-(a-1)//c
dd=b//d-(a-1)//d
s=b//(c*d//fractions.gcd(c,d))-(a-1)//(c*d//fractions.gcd(c,d))


print((b-(a-1)-(cc+dd-s)))
### BUGGY CODE ###

# sys.stdin.readline()
import sys
import time
input = sys.stdin.readline
import math

N,M = (int(x) for x in input().split())
A = list(map(int, input().split()))
# A.sort(reverse=True)

# t1 = time.time()
for i in range(M):
    a = max(A) // 2
    j = A.index(max(A))
    A[j] = a
    # if sum(A) <1:
    #     break

print(sum(A))

### FIXED CODE ###

# sys.stdin.readline()
import sys
import time
input = sys.stdin.readline
import math
import heapq

N,M = (int(x) for x in input().split())
A = list(map(int, input().split()))
A = [-i for i in A]
# print(A)
heapq.heapify(A)
# print(heapq.heappop(A))

# t1 = time.time()
for i in range(M):
    a = -heapq.heappop(A) // 2
    heapq.heappush(A, -a)
    # j = A.index(max(A))
    # A[j] = a
    # A[0] = A[0]//2
    # A.sort(reverse=True)
    # if sum(A) <1:
    #     break

print(-sum(A))
### BUGGY CODE ###

H, N = map(int, input().split())
inf = 10 ** 9
dp = [inf for i in range(H + 1)]
dp[0] = 0

for i in range(N):
    a, b = map(int, input().split())
    for j in range(H):
        nj = min(j + a, H)
        dp[nj] = min(dp[nj], dp[j] + b)

print(dp[H])


### FIXED CODE ###

H, N = map(int, input().split())
inf = 10 ** 9
dp = [inf for i in range(H + 1)]
dp[0] = 0

for i in range(N):
    a, b = map(int, input().split())
    for j in range(H):
        nj = min(j + a, H)
        dp[nj] = min(dp[nj], dp[j] + b)

print(dp[H])
### BUGGY CODE ###

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

for i in t:
    if i not in d:
        print("NO")
        exit()
    d.pop(d.index(i))
print("YES")

### FIXED CODE ###

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

p = {}
for d in D:
    if d not in p:
        p[d] = 1
    else:
        p[d] += 1

for t in T:
    if t not in p:
        print('NO')
        exit()
    if p[t] == 0:
        print('NO')
        exit()
    p[t] -= 1
    
print('YES')