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

from copy import deepcopy
from collections import deque
from functools import partial
from heapq import heappush, heappop

inputs = open(0).readlines()
n, k = map(int, inputs[0].split())
V = deque(map(int, inputs[1].split()))
W = []

def dfs(root, option, function):
    nodes, stack = [], [root]
    ans = 0
    while stack:
        current_node = stack.pop()
        if current_node in nodes:
            continue
        ans = function(current_node, ans)
        for n in option(current_node):
            if n not in nodes:
                stack.append(n)
    return ans

def option(node, k):
    i, j, k_ = node
    if i+j+k_ < k:
        return [(i+1, j, k_), (i, j+1, k_), (i, j, k_+1)]
    return []

def function(node, ans, W, V):
    i, j, k = node
    W_, V_ = map(deepcopy, (W, V))
    for _ in range(i):
        if V_:
            heappush(W_, V_.pop())
    for _ in range(j):
        if V_:
            heappush(W_, V_.popleft())
    for _ in range(k):
        if W_:
            _ = heappop(W_)
    return max(ans, sum(W_))

ans = dfs((0, 0, 0), partial(option, k=k), partial(function, W=W, V=V))
print(ans)

### FIXED CODE ###

from collections import deque

inputs = open(0).readlines()
n, k = map(int, inputs[0].split())
V = deque(map(int, inputs[1].split()))
def calc(ii, jj, kk):
    W = []
    for i in range(ii):
        W.append(V[i])
    for j in range(jj):
        W.append(V[-j-1])
    W.sort(reverse=True)
    for _ in range(kk):
        if W[-1] < 0:
            W.pop()
    return sum(W)

ans = 0
for i in range(min(n, k)+1):
    for j in range(min(n, k)+1-i):
        for k_ in range(min(i+j, k+1-i-j)):
            ans = max(ans, calc(i, j, k_))
print(ans)
### BUGGY CODE ###

[N,L] = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
ans = []
mini = min(A[0:L])
ans.append(mini)
for i in range(1,N-L+1) :
    if A[i+L-1] <= mini :
        mini = A[i+L-1]
    elif A[i-1] == mini :
        mini = min(A[i:i+L])
    ans.append(mini)
for i in ans[:-1] : print(i, end=" ")
print(ans[-1])

### FIXED CODE ###

def ascend(a,b):
    mini = min(A[a:a+L])
    ans[a] = mini
    for i in range(a+1,b):
        if A[i+L-1] <= mini : mini = A[i+L-1]
        elif A[i-1] == mini : mini = min(A[i:i+L])
        ans[i] = mini

def descend(a,b):
    mini = min(A[b-1:b+L-1])
    ans[b-1] = mini
    for i in range(b-2,a-1,-1):
        if A[i] <= mini : mini = A[i]
        elif A[i+L] == mini: mini = min(A[i:i+L])
        ans[i] = mini
    
[N,L] = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
ans = [None]*(N-L+1)
count = 0;
if N > 10 ** 4:
    for i in range(100):
        if A[i+1] > A[i] : count += 1
    if count > 80 : descend(0, N-L+1)
    else : ascend(0,N-L+1)
else :
    ascend(0, N-L+1)
for i in ans[:-1] : print(i, end=" ")
print(ans[-1])
### BUGGY CODE ###

#!/usr/bin/env python3
#ABC111 C

from operator import itemgetter
n = int(input())
v = list(map(int,input().split()))

s = [v[i] for i in range(n) if i % 2 == 0]
t = [v[i] for i in range(n) if i % 2 == 1]

ss = list(set(s))
tt = list(set(t))
ls = len(ss)
lt = len(tt)
sc = [[ss[i],s.count(ss[i])] for i in range(len(ss))]
tc = [[tt[i],t.count(tt[i])] for i in range(len(tt))]
sc.sort(key = itemgetter(1))
tc.sort(key = itemgetter(1))
if sc[-1][0] == tc[-1][0]:
    if ls == 1 and lt == 1:
        print(n - sc[-1][1])
    elif ls == 1 and lt != 1:
        print(n - sc[-1][1] - tc[-2][1])
    elif ls != 1 and lt == 1:
        print(n - sc[-2][1] - tc[-1][1])
    else:
        ma = max(sc[-2][1],tc[-2][1])
        print(n - sc[-1][1] - ma)
else:
    print(n - sc[-1][1] - tc[-1][1])


### FIXED CODE ###

#!/usr/bin/env python3
#ABC111 C

from operator import itemgetter
import collections

n = int(input())
v = list(map(int,input().split()))

s = [v[i] for i in range(n) if i % 2 == 0]
t = [v[i] for i in range(n) if i % 2 == 1]

sc = collections.Counter(s)
tc = collections.Counter(t)
sc = list(sc.items())
tc = list(tc.items())
ls = len(sc)
lt = len(tc)
sc.sort(key = itemgetter(1))
tc.sort(key = itemgetter(1))
if sc[-1][0] == tc[-1][0]:
    if ls == 1 and lt == 1:
        print(n - sc[-1][1])
    elif ls == 1 and lt != 1:
        print(n - sc[-1][1] - tc[-2][1])
    elif ls != 1 and lt == 1:
        print(n - sc[-2][1] - tc[-1][1])
    else:
        ma = max(sc[-2][1],tc[-2][1])
        print(n - sc[-1][1] - ma)
else:
    print(n - sc[-1][1] - tc[-1][1])
### BUGGY CODE ###

import bisect

n, m = map(int, input().split())
a = list(map(int, input().split()))
min_num = min(a)
process = []

for i in range(m):
    array = list(map(int, input().split()))
    if array[1] > min_num:
        process.append(array)


a.sort()
process = sorted(process, key=lambda x: -x[1])

for i in range(len(process)):
    index = bisect.bisect_left(a, process[i][1])
    ooo = min(index, process[i][0])
    if ooo == 0:
        continue
    else:
        a = a[ooo:] + [process[i][1] for k in range(ooo)]
    if a[0] > process[i][1]:
        break

print(sum(a))


### FIXED CODE ###

from operator import itemgetter

def main():
    n, m = map(int, input().split())
    a = list(map(int, input().split()))
    change = []
    process = []
    p_append = process.append

    for i in range(m):
        array = list(map(int, input().split()))
        p_append(array)

    process.sort(key = itemgetter(1),reverse=True)

    for i in range(len(process)):
        change += [process[i][1]] * process[i][0]
        if len(change) >= n:
            break

    a = a + change
    a.sort(reverse=True)
    a = a[:n]
    print(sum(a))

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

import sys
sys.setrecursionlimit(10**7)
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline().strip()
INF = 10 ** 18
MOD = 10 ** 9 + 7

debug = True
debug = False

def dprint(*objects):
    if debug == True:
        print(*objects)

def main():
    s = SI()
    t = SI()

    d = {}
    for i, c in enumerate(s):
        if c not in d.keys():
            d[c] = [i]
        else:
            d[c].append(i)

    def init_didx():
        didx = {}
        for k in d.keys():
            didx[k] = 0
        return didx

    didx = init_didx()
    for c in set(t):
        if c not in d.keys():
            print(-1)
            return

    dprint(d)
    dprint(didx)

    import bisect

    i_loop = 0
    currentidx = -1
    for c in t:
        # 次の文字を読む
        poslist = d[c]

        if len(poslist) <= didx[c]:
            # 文字を取り切っている場合は次のループに
            i_loop += 1
            didx = init_didx()
            currentidx = poslist[0]
            didx[c] += 1
        else:
            # とり切っていない場合

            posidx = bisect.bisect_right(poslist[didx[c]:], currentidx)

            if posidx >= len(poslist[didx[c]:]):
                # とれないなら次のループでとったことにする
                i_loop += 1
                didx = init_didx()
                currentidx = poslist[0]
                didx[c] += 1
            else:
                # 同じループでとれるなら取って、現在位置を更新
                pos = poslist[didx[c]:][posidx]
                currentidx = pos
                didx[c] = posidx + 1

        dprint(c, i_loop, pos, currentidx)
        dprint(didx)

    print(len(s)*i_loop + currentidx + 1)

main()

### FIXED CODE ###

import sys
def SI(): return sys.stdin.readline().strip()

def main():
    s = SI()
    t = SI()

    import collections
    d = collections.defaultdict(list)
    for i, c in enumerate(s):
        d[c].append(i)

    keys = d.keys()
    for c in set(t):
        if c not in keys:
            print(-1)
            return

    import bisect

    i_loop = 0
    currentidx = -1
    for c in t:
        # 次の文字を読む
        poslist = d[c]

        # とり切っていない場合
        posidx = bisect.bisect_right(poslist, currentidx)

        if posidx >= len(poslist):
            # とれないなら次のループでとったことにする
            i_loop += 1
            currentidx = poslist[0]
        else:
            # 同じループでとれるなら取って、現在位置を更新
            pos = poslist[posidx]
            currentidx = pos

    print(len(s)*i_loop + currentidx + 1)

main()
### BUGGY CODE ###

n,k,q = map(int,input().split())
#a = [ int(input()) for i in range(q)]
h = [k]*n

for i in range(q):
    a = int(input())
    h = [ h[i] - 1 for i in range(n)]
    h[a-1] += 1

for i in range(n):
    if h[i] > 0:
        print("Yes")
    else:
        print("No")

### FIXED CODE ###

n,k,q = map(int,input().split())
h = [k]*n

for i in range(q):
    a = int(input())
    h[a-1] += 1
h = [ h[i] - q for i in range(n)]

for i in range(n):
    if h[i] > 0:
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

import queue

# input
H, W = map(int, input().split())
A = [list(input()) for i in range(H)]

# bfs
bfs = [[-1 for j in range(W)] for i in range(H)]
que = queue.Queue()
for i in range(H):
    for j in range(W):
        if(A[i][j] == '#'):
            que.put_nowait((i, j))
            bfs[i][j] = 0
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
while(que.qsize()):
    p = que.get_nowait()
    for i in range(4):
        if(0 <= p[0]+dx[i] < H and 0 <= p[1]+dy[i] < W):
            if(bfs[p[0]+dx[i]][p[1]+dy[i]] == -1):
                que.put_nowait((p[0]+dx[i], p[1]+dy[i]))
                bfs[p[0]+dx[i]][p[1]+dy[i]] = bfs[p[0]][p[1]] + 1

# print ans
print(max([max(l) for l in bfs]))


### FIXED CODE ###

from collections import deque

# input
H, W = map(int, input().split())
A = [list(input()) for i in range(H)]

# bfs
bfs = [[-1 for j in range(W)] for i in range(H)]
que = deque()
for i in range(H):
    for j in range(W):
        if(A[i][j] == '#'):
            que.append((i, j))
            bfs[i][j] = 0
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
while(len(que)):
    p = que.popleft()
    for i in range(4):
        if(0 <= p[0]+dx[i] < H and 0 <= p[1]+dy[i] < W):
            if(bfs[p[0]+dx[i]][p[1]+dy[i]] == -1):
                que.append((p[0]+dx[i], p[1]+dy[i]))
                bfs[p[0]+dx[i]][p[1]+dy[i]] = bfs[p[0]][p[1]] + 1

# print ans
print(max([max(l) for l in bfs]))
### BUGGY CODE ###

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

for k in range(K):
    for i in range(N):
        if A[i] != N:
            break
    else:
        break

    B = [0] * N
    for i in range(N):
        d = A[i]
        left = max(0, i - d)
        right = min(N-1, i + d)
        B[left] += 1
        if right + 1 < N:
            B[right+1] -= 1
    for i in range(1, N):
        B[i] += B[i-1]
    A = B
print(" ".join(map(str, A)))


### FIXED CODE ###

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

for k in range(K):
    for i in range(N):
        if A[i] != N:
            break
    else:
        break

    B = [0] * N
    for i in range(N):
        d = A[i]
        left = max(0, i - d)
        right = min(N-1, i + d)
        B[left] += 1
        if right + 1 < N:
            B[right+1] -= 1
    for i in range(1, N):
        B[i] += B[i-1]
    A = B
print(" ".join(map(str, A)))
### BUGGY CODE ###

import sys
input = sys.stdin.readline

mod = 10**9+7

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

LX = [[] for _ in range(N+2)]
for l, r, x in LRX:
    LX[r].append((l, x))

dp = [[[0]*(N+2) for _ in range(N+2)] for _ in range(N+2)]
# dp[i][j][k] (i <= j <= k) 
# 三色それぞれ、最後に使ったindex(1-indexed)がi,j,k

dp[0][0][0] = 1

# (i, j, k+1)に置くのが、条件(l,x)に適しているか
def check(i, j, l, x):
    return (x == 3 and l <= i) or (x == 2 and i < l <= j) or (x == 1 and j < l)

for i in range(N+1):
    for j in range(i, N+1):
        for k in range(j, N+1):
            
            # 一番前の色を置く
            ok = True
            for l, x in LX[k+1]:
                if not check(j, k, l, x):
                    ok = False
            if ok:
                dp[j][k][k+1] = (dp[j][k][k+1] + dp[i][j][k]) % mod
            
            # 最後
            ok = True
            for l, x in LX[k+1]:
                if not check(i, j, l, x):
                    ok = False
            if ok:
                dp[i][j][k+1] = (dp[i][j][k+1] + dp[i][j][k]) % mod
            
            # 二番目
            ok = True
            for l, x in LX[k+1]:
                if not check(i, k, l, x):
                    ok = False
            if ok:
                dp[i][k][k+1] = (dp[i][k][k+1] + dp[i][j][k]) % mod
        

                

ans = 0
for a in range(N+1):
    for b in range(N+1):
        ans = (ans + dp[a][b][N]) % mod

print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline

mod = 10**9+7



# (i, j, k+1)に置くのが、条件(l,x)に適しているか
def check(i, j, l, x):
    return (x == 3 and l <= i) or (x == 2 and i < l <= j) or (x == 1 and j < l)


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

LX = [[] for _ in range(N+2)]
for l, r, x in LRX:
    LX[r].append((l, x))

dp = [[[0]*(j+1) for j in range(i+1)] for i in range(N+2)]
# dp[i][j][k] (k <= j <= i) 
# 三色それぞれ、最後に使ったindex(1-indexed)がi,j,k

dp[0][0][0] = 1

for i in range(N+1):
    for j in range(i, N+1):
        for k in range(j, N+1):
            
            # 一番前の色を置く
            ok = True
            for l, x in LX[k+1]:
                if not check(j, k, l, x):
                    ok = False
                    break
            if ok:
                dp[k+1][k][j] = (dp[k+1][k][j] + dp[k][j][i]) % mod
            
            # 最後
            ok = True
            for l, x in LX[k+1]:
                if not check(i, j, l, x):
                    ok = False
                    break
            if ok:
                dp[k+1][j][i] = (dp[k+1][j][i] + dp[k][j][i]) % mod
            
            # 二番目
            ok = True
            for l, x in LX[k+1]:
                if not check(i, k, l, x):
                    ok = False
                    break
            if ok:
                dp[k+1][k][i] = (dp[k+1][k][i] + dp[k][j][i]) % mod
        

ans = 0
for a in range(N+1):
    for b in range(a,N+1):
        ans = (ans + dp[N][b][a]) % mod

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

import numpy as np

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

maze_x = [input() for _ in range(H)]
maze_y = [''.join(x) for x in zip(*maze_x)]

def count_light(maze, W, H):
    cnt = [[0]*W for _ in range(H)]
    for hh in range(H):
        lst = [i for i in maze[hh].split('#') if i != '']
        ww = 0
        k = 0
        while 0 <= ww <= W - 1:
            if maze[hh][ww] == '.':
                ln = len(lst[k])
                cnt[hh][ww:ww+ln] = [ln]*ln
                ww += ln-1
                k += 1
            ww += 1
    return cnt
cnt = (np.array(count_light(maze_x, W, H)) + np.array(count_light(maze_y, H, W)).T -1)

print(max(0,max([max(cnt[i]) for i in range(H)])))


### FIXED CODE ###

import numpy as np

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

maze01 = np.array([[int(x=='.') for x in input()] for _ in range(H)]) 

u = np.zeros((H, W), dtype=np.int32)
d = np.zeros((H, W), dtype=np.int32)
r = np.zeros((H, W), dtype=np.int32)
l= np.zeros((H, W), dtype=np.int32)


u[0] = maze01[0]
d[H - 1] = maze01[H - 1]
for hh in range(1,H):
    u[hh] = u[hh-1] + maze01[hh]
    u[hh] *= maze01[hh]
    d[H - hh - 1] = d[H - hh] + maze01[H - hh - 1]
    d[H - hh - 1] *= maze01[H - hh - 1]

l[:, 0] = maze01[:, 0]
r[:, W - 1] = maze01[:, W - 1]
for ww in range(1, W):
    l[:, ww] = l[:, ww -1] + maze01[:, ww]
    l[:, ww] *= maze01[:, ww]
    r[:, W - ww -1] = r[:, W - ww] + maze01[:, W - ww - 1]
    r[:, W - ww -1] *= maze01[:, W - ww - 1]

cnt = r + l + u + d - 3

print(max([max(cnt[i]) for i in range(H)]))
### BUGGY CODE ###

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

l = [0]*(N+1)
l[0] = 1
for i in range(1, N+1):
  if i in a:
    l[i] = 0
  else:
    if i == 1:
      l[1] = 1
    else:
      l[i] = (l[i-1] + l[i-2]) % (10**9+7)

print(l[N])

### FIXED CODE ###

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

l = [0]*(N+1)
l[0] = 1
j = 0
for i in range(1, N+1):
  if j < M and i == a[j]:
    j += 1
  else:
    if i == 1:
      l[1] = 1
    else:
      l[i] = (l[i-1] + l[i-2]) % (10**9+7)

print(l[N])
### BUGGY CODE ###

x = int(input())
i = 1
n= 0
if x % 2 == 0:
    print(-1)
else:
    for i in range(1, 1000000):

        l = 7 * (10**i - 1) // 9
        n+=1
        if l % x == 0:
            break
    print(n)


### FIXED CODE ###

k = int(input())
a=0
for i in range (1,10**6):
    a=10*a+7
    a%=k
    if a==0:
      ans=i
      break;
    else:
      ans=-1
print(ans)
### BUGGY CODE ###

from collections import deque, Counter

N, M, K = map(int, input().split())
Friend = [[]for i in range(N)]
Block = [[] for i in range(N)]

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

for i in range(K):
    c, d = map(int, input().split())
    c -= 1
    d -= 1
    Block[c].append(d)
    Block[d].append(c)
Group = [0] * N
Q = deque()
for i in range(1, N):
    if 0 not in Group:
        break
    else:
        z = Group.index(0)
        Group[z] = i
        Q.append(z)
        while len(Q) > 0:
            now = Q.popleft()
            for j in Friend[now]:
                if Group[j] != 0:
                    continue
                else:
                    Group[j] = i
                    Q.append(j)
G_ = Counter(Group)
for i in range(N):
    ans = G_[Group[i]] - 1
    for j in Friend[i]:
        if Group[i] == Group[j]:
            ans -= 1
    for j in Block[i]:
        if Group[i] == Group[j]:
            ans -= 1
    print(ans, end=' ')


### FIXED CODE ###

# Union-Find
def find(x):
    if par[x] < 0:
        return x
    else:
        par[x] = find(par[x])
        return par[x]


def unite(x, y):
    x = find(x)
    y = find(y)
    if x == y:
        return False
    if par[x] > par[y]:
        x, y = y, x
    par[x] += par[y]
    par[y] = x
    return True


def same(x, y):
    return find(x) == find(y)


def size(x):
    return -par[find(x)]


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

par = [-1] * N
for i in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    unite(a, b)
    Friend[a].append(b)
    Friend[b].append(a)

Block = [[] for _ in range(N)]
for i in range(K):
    c, d = map(int, input().split())
    c -= 1
    d -= 1
    Block[c].append(d)
    Block[d].append(c)

Ans = []
for i in range(N):
    ans = size(i) - 1
    ans -= len(Friend[i])
    for b in Block[i]:
        if same(i, b):
            ans -= 1
    Ans.append(str(ans))

print(' '.join(Ans))
### BUGGY CODE ###

N,K=map(int,input().split())
ab=[list(map(int,input().split())) for _ in range(N-1)]
graph=[[] for _ in [0]*N]
for a,b in ab:
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)
    
info=[[False,set(),set(),-1] for _ in [0]*N]
q=[[0,""]]
status=[set(),set()]
while(q):
    i,j = q.pop()
    if j!="":
        status=[{j},{k for k in info[j][1]}]
    info[i][1]=status[0]|info[i][1]
    info[i][2]=status[1]|info[i][2]
    if info[i][0]==False:
        info[i][0]=True
        info[i][3]=K-len(info[i][1])-len(info[i][2])
    while(graph[i]):
        g=graph[i].pop()
        q.append((g,i))
ans=1
mod=10**9+7
for i in info:
    ans=(ans*i[3])%mod
print(ans)

### FIXED CODE ###

N,K=map(int,input().split())
ab=[list(map(int,input().split())) for _ in range(N-1)]
graph=[[] for _ in [0]*N]
[graph[a-1].append(b-1) for a,b in ab]
[graph[b-1].append(a-1) for a,b in ab]
q=[[-1,0]]
cnt=0
ans=K
mod=10**9+7
while(q):
    q1=[]
    if cnt<2:
        cnt+=1
    for i,j in q:
        g=graph[j]
        if i!=-1:
            g.remove(i)
        for cnt2,k in enumerate(g):
            q1.append([j,k])
            ans=(ans*(K-cnt-cnt2))%mod
    q=q1
print(ans)
### BUGGY CODE ###

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

tmp = [n]

while True:
    m = abs(n - k)
    if m in tmp:
        ans = min(tmp)
        break
    else:
        tmp.append(m)
        n = m

print(ans)

### FIXED CODE ###

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

tmp = n % k
if n >= k:
    ans = min(tmp, k - tmp)
else:
    ans = min(n, k - n)

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

import numpy as np
import sys
import math

S = input()

mm = [0] * (2019)
mm[0] = 1
T = 0

for ind , s in enumerate( S[::-1] ):
    T = T + ( int(s) * (10 ** (ind) ))
    mm[T % 2019 ] += 1

ans = 0

for m in mm:
    ans += int( (m * (m-1) ) / 2 )

print(ans)

### FIXED CODE ###

import numpy as np
import sys
import math

S = input()

mm = [0] * (2019)
mm[0] = 1
a = [0] * (len(S) + 1 ) 
T = 0
ten = 1
ll = len(S)
for i in range(ll):
    if i > 0:
        ten = ( ten * 10 ) % 2019
    a[i+1] =  ( a[i] + (int(S[ll-1-i])*ten ) ) % 2019
    mm[ a[i+1] ] += 1
    #print(s)

ans = 0

for m in mm:
    ans += int( (m * (m-1) ) / 2 )

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

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

d=[]
for i in range(m):
    b,c = map(int, input().split())
    d.extend([c]*b)    
d.sort(reverse=True)

if len(d)>n:d=d[:n]

a.extend(d)
a.sort(reverse=True)

print(sum(a[:n]))

### FIXED CODE ###

n,m=map(int,input().split())
a = list(map(int, input().split()))
bc=[list(map(int,input().split())) for _ in range(m)]
#print(bc)
bc=sorted(bc,key= lambda x:x[1],reverse=True)
#print(bc)

bc2=[]
for i in range(m):
    bc2.extend([bc[i][1]]*bc[i][0])
    if len(bc2)>n: break
#print(bc2)
a.extend(bc2)
a.sort(reverse=True)

print(sum(a[:n]))
### BUGGY CODE ###

n,m=map(int,input().split())
lr=[list(map(int,input().split())) for i in range(m)]
lis=[0]*n
for l,r in lr:
  for t in range(l,r+1):
    lis[t-1]+=1
ans=0
for ll in lis:
  if ll==m:
    ans+=1
print(ans)

### FIXED CODE ###

n,m=map(int,input().split())
l,r=map(int,input().split())
for i in range(m-1):
  x,y=map(int,input().split())
  l=max(l,x)
  r=min(r,y)
print(r-l+1 if l<=r else(0))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10 ** 6)


def main():
    N = int(input())
    A = list(map(int, input().split()))
    c = [[None] * N for _ in range(N)]
    for r in reversed(range(N)):
        c[r][r] = A[r]
        for l in range(r + 1, N):
            c[r][l] = max(-c[r + 1][l] + A[r], -c[r][l - 1] + A[l])
    
    print(c[0][N - 1])


main()


### FIXED CODE ###

def main():
    N = int(input())
    A = list(map(int, input().split()))
    c = [0] * N
    for r in reversed(range(N)):
        ar = A[r]
        c[r] = t = ar
        for l in range(r + 1, N):
            c[l] = t = max(ar - c[l], A[l] - t)
    
    print(c[-1])


main()
### BUGGY CODE ###

import heapq
n, m = map(int, input().split())
a = list(map(int, input().split()))
a = [-1 * x for x in a]
heapq.heapify(a)
for _ in range(m):
    b, c = map(int, input().split())
    for i in range(b):
        heapq.heappush(a, -1 * c)

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

print(ans)

### FIXED CODE ###

import heapq
n, m = map(int, input().split())
a = list(map(int, input().split()))
heapq.heapify(a)
lst = []
for _ in range(m):
    b, c = map(int, input().split())
    lst.append((b, c))

lst = sorted(lst, key = lambda x: -x[1])
flag = False
for b, c in lst:
    for _ in range(b):
        min_num = heapq.heappop(a)
        if min_num < c:
            heapq.heappush(a, c)
        else:
            heapq.heappush(a, min_num)
            flag = True
            break
    if flag:
        break

print(sum(a))
### BUGGY CODE ###

N, M = map(int,input().split())
L = [0] * M
R = [0] * M
for i in range(M):
    L[i], R[i] = map(int,input().split())
ans = 0
for i in range(N):
    count = 0
    for j in range(M):
        if L[j] <= (i+1) and (i+1) <= R[j]:
            count += 1
    if count == M:
        ans += 1
print(ans)

### FIXED CODE ###

N, M = map(int,input().split())
L = [0] * M
R = [0] * M
for i in range(M):
    L[i], R[i] = map(int,input().split())
ans = 0
A = [0] * N
L_max = max(L)
R_min = min(R)
if R_min >= L_max:
    ans = R_min - L_max + 1
else:
    ans = 0
print(ans)