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

from sys import stdin
input = stdin.readline
MOD = 998244353


def solve():
    N,K = map(int,input().split())
    step = [tuple(map(int,inp.split())) for inp in stdin.read().splitlines()]
    # @lru_cache(None)
    # def dp(n):
    #     if n == 1:
    #         return 1
    #     res = 0
    #     for a,b in step:
    #         if n <= a:
    #             continue
    #         for i in range(a,b+1):
    #             if n > i:
    #                 res += dp(n-i)
    #     return res % MOD
    #
    # print(dp(N))

    dp = [0] * (N+1)
    dp[1] = 1
    for i in range(2,N+1):
        for a,b in step:
            if i <= a:
                continue
            for j in range(a,b+1):
                if i > j:
                    dp[i] += dp[i-j]
        dp[i] %= MOD
    print(dp[N])



if __name__ == '__main__':
    solve()


### FIXED CODE ###

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

def solve():
    n,K = map(int,input().split())
    step = [tuple(map(int,inp.split())) for inp in stdin.read().splitlines()]
    dp=defaultdict(int)

    f=0
    dp[1]=1
    for i in range(1,1+n):
        for r,l in step:
            f=(f+-dp[i-1-l]+dp[i-r])%mod
        dp[i]=(dp[i]+f)%mod
    print(dp[n])



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

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

BC = [list(map(int, input().split())) for _ in range(M)]

BC.sort(reverse = True, key=lambda x : x[1])

for b, c in BC:
    A.sort()
    for j in range(b):
        if A[j] >= c:
            break
        A[j] = c
    else:
        continue
    break
print(sum(A))


### FIXED CODE ###

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

BC = [list(map(int, input().split())) for _ in range(M)]

A.sort()
BC.sort(reverse = True, key=lambda x : x[1])

index = -1
for b, c in BC:
    for _ in range(b):
        index += 1
        if index >= N:
            break
        if A[index] >= c:
            break
        A[index] = c
    else:
        continue
    break
print(sum(A))
### BUGGY CODE ###

X = int(input())
diff = 1
for i in range(2,X):
    if X % i == 0:
        diff = i
        break

s = (10 **9)//2
while True:
    ss = s/2
    A = ss 
    B = ss - diff
    xx = A ** 5 - B ** 5
    if xx == X:
        break
    elif xx > X:
        s = ss //2
    else:
        s =  (3*ss) //4
print(int(A),int(B))

### FIXED CODE ###

def main():
    X = int(input())
    for B in range(-120,121):
        for A in range(B,121):
            xx = A**5 -B ** 5
            if X ==  xx:
                print(A,B)
                return
            elif X <xx:
                break

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

from operator import mul
from functools import reduce

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

def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under

ax = cmb(N, a)
bx = cmb(N, b)

sum = pow(2, N)

print((sum - ax - bx - 1)%10000000)

### FIXED CODE ###

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

MOD = 10**9+7

def modcmb(n, r, m):
    x = 1
    y = n
    for i in range(2,r+1):
        x *= i
        x %= MOD
        y *= n-i+1
        y %= MOD
    return y * pow(x, m-2, m) % m

ans = pow(2, N, MOD) - modcmb(N, a, MOD) - modcmb(N, b, MOD) - 1
print(ans % MOD)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
A.sort()
A.reverse()
que = []

def solve(i):
    if len(que) >=  2:
        return True
    num = A[i]
    check = num in que
    if A.count(num) > 3:
        que.append(num)
        que.append(num)
    elif A.count(num) > 1 and check == False:
        que.append(num)
    if i == N - 1:
        return False
    else:
        return solve(i+1)

a = solve(0)
if a == True:
    ans = que[0] * que[1]
    print(ans)
else:
    print(0)


### FIXED CODE ###

from collections import Counter

N = int(input())
A = list(map(int, input().split()))
c_dict = Counter(A)
B = []
C = []

for k, v in c_dict.items():
    if v >= 4:
        B.append(k)
    elif v >= 2:
        C.append(k)
B.sort(reverse=True)
C.sort(reverse=True)

if len(B) < 1 and len(C) < 2:
    print(0)
elif len(B) < 1 and len(C) >= 2:
    F = C[1] * C[0]
    print(F)
elif len(B) >= 1 and len(C) == 1:
    D = B[0] ** 2
    E = C[0] * B[0]
    print(max(D, E))
elif len(B) >= 1 and len(C) >= 2:
    D = B[0] ** 2
    E = C[0] * B[0]
    F = C[1] * C[0]
    print(max(D, E, F))
### BUGGY CODE ###

N, M = [int(i) for i in input().split()]
A = [int(i) for i in input().split()]

# sa = sorted(A)[::-1]

da = []

cnt = 0

for i in range(N):
    for j in range(N):
        # if cnt > M:
        #     break
        da.append(A[i] + A[j])
        cnt += 1


sa = sorted(da)[::-1]

# print(N)
# print(M)
# print(A)

print(sum(sa[:M]))

### FIXED CODE ###

N, M = [int(i) for i in input().split()]
A = [int(i) for i in input().split()]

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

# print(len(A))

max_p = max(A)

X = max_p



cnt = [0 for x in range(100001)]
hpp = [0 for x in range(100001)]


# print(A)

for i in A:
    # print(i)
    # if cnt[i] != 0:
    #     continue
    cnt[i] += 1
    hpp[i] += i
# print(cnt[:100])

for i in range(1, 100001)[::-1]:
    cnt[i - 1] += cnt[i]
    hpp[i - 1] += hpp[i]

def countpair(left, x):
    # return cnt[x - left + 1] if (x - left > 0) else N
    if x - left <= 0:
        return N
    elif x - left > 100000:
        return 0
    else:
        return cnt[x - left]

def get_hpp(left, x):
    if x - left <= 0:
        return hpp[0]
    elif x - left > 100000:
        return 0
    else:
        return hpp[x - left]
# print(hpp[:100])


# print(cnt[:100])

small = 0
large = max_p * 2
threshold = 0
# d_c = 0

# mems = []

while (small <= large):
    # d_c += 1
    # print(small, large)
    X = (small + large) // 2

    nums = 0
    for i in range(N):
        left = A[i]
        # print(len(A))
        nums += countpair(left, X)

    if nums >= M:
        threshold = X
        small = X + 1
    else:
        large = X - 1

X = threshold

# print("X:", X)
# print("threshold:", threshold)

Y = X + 1

hpp_sum = 0
num_sum = 0

for i in range(N):
    # print("-----------")
    left = A[i]
    cnt_num = countpair(left, Y)
    num_sum += cnt_num
    # print("left:", left)
    # print("cnt_num:", cnt_num)
    hpp_sum += left * cnt_num
    # print("get_hpp:", get_hpp(left, Y))
    hpp_sum += get_hpp(left, Y)
    # print("hpp_sum:", hpp_sum)


hpp_sum += X * (M - num_sum) if (M - num_sum > 0) else 0

print(hpp_sum)


# print(out)

# for i in range(N):
### BUGGY CODE ###

#!/usr/bin/env python
#-*- coding:utf-8 -*-
import heapq

while True:
	# 割引券，駅，路線，スタート，ゴール
	c, n, m, s, d = map(int, raw_input().split())
	if not (c or n or m or s or d): break
	field = {}
	for i in xrange(m):
		a, b, f = map(int, raw_input().split())
		field[(a, b)] = f;
		field[(b, a)] = f;
	visited = {}
	q = []
	heapq.heappush(q, (0, c, s))
	while q:
		cost, rem, pos = heapq.heappop(q)
		if pos == d:
			print cost
			break
		for i in xrange(1, n + 1):
			edge = (pos, i)
			if edge in field:
				next = (rem, i)
				ncost = cost + field[edge]
				if not next in visited or visited[next] < ncost:
					heapq.heappush(q, (ncost, rem, i))
					visited[next] = ncost
				if rem > 0:
					next = (rem - 1, pos)
					ncost = cost + field[edge] / 2
					if not next in visited or visited[next] < ncost:
						heapq.heappush(q, (ncost, rem - 1, i))
						visited[next] = ncost

### FIXED CODE ###

#!/usr/bin/env python
#-*- coding:utf-8 -*-
import heapq

while True:
	# 割引券，駅，路線，スタート，ゴール
	c, n, m, s, d = map(int, raw_input().split())
	if not (c or n or m or s or d): break
	field = {}
	for i in xrange(m):
		a, b, f = map(int, raw_input().split())
		field[(a, b)] = field[(b, a)] = f;
	visited = {}
	q = []
	heapq.heappush(q, (0, c, s))
	while q:
		cost, rem, pos = heapq.heappop(q)
		if pos == d:
			print cost
			break
		for i in xrange(1, n + 1):
			edge = (pos, i)
			next = (rem, i)
			ncost = cost + field.get(edge, 0x7fffffff)
			if ncost < visited.get(next, 0x7fffffff):
				heapq.heappush(q, (ncost, rem, i))
				visited[next] = ncost
			next = (rem - 1, i)
			ncost = cost + field.get(edge, 0x7fffffff) / 2
			if rem > 0 and ncost < visited.get(next, 0x7fffffff):
				heapq.heappush(q, (ncost, rem - 1, i))
				visited[next] = ncost
### BUGGY CODE ###


class UnionFind(object):

    def __init__(self, N):
        self._tree = [i for i in range(N)]
        self._rank = [0] * (N + 1)

    def find(self, x):
        if self._tree[x] == x:
            return x
        else:
            self._tree[x] = self.find(self._tree[x])
            return self._tree[x]

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)

        # ランクを考慮しない場合はどちらが親になっても良い
        if self._rank[x] < self._rank[y]:
            self._tree[x] = y
        else:
            self._tree[y] = x

        if self._rank[x] == self._rank[y]:
            self._rank[x] += 1

    def has_same_parent(self, x, y):
        return self.find(x) == self.find(y)


N, M = map(int, input().split())
A_B = [tuple(map(int, input().split())) for _ in range(M)]


def calc_inconvenience(unionfind, N):
    inconvenience = 0
    for i in range(1, N + 1):
        for j in range(i + 1, N + 1):
            if not unionfind.has_same_parent(i, j):
                inconvenience += 1
    return inconvenience


result = list()
unionfind = UnionFind(N + 1)
for a, b in reversed(A_B):
    result.append(calc_inconvenience(unionfind, N))
    unionfind.unite(a, b)
for r in reversed(result):
    print(r)




### FIXED CODE ###

class UnionFind(object):

    def __init__(self, N):
        self._tree = [i for i in range(N)]
        self._rank = [0] * (N + 1)
        self.size = [1] * N
        self.inconvenience = N * (N - 1) // 2

    def find(self, x):
        if self._tree[x] == x:
            return x
        else:
            self._tree[x] = self.find(self._tree[x])
            return self._tree[x]

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        self.inconvenience -= self.size[x] * self.size[y]
        if self._rank[x] < self._rank[y]:
            self._tree[x] = y
            self.size[y] += self.size[x]
        else:
            self._tree[y] = x
            self.size[x] += self.size[y]

        if self._rank[x] == self._rank[y]:
            self._rank[x] += 1


N, M = map(int, input().split())
A_B = [tuple(map(int, input().split())) for _ in range(M)]

result = list()
uf = UnionFind(N)
for a, b in reversed(A_B):
    result.append(max(0, uf.inconvenience))
    uf.unite(a - 1, b - 1)
for r in reversed(result):
    print(r)
### BUGGY CODE ###

import math

K = int(input())
res=0
for a in range(1,K+1):
    for b in range(1,K+1):
        for c in range(1,K+1):
            #print(a,b,c)
            tmp = (math.gcd(math.gcd(a,b),c))
            res += tmp
print(res)

### FIXED CODE ###

import math

K = int(input())
res=0
for a in range(1,K+1):
    for b in range(1,K+1):
        tmp = math.gcd(a,b)
        for c in range(1,K+1):
            #print(a,b,c)
            res += math.gcd(tmp,c)
print(res)
### BUGGY CODE ###

from collections import deque

h,w=map(int,input().split())
s=[list(input()) for i in range(h)]

q=deque()
ans=0

def bfs(i,j):
    global ans
    q.append((i,j))
    while q:
        y,x=q.popleft()
        if s[y][x]=='#':
            ans+=1
        for dy,dx in ((1,0),(0,1),(-1,0),(0,-1)):
            ny = y+dy
            nx = x+dx
            if 0<=ny<h and 0<=nx<w and s[y][x]!=s[ny][nx] and field[ny][nx]==False:
                field[ny][nx]=True
                q.append((ny,nx))

                         
for i in range(h):
    for j in range(w):
        if s[i][j]=='.':
            field=[[False]*w for j in range(h)]
            field[i][j]=True
            bfs(i,j)

print(ans)

### FIXED CODE ###

from collections import deque

h,w=map(int,input().split())
s=[list(input()) for i in range(h)]

q=deque()
ans=0

def bfs(i,j):
    global ans
    white=0
    black=0
    q.append((i,j))
    while q:
        y,x=q.popleft()
        if s[y][x]=='#':
            black+=1
        if s[y][x]=='.':
            white+=1
        for dy,dx in ((1,0),(0,1),(-1,0),(0,-1)):
            ny = y+dy
            nx = x+dx
            if 0<=ny<h and 0<=nx<w and s[y][x]!=s[ny][nx] and field[ny][nx]==False:
                field[ny][nx]=True
                q.append((ny,nx))
    ans+=(black*white)

field=[[False]*w for j in range(h)]                         
for i in range(h):
    for j in range(w):
        if s[i][j]=='.' and field[i][j]==False:
            field[i][j]=True
            bfs(i,j)

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

# TODO D - Cake 123
# https://atcoder.jp/contests/abc123/tasks/abc123_d

X, Y, Z, K = map(int, raw_input().split())

A = map(int,raw_input().split())
B = map(int,raw_input().split())
C = map(int,raw_input().split())

AB = sorted([a+b for a in A for b in B], reverse=True)
ABC = sorted([ab + c for ab in AB[:K] for c in C], reverse=True)

for i in ABC[:K]:
    print '{}'.format(i)


### FIXED CODE ###

#abc123d
 
x,y,z,k=map(int,raw_input().split())
a=sorted(map(int,raw_input().split()),reverse=True)
b=sorted(map(int,raw_input().split()),reverse=True)
c=sorted(map(int,raw_input().split()),reverse=True)
 
ab=sorted([i+j for i in a for j in b],reverse=True)
res=sorted([ij+l for ij in ab[:k] for l in c],reverse=True)
for i in res[:k]:
	print i
### BUGGY CODE ###

N = int(input())
S = list(input())

ans = []
for i in range(N-2):
    for j in range(i+1,N-1):
        for k in range(j+1,N):
            ans.append(S[i]+S[j]+S[k])
ans_set = set(ans)
print(len(ans_set))

### FIXED CODE ###

N = int(input())
S = list(input())

ans = []
a1 = []
for i in range(N-2):
    if S[i] in a1:continue
    a1.append(S[i])
    a2 = []
    for j in range(i+1,N-1):
        if S[j] in a2:continue
        a2.append(S[j])
        a3 = []
        for k in range(j+1,N):
            if S[k] in a3:continue
            a3.append(S[k])
            ans.append(S[i]+S[j]+S[k])
ans_set = set(ans)
print(len(ans_set))
### BUGGY CODE ###

N = int(input())
data = []
for _ in range(N):
	A = int(input())
	items = []
	for __ in range(A):
		x, y = map(int, input().split())
		items.append((x - 1, y))
	data.append(items)
 
best = 0
 
def check(i):
    for j in range(N):
        if ((i >> j) & 1) == 1:           
            for x, y in data[j]:
                if y !=((i >> x) & 1):return False						
    return True
 
for i in range(1 << 2**N):
    if check(i):
        count=0
        for j in range(N):
            count += ((i >> j) & 1)
        if count > best:best = count
	
print(best)

### FIXED CODE ###

N = int(input())
data = []
for _ in range(N):
	A = int(input())
	items = []
	for __ in range(A):
		x, y = map(int, input().split())
		items.append((x - 1, y))
	data.append(items)
 
best = 0
 
def check(i):
    for j in range(N):
        if ((i >> j) & 1) == 1:           
            for x, y in data[j]:
                if y !=((i >> x) & 1):return False						
    return True
 
for i in range(2**N):
    count=0
    for j in range(N):count += ((i >> j) & 1)
    if count>best:
        if check(i):best = count
	
print(best)
### BUGGY CODE ###

import networkx as nx
room, route_count = map(int,input().split())

G = nx.Graph()
G.add_nodes_from(range(1,room+1))
G.add_edges_from([list(map(int,input().split())) for _ in range(route_count)])

is_end = False
for i in range(2, room+1):
  if nx.has_path(G,source=i, target=1)==False:
    is_end = True
    break

if is_end:
  print('No')
else:
  print('Yes')
  shortest_path_dict = nx.single_target_shortest_path(G, target=1)
  for i in range(2,room+1):
    print(shortest_path_dict[i][1])


### FIXED CODE ###

import networkx as nx
room, route_count = map(int,input().split())
route = [list(map(int,input().split())) for _ in range(route_count)]

G = nx.Graph()
G.add_nodes_from(range(1,room+1))
G.add_edges_from(route)
pre = nx.predecessor(G, 1)

print('Yes')
for i in range(2,room+1):
  print(pre[i][0])
### BUGGY CODE ###

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

l = []
l.append(a[0])
cou =[]



for i in range(1,n):
    b = a[i]
    for j in range(len(l)):
      if b==l[j]:
        cou.append(b)
        break
      if b%l[j]==0:
        break
    else:
      l.append(b)

print(len(l)-len(set(cou)))


### FIXED CODE ###

counter = [0 for i in range(10**6+1)]
n = int(input())
a = sorted(list(map(int,input().split())))
for i in a:
  counter[i] += 1
l  = [0 for i in range(10**6+1)]
cou = 0
for i in range(n):
  b = a[i]
  if l[b]==0:
    cou += 1
    for j in range(b,10**6+1,b):
      l[j] = 1
    if counter[b]>=2:
      cou -=1
print(cou)
### BUGGY CODE ###

from collections import deque
import itertools

H, W = map(int, input().split())
C_h, C_w = map(int, input().split())
D_h, D_w = map(int, input().split())

S = [input() for _ in range(H)]
dist = [[-1 for i in range(W)] for j in range(H)]
dist[C_h-1][C_w-1] = 0

d = deque([[C_h-1, C_w-1, 0]])

def check_movable(h, w):
    if h < 0 or h >= H or w < 0 or w >= W:
        return False
    if S[h][w] == "#":
        return False
    else:
        return True

def check_appnendable(h, w, cost):
    if not check_movable(h,w):
        return False
    if dist[h][w] == -1:
        return True
    elif dist[h][w] > cost:
        return True
    else:
        return False

dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
while d:
    h, w, cost = d.pop()
    for dh, dw in zip(dx, dy):
        if check_appnendable(h+dh, w+dw, cost):
            d.append([h+dh, w+dw, cost])
            dist[h+dh][w+dw] = cost
    for dh, dw in itertools.product(range(-2, 3), range(-2, 3)):
        if check_appnendable(h+dh, w+dw, cost+1):
            d.appendleft([h+dh, w+dw, cost+1])
            dist[h+dh][w+dw] =cost+1

print(dist[D_h-1][D_w-1])

### FIXED CODE ###

from collections import deque

H, W = map(int, input().split())
C_h, C_w = map(int, input().split())
D_h, D_w = map(int, input().split())

S = [input() for _ in range(H)]
dist = [[float("inf") for i in range(W)] for j in range(H)]
dist[C_h-1][C_w-1] = 0

d = deque([[C_h-1, C_w-1, 0]])

def check_movable(h, w):
    if h < 0 or h >= H or w < 0 or w >= W:
        return False
    if S[h][w] == "#":
        return False
    else:
        return True

def check_appnendable(h, w, cost):
    if not check_movable(h,w):
        return False
    if dist[h][w] > cost:
        return True
    else:
        return False

dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
while d:
    h, w, cost = d.pop()
    for dh, dw in zip(dx, dy):
        if check_appnendable(h+dh, w+dw, cost):
            d.append([h+dh, w+dw, cost])
            dist[h+dh][w+dw] = cost
    for dh in range(-2, 3):
        for dw in range(-2, 3):
            if check_appnendable(h+dh, w+dw, cost+1):
                d.appendleft([h+dh, w+dw, cost+1])
                dist[h+dh][w+dw] =cost+1

if dist[D_h-1][D_w-1] < float("inf"):
    print(dist[D_h-1][D_w-1])
else:
    print(-1)
### BUGGY CODE ###

#!/usr/bin/env python3

def solve(x):
    if x >= 2000:
        return True
    memo = [True] + [False]*x

    def dp(k):
        if k == 0:
            return True
        elif k < 0:
            return False
        elif memo[k]:
            return True
        for i in range(100,106):
            if dp(k-i):
                return True
        
        return False
    
    for i in range(x):
        memo[i+1] = dp(i+1)
    return memo[x]



def main():
    X = int(input())
    print(int(solve(X)))
    return

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3

def solve(x):
    if x >= 2000:
        return True
    memo = [True] + [False]*x

    def dp(k):
        if k == 0:
            return True
        for i in range(100,106):
            if k-i >= 0 and memo[k-i]:
                return True
        
        return False
    
    for i in range(x):
        memo[i+1] = dp(i+1)
    return memo[x]



def main():
    X = int(input())
    print(int(solve(X)))
    return

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

n = int(input())
 
str = input()
sum = 0
ans = []
for i in range(n):
  if str[i] == "R":
    ans.append(2)
  elif str[i] == "G":
    ans.append(3)
  else:
    ans.append(5)

for i in range(n-2):
  for j in range(i+1, n-1):
    for k in range(j+1, n):
      if ans[i] - ans[j] == 0:
        break
      elif j - i == k - j:
        pass
      elif ans[i] + ans[j] + ans[k] == 10:
        sum += 1
print(sum)

### FIXED CODE ###

n = int(input())
 
str = input()

r = str.count('R')
g = str.count('G')
b = str.count('B')
sum = r * g * b
for i in range(n-2):
  for j in range(i+1, n-1):
    k = 2 * j - i
    if k < n:
      if str[i] != str[j] and str[i] != str[k] and str[j] != str[k] :
        sum -= 1
    
print(sum)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**9)

X, Y = map(int, input().split())

def rec(x, y) :
    flg = False
    for i in range(2, x + 1, 2) :
        flg = flg or not rec(x-i, y+i//2)
    for i in range(2, y + 1, 2) :
        flg = flg or not rec(x+i//2, y-i)
        
    return flg
    
if rec(X, Y) :
    print('Alice')
else :
    print('Brown')

### FIXED CODE ###

X, Y = map(int, input().split())

if abs(X-Y) <= 1 :
    print('Brown')
else :
    print('Alice')
### BUGGY CODE ###

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on Fri Mar 23 11:18:48 2018

@author: natsukiiwano
"""

_in_ = list(map(int,input().split(" ")))
H,W,D = _in_[0],_in_[1],_in_[2]
dic = {}
for h in range(H):
    _in_ = list(map(int,input().split(" ")))
    for w in range(W):
        dic[_in_[w]]=h+w*1j


for n in range(H*W-D):
    dic[n+1] = int(abs(dic[n+1].real-dic[n+1+D].real)+abs(dic[n+1].imag-dic[n+1+D].imag))
        
for q in range(int(input())):
    _in_ = list(map(int,input().split(" ")))
    _from_,_to_ = _in_[0],_in_[1]
    _sum_=0
    while _to_ != _from_:
        _sum_ = _sum_ + dic[_from_]
        _from_ = _from_ + D
    print(_sum_)

### FIXED CODE ###

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on Fri Mar 23 12:24:26 2018

@author: natsukiiwano
"""
import numpy as np

_in_ = input().split(" ")
H,W,D = int(_in_[0]),int(_in_[1]),int(_in_[2])

px,py= np.zeros(90001),np.zeros(90001)
d=np.zeros(90001)
for i in range(H):
    _in_ = list(map(int,input().split(" ")))
    for j in range(W):
        px[_in_[j]]=i
        py[_in_[j]]=j

for i in range(D+1,H*W+1):
    d[i]=d[i-D]+abs(px[i]-px[i-D])+abs(py[i]-py[i-D])

Q = int(input())
for i in range(Q):
    _in_ = input().split(" ")
    L,R = int(_in_[0]),int(_in_[1])
    print(int(d[R]-d[L]))
### BUGGY CODE ###

import sys
def input():
    return sys.stdin.readline().strip()
 
def main():
    nk=list(map(int,input().split()))
    h=list(map(int,input().split()))
    n=nk[0]
    k=nk[1]
    dp=[10**9]*n
    dp[0]=0
    dp[1]=abs(h[1]-h[0])
    for i in range(2,n):
        dp[i]=min(dp[j]+abs(h[i]-h[j]) for j in range(max(0,i-k),i))
        # for j in range(max(0,i-k),i):
        #     dp[i]=min(dp[j]+abs(h[i]-h[j]),dp[i])
 
    print (dp[-1])
 
if __name__ == "__main__":
    main()


### FIXED CODE ###

n,h=map(int,input().split())
l=list(map(int,input().split()))
c=[10**9]*n
c[0]=0
c[1]=abs(l[0]-l[1])
for i in range(2,n):
    c[i]=min( c[j]+abs(l[i]-l[j]) for j in range(max(0,i-h),i) )
print(c[-1])
### BUGGY CODE ###

import math

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

def waribiki(s,maisu):
    return math.floor(s/(2**maisu))

for _ in range(m):
    p = a.pop()
    a.append(waribiki(p,1))
    a.sort()

print(sum(a))

### FIXED CODE ###

import heapq
n,m = map(int, input().split())
a = list(map(lambda x: int(x)*(-1), input().split()))
heapq.heapify(a)
 
for i in range(m):
	target = heapq.heappop(a)
	heapq.heappush(a, (-1)*(-target//2))
	
print(-sum(a))