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

import sys
sys.setrecursionlimit(10 ** 9)
sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, M = lr()
A = []
for m in range(M):
    a = ir()
    A.append(a)
C = [0 for _ in range(N+1)]
C[0] = 1
for i in range(len(C)):
    if i in A:
        continue
    if i >= 2:
        C[i] += C[i-2]
    if i >= 1:
        C[i] += C[i-1]

print(C[N] % 1000000007)


### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 9)
sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, M = lr()
A = {i: False for i in range(N+1)}
for m in range(M):
    a = ir()
    A[a] = True
C = [0 for _ in range(N+1)]
C[0] = 1
for i in range(len(C)):
    if A[i]:
        continue
    if i >= 2:
        C[i] += C[i-2]
        C[i] += C[i-1]
        C[i] %= 1000000007
    elif i >= 1:
        C[i] += C[i-1]
        C[i] %= 1000000007

print(C[N] % 1000000007)
### BUGGY CODE ###

ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))


s = input()

n = ii()

for i in range(n):
    q = input().split()

    if(q[0] == '1'):
        # reverse
        s = s[::-1]
    else:
        if(q[1] == '1'):
            s = q[2] + s
        else:
            s = s + q[2]

print(s)


### FIXED CODE ###

ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))


s = input()

n = ii()
r = 0
head = ''
tail = ''
for i in range(n):
    q = input().split()

    if(q[0] == '1'):
        # reverse
        r += 1
    else:
        if(q[1] == '1'):
            if(r%2 ==0):
                # s = q[2] + s
                head = q[2] + head
            else:
                # s = s + q[2]
                tail = tail + q[2]
        else:
            if(r%2 ==0):
                # s = s + q[2]
                tail = tail + q[2]
            else:
                # s = q[2] + s
                head = q[2] + head

    # print('*********************',i,head,tail)
    

if(r%2==1):
    # s = s[::-1]
    # print('rev')
    print( tail[::-1] + s[::-1]+ head[::-1])
else:

    print(head +  s + tail)
### BUGGY CODE ###

def main():
  N, M = map(int, input().split())
  inf =  10**9
  p = 1<<N
  dp = [[inf]*p for _ in range(M+1)]
  for i in range(M+1):
    dp[i][0] = 0
  for i in range(M):
    a, b = map(int, input().split())
    C = list(map(int, input().split()))
    c_bit = sum([1<<(c-1) for c in C])
    for j in range(p):
      #print(min(dp[i][j|c_bit], dp[i][j] + a))
      dp[i+1][j|c_bit] = min(dp[i][j|c_bit], dp[i][j] + a, dp[i+1][j|c_bit])
      dp[i+1][j] = min(dp[i][j], dp[i+1][j])
  if dp[M][2**N-1] == inf:
    print(-1)
  else: 
    print(int(dp[M][2**N-1]))
  
if __name__ == "__main__":
  main()  

### FIXED CODE ###

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

def main():
  for i in range(M):
    a, b = map(int, input().split())
    C = list(map(int, input().split()))
    c_bit = sum([2**(c-1) for c in C])
    for j in range(2**N):
      if dp[i][j] == inf:
        continue
      else:
        #print(min(dp[i][j|c_bit], dp[i][j] + a))
        dp[i+1][j|c_bit] = min(dp[i][j|c_bit], dp[i][j] + a, dp[i+1][j|c_bit])
        dp[i+1][j] = min(dp[i][j], dp[i+1][j])
  if dp[M][2**N-1] == inf:
    print(-1)
  else: 
    print(int(dp[M][2**N-1]))
  
if __name__ == "__main__":
  main()
### BUGGY CODE ###

n, k = map(int, input().split())
list = [int(i) for i in input().split()]
dict = {}
for l in list:
  if l not in dict:
    dict[l]=1
  else:
    dict[l] += 1
if len(dict)<=k:
  print(0)
else:
  sorted_list = sorted(dict.items(), key=lambda x:x[1])
  res = 0
  for i,d in enumerate(sorted_list):
    if len(sorted_list[i:])<=k:
      print(res)
      break
    res += d[1]

### FIXED CODE ###

import collections
n, k = map(int, input().split())
list = input().split()
c_list = collections.Counter(list)
sorted_c_list = sorted(c_list.values(),reverse=True)
print(sum(sorted_c_list[k:]))
### BUGGY CODE ###

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

S = set(s)
c_m = int(0)
l = []

for i in range(len(S)):
    a = S.pop()
    c_i = int(s.count(a))
    if c_i > c_m:
        c_m = c_i
        l = [a]
    elif c_i == c_m:
        l.append(a)

l.sort()
for i in range(len(l)):
  print(l[i])


### FIXED CODE ###

n = int(input())
d = dict()
for _ in range(n):
    x = str(input())
    if x in d:
        d[x] += 1
        continue
    else:
        d[x] = 0

d_sort = sorted(d.items(), key=lambda d:d[1], reverse = True)
d_max = d_sort[0][1]

ans = []
for i in d_sort:
    if d_max == i[1]:
        ans.append(i[0])
    else:
        break

ans.sort()
for a in ans:
    print(a)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=sys.stdin.readline
def resolve():
    n,k=map(int,input().split())
    X=[0]*n
    Y=[0]*n
    for i in range(n):
        X[i],Y[i]=map(int,input().split())
    ans=INF
    from itertools import product
    for a,b in product(range(n),repeat=2):
        for c,d in product(range(a+1,n),range(b+1,n)):
            x0,x1=sorted([X[a],X[c]])
            y0,y1=sorted([Y[b],Y[d]])
            if k<=sum((x0<=X[i]<=x1 and y0<=Y[i]<=y1) for i in range(n)):
                ans=min(ans,(x1-x0)*(y1-y0))
    print(ans)
resolve()

### FIXED CODE ###

import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=sys.stdin.readline
def resolve():
    n,k=map(int,input().split())
    X=[0]*n
    Y=[0]*n
    for i in range(n):
        X[i],Y[i]=map(int,input().split())
    ans=INF
    for a in range(n):
        for b in range(n):
            for c in range(a+1,n):
                for d in range(b+1):
                    x0,x1=sorted([X[a],X[c]])
                    y0,y1=sorted([Y[b],Y[d]])
                    count=0
                    for i in range(n):
                        if x0<=X[i]<=x1 and y0<=Y[i]<=y1:
                            count+=1
                    if count>=k:
                        ans=min(ans,(x1-x0)*(y1-y0))
    print(ans)
resolve()
### BUGGY CODE ###

n = int(input())
l = sorted(list(map(int, input().split())))
cnt = 0
for i in range(n - 2):
    for j in range(i + 1, n - 1):
        c_max = l[i] + l[j]
        for k in range(j + 1, n):
            if l[k] >= c_max:
                c_index = k
                break
        else:
            c_index = n
        cnt += c_index - (j + 1)
print(cnt)


### FIXED CODE ###

import bisect

n = int(input())
l = sorted(list(map(int, input().split())))
cnt = 0
for i in range(n-1, 1, -1):
    for j in range(i - 1, 0, -1):
        c = l[i] - l[j]
        index = bisect.bisect_right(l, c, 0, j)
        cnt += j - index
print(cnt)
### BUGGY CODE ###

s = input()
n = len(s)
dp = [[0]*13 for _ in range(n+1)]
dp[0][0] = 1
d = {(j, k):(10*j+k)%13 for k in range(10) for j in range(13)}
for i in range(n):
  if s[i] != "?":
    t = int(s[i])
    for j in range(13):
      dp[i+1][d[(j, t)]] += dp[i][j]
  else:
    for k in range(10):
      for j in range(13):
        dp[i+1][d[(j, k)]] += dp[i][j]
print(dp[n][5]%(10**9+7))

### FIXED CODE ###

s = input()
n = len(s)
mod = 10**9+7
dp = [[0]*13 for _ in range(n+1)]
dp[0][0] = 1
d = {(j, k):(10*j+k)%13 for k in range(10) for j in range(13)}
for i in range(n):
  if s[i] != "?":
    t = int(s[i])
    for j in range(13):
      dp[i+1][d[(j, t)]] += dp[i][j]
      dp[i+1][d[(j, t)]] %= mod
  else:
    for k in range(10):
      for j in range(13):
        dp[i+1][d[(j, k)]] += dp[i][j]
        dp[i+1][d[(j, k)]] %= mod
print(dp[n][5]%mod)
### BUGGY CODE ###

limit, sum_xyz = map(int, input().split())

pair = list()

for x in range(limit + 1):
    for y in range(limit + 1):
        z = sum_xyz - x - y
        if z < 0 or z > limit:
            continue
        else:
            pair.append([x, y, z])
ans = len(pair)

print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline
 
def main():
    K,S = [int(x) for x in input().split()]
 
    count = 0
 
    for x in range(K+1):
        for y in range(K+1):
            z = S - (x + y)
            if z >= 0 and z <= K:
                count += 1
 
    print(count)
 
if __name__ == '__main__':
    main()
### BUGGY CODE ###

import numpy as np
import sys

L, N = map(int, input().split())
X = np.array([int(sys.stdin.readline()) for _ in range(N)])
Y1 = np.concatenate(([X[0]], X[1:] - X[:-1], [L - X[-1]]))
Y2 = Y1[::-1]


def func(n):
    return np.concatenate((np.full(n + 1, N - n, dtype=np.int), np.arange(N - n - 2, -1, -2), np.arange(N - n - 1, -1, -2)[::-1]))


ans = 0
for n in range(0, (N + 1) // 2):
    a = func(n)
    len1 = np.dot(a, Y1)
    len2 = np.dot(a, Y2)
    ans = max(ans, len1, len2)

print(ans)

### FIXED CODE ###

import numpy as np
import sys

L, N = map(int, input().split())
X = np.array([int(sys.stdin.readline()) for _ in range(N)])
X2 = L - X[::-1]
Y1 = np.concatenate(([X[0]], X[1:] - X[:-1], [L - X[-1]]))
Y2 = Y1[::-1]
Z = np.concatenate((np.arange(N, -1, -2), np.arange(N - 1, -1, -2)[::-1]))


def myfunc(n, x):
    return x[n + (N - n + 1)//2 - 1] - 2 * x[n - 1] - (L - x[N - (N - n + 1)//2])


len1 = np.dot(Z, Y1)
len2 = np.dot(Z, Y2)
x1 = X.tolist()
x2 = X2.tolist()
ans = max(len1, len2)
for n in range(1, (N + 1) // 2):
    len1 += myfunc(n, x1)
    len2 += myfunc(n, x2)
    ans = max(ans, len1, len2)

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

N = int(input())
s = []; count = 0
for i in range(N):
    spell = ''.join(sorted(input()))
    if spell in s:
        count += int(s.count(spell))
    s.append(spell)

print(count)

### FIXED CODE ###

N = int(input())
dic = {}
for i in range(N):
    spell = ''.join(sorted(input()))
    if spell in dic.keys():
        dic[spell] += 1
    else:
        dic[spell] = 1

count = 0
for num in dic.values():
    count += sum([i for i in range(num)])

print(count)
### BUGGY CODE ###

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

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

sum_a = sum(A)
# dc:Divisor Candidate(割る数の候補)
dc_list = [x for x in reversed(range(1, sum_a + 1)) if sum_a % x == 0]

for d in dc_list:
    mods = sorted([a % d for a in A])
    # cs:sumulative sum(累積和)
    mod_cs = [0] * (len(mods) + 1)
    for i, mod in enumerate(mods):
        mod_cs[i + 1] = mod_cs[i] + mod

    for i, mod_cumulative in enumerate(mod_cs):
        minus_op = mod_cumulative
        plus_op = (d * (len(mod_cs) - 1 - i)) - (mod_cs[-1] - mod_cs[i])

        if minus_op == plus_op and minus_op <= K:
            print(d)
            exit(0)
        elif minus_op > K:
            break


### FIXED CODE ###

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

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

sum_a = sum(A)
# dc:Divisor Candidate(割る数の候補)
#dc_list = [x for x in reversed(range(1, sum_a + 1)) if sum_a % x == 0]
dc_list = []
for i in range(1, int(sum_a ** 0.5) + 1):
    if sum_a % i == 0:
        dc_list.append(i)
        if i != sum_a // i:
            dc_list.append(sum_a // i)

dc_list.sort(reverse = True)

for d in dc_list:
    mods = [a % d for a in A]
    mod_sum = sum(mods)
    if mod_sum % d != 0:
        continue
    mods = sorted(mods)

    op = 0
    mod_len = len(mods)
    for i, mod in enumerate(mods):
        op += mod

        if op > K:
            break

        if (mod_len - (i + 1)) * d == mod_sum and op <= K:
            print(d)
            exit(0)
### BUGGY CODE ###


N = int(input())
A = [int(a) for a in input().split()]

def soinsuubunkai(N):
    num_ = N
    list_ = []
    for k in range(2, N+1):
        while True:
            if num_ % k == 0:
                list_.append(k)
                num_ = num_ // k
            else:
                break
    return list_

counter = 0
for a in A:
    tmp = soinsuubunkai(a)
    counter += tmp.count(2)

print(counter)

### FIXED CODE ###


N = int(input())
A = [int(a) for a in input().split()]

counter = 0
for a in A:
    tmp = a
    while True:
        if tmp == 0:
            break
        elif tmp % 2 == 0:
            counter += 1
            tmp = tmp // 2
        else:
            break


print(counter)
### BUGGY CODE ###

import numpy as np
import sys
input = sys.stdin.readline
N = int(input())
a = list(map(int,input().split()))
ma = max(a)
maketa = len(bin(ma))-2
mat = np.zeros((N,maketa))
for i,elem in enumerate(a):
    mat[i] = np.array(list(bin(elem)[2:].zfill(maketa)))
res = 0
mat = mat.T
dic = {}
for i in range(maketa):
    dic[i] = int(np.sum(mat[maketa-i-1]))
for i in range(maketa):
    num = dic[i]
    res += num*(N-num)*(2**(i))
print(res%(10**9+7))


### FIXED CODE ###

N = int(input())
a = list(map(int,input().split()))
ma = max(a)
maketa = len(bin(ma))-2
#print(maketa)
res = 0
dic = {}
for i in range(maketa):
    dic[i] = 0
for i in range(0,maketa):
    num = 0
    for j in range(N):
        #print(a[j] & (2**i))
        dic[i] += int((a[j] & (2**i))>>i)
        #count += 1
for i in range(maketa):
    num = dic[i]
    res += num*(N-num)*(2**(i))
print(res%(10**9+7))
### BUGGY CODE ###

import sys
import heapq as hq
input = sys.stdin.readline
n = int(input())
x_xy = []
y_xy = []
for i in range(n):
  x,y = map(int,input().split())
  x_xy.append([x,i+1])
  y_xy.append([y,i+1])
x_xy.sort()
y_xy.sort()
edge = [[] for i in range(n+1)]
for i in range(1,n):
  xf,v2 = x_xy[i]
  xi,v1 = x_xy[i-1]
  edge[v1].append([abs(xf-xi),v2])
  edge[v2].append([abs(xf-xi),v1])
  yf,v2 = y_xy[i]
  yi,v1 = y_xy[i-1]
  edge[v1].append([abs(yf-yi),v2])
  edge[v2].append([abs(yf-yi),v1])
edges = edge[1]
hq.heapify(edges)
connect = [0 for i in range(n+1)]
connect[1] = 1
ans = 0
while edges:
  cost,v2 = hq.heappop(edges)
  if connect[v2] == 1:
    continue
  ans += cost
  connect[v2] = 1
  for e in edge[v2]:
    hq.heappush(edges,e)
print(ans)

### FIXED CODE ###

import sys
from scipy.sparse.csgraph import minimum_spanning_tree
from scipy.sparse import csr_matrix
input = sys.stdin.readline
n = int(input())
xy = [list(map(int,input().split()))+[i] for i in range(n)]
evv = set()
for Key in range(2):
  xy_s = sorted(xy,key = lambda x:x[Key])
  for i in range(1,n):
    evv.add((xy_s[i][2],xy_s[i-1][2],min(abs(xy_s[i-1][0]-xy_s[i][0]),abs(xy_s[i-1][1]-xy_s[i][1]))))
v1,v2,edge = zip(*evv)
csr = csr_matrix((edge,(v1,v2)),shape = (n,n))
mst = minimum_spanning_tree(csr)
print(int(mst.sum()))
### BUGGY CODE ###

from collections import deque

n = int(input())

q = deque()

list2 = [input().split(" ") for _ in range(n)]

for lst in list2:

	if lst[0] == "insert":
		q.appendleft(int(lst[1]))
	elif lst[0] == "delete":
		try:
			q.remove(int(lst[1]))
		except:
			pass

	elif lst[0] == "deleteFirst":
		q.popleft()
	elif lst[0] == "deleteLast":
		q.pop()

print(*q)



### FIXED CODE ###

from collections import deque
from sys import stdin

n = int(input())

q = deque()

for _ in range(n):
	cmd = stdin.readline().strip().split()
	if cmd[0] == "insert":
		q.appendleft(cmd[1])
	elif cmd[0] == "deleteFirst":
		q.popleft()
	elif cmd[0] == "deleteLast":
		q.pop()
	elif cmd[0] == "delete":
		try:
			q.remove(cmd[1])
		except:
			pass

print(*q)
### BUGGY CODE ###

n, m = [int(i) for i in input().split()]
pre = []
year = []
year_order = [0 for i in range(m)]
each_arr = [[] for i in range(n)]
each_sort = [[] for i in range(n)]

for i in range(m):
    p, y = [int(i) for i in input().split()]
    pre.append(p)
    year.append(y)


for i in range(m):
    each_arr[pre[i]-1].append(year[i])

for j in range(n):
    each_sort[j] = sorted(each_arr[j])

for i in range(m):
    year_order[i] = each_sort[pre[i]-1].index(each_arr[pre[i]-1][0])+1
    each_arr[pre[i]-1].remove(each_arr[pre[i]-1][0])

for i in range(m):
    print("{0:06d}".format(pre[i])+"{0:06d}".format(year_order[i]))

### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

N, M = map(int, input().split())
L = []
for i in range(M):
    P, Y = map(int, input().split())
    L.append([P, Y, i])

L = sorted(L)

reset = 0
count = 0
ans = []
for i in range(M):
    if L[i][0] != reset:
        reset = L[i][0]
        count = 1
    else:
        count += 1
    
    ans.append([L[i][2], str(reset).zfill(6) + str(count).zfill(6)])

ans = sorted(ans)

for i in range(M):
    print(ans[i][1])
### BUGGY CODE ###

S = input().split(" ")
N = int(S[0])
M = int(S[1])

def calculate(n,m):
    result = []
    for i in range(n):
        for j in range(m):
            count = 0
            if i - 1 >=0:
                count = count + 1

            if i + 1 <= n - 1:
                count = count + 1

            if j - 1 >= 0:
                count = count + 1

            if j + 1 <= m - 1:
                count = count + 1

            if (i -1 >= 0) and (j-1 >= 0):
                count = count + 1

            if (i - 1 >= 0) and (j + 1 <= m - 1):
                count = count + 1

            if (i + 1 <= n - 1) and (j - 1 >= 0):
                count = count + 1

            if (i + 1 <= n - 1) and (j + 1 <= m - 1):
                count = count + 1


            result.append((count+1) % 2)

    print(sum(result))
calculate(N,M)

### FIXED CODE ###

S = input().split(" ")
N = int(S[0])
M = int(S[1])

def calculate(n,m):

    if n == 1 and m == 1:
        return 1

    if n == 1:
        return m - 2

    if m == 1:
        return n - 2

    return (n - 2) * (m - 2)
result = calculate(N,M)
print(result)
### BUGGY CODE ###

n=int(input())
a=[input() for i in range(n)]
b=list(set(a))
c=[]
d=0
for i in b:
  if a.count(i)>d:
    c=[i]
    d=a.count(i)
  elif a.count(i)==d:
    c+=[i]
c.sort()
for i in c:
  print(i)


### FIXED CODE ###

n=int(input())
dict={}
xs=[]
for i in range(n):
  s=input()
  xs+=[s]
  if s not in dict:
    dict[s]=1
  else:
    dict[s]+=1
pin=0
xs=list(set(xs))
for i in xs:
  pin=max(pin,dict[i])
ans=[]
for i in xs:
  if dict[i]==pin:
    ans+=[i]
ans.sort()
for i in ans:
  print(i)
### BUGGY CODE ###

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


for i in range(k):
    b = [0] * (n+1)
    for j in range(n):
        l = max(0, j-a[j])
        r = min(n, j+a[j]+1)
        b[l] += 1
        b[r] -= 1
    for j in range(n):
        b[j+1] += b[j]
    b.pop()
    if a == b:
        print(' '.join(map(str, a)))
        exit()
    a = b
print(' '.join(map(str, a)))

### FIXED CODE ###

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


for i in range(k):
    b = [0] * (n+1)
    for j in range(n):
        l = max(0, j-a[j])
        r = min(n, j+a[j]+1)
        b[l] += 1
        b[r] -= 1
    for j in range(n):
        b[j+1] += b[j]
    b.pop()
    if a == b:
        break
    a = b
print(' '.join(map(str, a)))
### BUGGY CODE ###

s=list(input())
n=len(s)
mod=10**9+7
dp=[[0]*13 for j in range(100005)]
dp[0][0]=1
for i in range(n):
    if s[i]=="?":
        for j in range(10):
            for k in range(13):
                dp[i+1][(k*10+j)%13]+=dp[i][k]
        for j in range(13):
            dp[i+1][j]%=mod
    else:
        for k in range(13):
            dp[i+1][(k*10+int(s[i]))%13]+=dp[i][k]
        for j in range(13):
            dp[i+1][j]%=mod
print(dp[n][5])


### FIXED CODE ###

s=list(input())
n=len(s)
mod=10**9+7
dp=[[0]*13 for j in range(100005)]
dp[0][0]=1
for i in range(n):
    if s[i]=="?":
        for j in range(10):
            for k in range(13):
                dp[i+1][(k*10+j)%13]+=dp[i][k]
        for j in range(13):
            dp[i+1][j]%=mod
    else:
        for k in range(13):
            dp[i+1][(k*10+int(s[i]))%13]+=dp[i][k]
        for j in range(13):
            dp[i+1][j]%=mod
print(dp[n][5])
### BUGGY CODE ###

S = input()
pre, post = [], []
Q = int(input())
reversed = False
for _ in range(Q):
  query = input().split()
  if query[0] == '1':
    reversed = not reversed
    pre, post = post, pre
  else:  # query[0] == 2
    F, C = query[1:]
    if F == '1':
      if reversed:
        pre.append(C)
      else:
        pre = [C] + pre
    else:  # F == '2'
      if reversed:
        post = [C] + post
      else:
      	post.append(C)
if reversed:
  print(''.join(pre[::-1]) + S[::-1] + ''.join(post[::-1]))
else:
  print(''.join(pre) + S + ''.join(post))

### FIXED CODE ###

from collections import deque

S = input()
pre, post = deque(), deque()
Q = int(input())
reversed = False
for _ in range(Q):
  query = input().split()
  if query[0] == '1':
    reversed = not reversed
    pre, post = post, pre
  else:  # query[0] == 2
    F, C = query[1:]
    if F == '1':
      if reversed:
        pre.append(C)
      else:
        pre.appendleft(C)
    else:  # F == '2'
      if reversed:
        post.appendleft(C)
      else:
      	post.append(C)
if reversed:
  print(''.join(pre)[::-1] + S[::-1] + ''.join(post)[::-1])
else:
  print(''.join(pre) + S + ''.join(post))
### BUGGY CODE ###

import numpy as np
import sys
N, D, A = map(int, input().split())
L = 2 * D
I = np.array(sys.stdin.read().split(), np.int32)
X = I[::2]
H = I[1::2]
sort_ind = np.argsort(X)
X = X[sort_ind]
H = H[sort_ind]
S = np.zeros(N+1, np.int32)

atack = 0
ans = 0
for i in range(N):
	atack += S[i]
	H[i] -= atack
	if H[i] > 0:
		atack_cnt = -(-H[i]//A)
		ans += atack_cnt
		S[i+1] += atack_cnt * A
		ind = np.searchsorted(X,X[i]+L+1,side = 'left')
		S[ind] -= atack_cnt * A

print(ans)

### FIXED CODE ###

import numpy as np
import sys
N, D, A = map(int, input().split())
L = 2 * D
I = np.array(sys.stdin.read().split(), np.int64)
X = I[::2]
H = I[1::2]
sort_ind = np.argsort(X)
X = X[sort_ind]
H = H[sort_ind]
S = np.zeros(N+1, np.int64)
ind = np.searchsorted(X,X+L+1,side = 'left')

atack = 0
ans = 0
for i in range(N):
	atack += S[i]
	H[i] -= atack
	if H[i] > 0:
		atack_cnt = -(-H[i]//A)
		ans += atack_cnt
		tmp = atack_cnt * A
		S[i+1] += tmp
		S[ind[i]] -= tmp

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

import sys
input = sys.stdin.readline

H, W, M = map(int, input().split())

H_list = [0] * (H + 1)
W_list = [0] * (W + 1)


S = set()
INF = 10 ** 6

for _ in range(M):
    a, b = map(int, input().split())
    tmp = INF * a + b
    S.add(tmp)
    H_list[a] += 1
    W_list[b] += 1

ans = 0
for h in range(1, H + 1):
    for w in range(1, W + 1):
        tmp = H_list[h] + W_list[w]
        if INF * h + w in S:
            tmp -= 1
        ans = max(ans, tmp)

print (ans)


### FIXED CODE ###

def main():
    import sys
    input = sys.stdin.readline

    H, W, M = map(int, input().split())

    H_list = [[0, i] for i in range(H + 1)] 
    W_list = [[0, i] for i in range(W + 1)] 


    S = set()
    S_add = S.add
    INF = 10 ** 6

    for _ in range(M):
        a, b = map(int, input().split())
        tmp = INF * a + b
        S_add(tmp)
        H_list[a][0] += 1
        W_list[b][0] += 1

    ans = 0
    H_list.sort(reverse=True)
    W_list.sort(reverse=True)

    tmp_H = H_list[0][0]
    tmp_W = W_list[0][0]
    tmp_ans = tmp_H + tmp_W

    for h in range(H):
        if H_list[h][0] + 1 < tmp_H:
            continue
        h_ = H_list[h][1]
        H_ = H_list[h][0]
        for w in range(W):
            if W_list[w][0] + H_ + 1 < tmp_ans:
                break
            w_ = W_list[w][1]
            tmp = H_ + W_list[w][0]
            if INF * h_ + w_ in S:
                tmp -= 1
            ans = max(ans, tmp)
            if ans == tmp_ans:
                print (ans)
                return

    print (ans)

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

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

for i in range(m):
  a=sorted(a)
  a[n-1]=a[n-1]/2
  
ans=0
for j in range(n):
  ans=ans+int(a[j])
  
print(ans)

### FIXED CODE ###

import heapq	

n,m=map(int,input().split())
a=list(map(int,input().split()))
hq=[]
for i in range(len(a)):
  heapq.heappush(hq,-a[i])

if n==1:
  for i in range(m):
    hq[0]=(((-1)*hq[0])//2)*(-1)
else:
  for i in range(m):
    v=heapq.heappop(hq)
    heapq.heappush(hq,((v*-1)//2)*(-1))

ans=0
for i in range(len(hq)):
  ans=ans+(-1)*heapq.heappop(hq)

print(ans)