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

from functools import lru_cache

N, A = map(int, input().split())
X = tuple(int(x) for x in input().split())

# 平均を出すのに選んだ個数が必要
@lru_cache(maxsize=None)
def rec(x, a, k):
    """
    :param x: tuple
        数列
    :param a: int
        総和
    :param k: int
        選ぶ個数
    :return: int
        通り数
        Number of patterns
    """
    if k == 0:
        if a == 0:
            return 1
        else:
            return 0

    if a < 0 or len(x) < k:
        return 0

    ret = rec(x[1:], a, k)
    ret += rec(x[1:], a - x[0], k - 1)
    return ret

m = (rec(X, k * A, k) for k in range(1, N + 1))
print(sum(m))

### FIXED CODE ###

from functools import lru_cache

N, A = map(int, input().split())
X = tuple(int(x) for x in input().split())

# 平均を出すのに選んだ個数が必要
@lru_cache(maxsize=None)
def rec(i, a, k):
    """
    :param i: int 
        数列の長さ
    :param a: int
        総和
    :param k: int
        選ぶ個数
    :return: int
        通り数
        Number of patterns
    """
    if k == 0:
        if a == 0:
            return 1
        else:
            return 0

    if a < 0 or i < k:
        return 0

    ret = rec(i - 1, a, k)
    ret += rec(i - 1, a - X[i - 1], k - 1)
    return ret

i = len(X)
m = (rec(i, k * A, k) for k in range(1, N + 1))
print(sum(m))
### BUGGY CODE ###

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

idx = B[0]
idx_count = 0
idx_set = []
for i in range(N):
  if idx != B[i]:
    tmp1 = int(idx_count*(idx_count-1)/2)		# 同一の整数を持つボールの組合せ数
    tmp2 = int((idx_count-1)*(idx_count-2)/2)	# 同一の整数を持つボールを1つ除いたときの組合せ数
    idx_set.append([idx, tmp1, tmp2])
    idx_count = 0
    idx = B[i]
  idx_count+=1
if idx_count != 0:
  tmp1 = int(idx_count*(idx_count-1)/2)			# 同一の整数を持つボールの組合せ数
  tmp2 = int((idx_count-1)*(idx_count-2)/2)		# 同一の整数を持つボールを1つ除いたときの組合せ数
  idx_set.append([idx, tmp1, tmp2])
#print(idx_set)
idx_sum_set = []
all_c = 0
for i in range(len(idx_set)):
  all_c += idx_set[i][1]
for i in range(len(idx_set)):
  tmp = all_c-idx_set[i][1]+idx_set[i][2]
  idx_sum_set.append([idx_set[i][0], tmp])    

if len(idx_sum_set) == 1:
  for i in range(N):
    print(idx_sum_set[0][1])
elif all_c == 0:
  for i in range(N):
    print(0)
else:
  for i in range(N):
    j = int(len(idx_sum_set)/2)
    while 1:
      if A[i] == idx_sum_set[j][0]:
        print(idx_sum_set[j][1])
        break
      elif A[i] > idx_sum_set[j][0]:
        j = j + int((len(idx_sum_set)-j)/2)
      elif A[i] < idx_sum_set[j][0]:
        j = int(j/2)



### FIXED CODE ###

import numpy as np
N = int(input())
A = list(map(int, input().split()))
B = np.zeros(N+1)

for i in range(N):
  B[A[i]]+=1
#print(B)

all_c = 0
for i in range(1,N+1):
  all_c += int(B[i]*(B[i]-1)/2)			# 同一の整数を持つボールの組合せ数
for i in range(N):
  if B[A[i]] != 0:
    print(int(all_c-(B[A[i]]-1)))
### BUGGY CODE ###

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

road = []
x_list = []

for i in range(N):
    s,t,x = list(map(int,input().split()))
    road.append([0,s-x,x])
    road.append([1,t-x,x])

for i in range(Q):
    road.append([2,int(input()),i])

from collections import defaultdict

counter = defaultdict(int)
counter[10**27] = 1
ans = [0]*Q

road.sort(key=lambda x:x[0])
road.sort(key=lambda x:x[1])

q = [10**27]

from heapq import heappop,heappush

for id,_,x in road:
    if id==0:
        heappush(q,x)
        counter[x]+=1
    elif id==1:
        counter[x]-=1
    else:
        while counter[q[0]]==0:
            heappop(q)
        #print(q)
        if q[0]<10**27:
            ans[x] = q[0]
        else:
            ans[x] = -1
print("\n".join(map(str,ans)))

### FIXED CODE ###

import sys

sys.setrecursionlimit(500000)
def input():
    return sys.stdin.readline()[:-1]

def main():
    N,Q = list(map(int,input().split()))

    road = []
    x_list = []

    for i in range(N):
        s,t,x = list(map(int,input().split()))
        road.append([0,s-x,x])
        road.append([1,t-x,x])

    for i in range(Q):
        road.append([2,int(input()),i])

    from collections import defaultdict

    counter = defaultdict(int)
    counter[10**27] = 1
    ans = [0]*Q

    road.sort(key=lambda x:x[0])
    road.sort(key=lambda x:x[1])

    q = [10**27]

    from heapq import heappop,heappush

    for id,_,x in road:
        if id==0:
            heappush(q,x)
            counter[x]+=1
        elif id==1:
            counter[x]-=1
        else:
            while counter[q[0]]==0:
                heappop(q)
            #print(q)
            if q[0]<10**27:
                ans[x] = q[0]
            else:
                ans[x] = -1
    print("\n".join(map(str,ans)))

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

MOD = 10**9+7

S = input()
N = len(S)
amari = [0 for _ in range(13)]


for i, s in enumerate(S):
    if i == 0:
        next_amari = [0 for _ in range(13)]
        if s != "?":
            number = int(s)
            now_amari = number * pow(10, N-1-i, 13) % 13
            next_amari[now_amari] = 1
        else:
            for number in range(10):
                now_amari = number * pow(10, N-1-i, 13) % 13
                next_amari[now_amari] += 1
        amari = next_amari
        continue

    next_amari = [0 for _ in range(13)]
    if s != "?":
        number = int(s)
        now_amari = number * pow(10, N-1-i, 13) % 13
        for j, n in enumerate(amari):
            next_amari[(j+now_amari) % 13] = n
    else:
        for number in range(10):
            now_amari = number * pow(10, N-1-i, 13) % 13
            for j, n in enumerate(amari):
                next_amari[(j+now_amari) % 13] = (n+next_amari[(j+now_amari) % 13])%MOD

    amari = next_amari
print(amari[5])


### FIXED CODE ###

MOD = 10**9+7

S = input()
N = len(S)
amari = [0 for _ in range(13)]


for i, s in enumerate(S):
    if i == 0:
        next_amari = [0 for _ in range(13)]
        if s != "?":
            number = int(s)
            now_amari = number * pow(10, N-1-i, 13) % 13
            next_amari[now_amari] = 1
        else:
            for number in range(10):
                now_amari = number * pow(10, N-1-i, 13) % 13
                next_amari[now_amari] += 1
        amari = next_amari
        continue

    next_amari = [0 for _ in range(13)]
    if s != "?":
        number = int(s)
        now_amari = number * pow(10, N-1-i, 13) % 13
        for j, n in enumerate(amari):
            next_amari[(j+now_amari) % 13] = n
    else:
        for number in range(10):
            now_amari = number * pow(10, N-1-i, 13) % 13
            for j, n in enumerate(amari):
                next_amari[(j+now_amari) % 13] = (n+next_amari[(j+now_amari) % 13])%MOD

    amari = next_amari
print(amari[5])
### BUGGY CODE ###

import sys
import collections


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    n = int(readline())
    a = [list(map(int, readline().split())) for _ in range(n)]
    for i in range(n):
        for j in range(n - 1):
            a[i][j] -= 1
    ls = [0] * n
    ql = collections.deque()
    for i in range(n):
        ql.append([0, i])

    for i in range(10 ** 10):
        fq = [True] * n
        while ql:
            d, ps = ql.popleft()
            if d == i:
                if ls[ps] < n - 1 and fq[ps]:
                    nw = a[ps][ls[ps]]
                    if ls[nw] < n - 1 and fq[nw]:
                        rw = a[nw][ls[nw]]
                        if ps == rw:
                            ls[ps] += 1
                            ql.append([d+1, ps])
                            ls[nw] += 1
                            ql.append([d+1, nw])
                            fq[nw] = False
                            fq[ps] = False
            else:
                ql.appendleft([d, ps])
                break
        if len(ql) == 0 or sum(ls) == n * (n - 1):
            print(i + 1 if sum(ls) == n * (n - 1) else -1)
            exit()


if __name__ == '__main__':
    solve()


### FIXED CODE ###

def slove():
    import sys
    import collections
    input = sys.stdin.readline
    n = int(input().rstrip('\n'))
    a = [list(map(int, input().rstrip('\n').split())) for _ in range(n)]
    ad = [0] * n
    dq = collections.deque([[0, i + 1] for i in range(n)])
    for i in range(10 ** 15):
        fd = {}
        while True:
            if len(dq) != 0:
                d, q = dq.popleft()
                q -= 1
                if d <= i:
                    if ad[q] < n - 1:
                        qq = a[q][ad[q]] - 1
                        tq = a[qq][ad[qq]] - 1
                        if q == tq and qq not in fd and tq not in fd:
                            ad[qq] += 1
                            ad[tq] += 1
                            if ad[qq] < n - 1:
                                dq.append([d + 1, qq + 1])
                            if ad[tq] < n - 1:
                                dq.append([d + 1, tq + 1])
                            fd[qq] = 0
                            fd[tq] = 0
                else:
                    dq.append([d, q + 1])
                    break
            else:
                break
        if len(dq) == 0:
            b = True
            for v in ad:
                if v != n - 1:
                    b = False
                    break
            if b:
                print(i + 1)
                exit()
            else:
                print(-1)
                exit()


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

n = int(input())
columns = [int(input()) for i in range(n)]
for order_element in range(0,len(columns)):
    copied=columns.copy()
    copied.pop(order_element)
    print(sorted(copied)[-1])

### FIXED CODE ###

n = int(input())
lister = [int(input()) for i in range(n)]
ordered=sorted(lister,reverse=True)

for element in lister:
  if ordered[0]!=element:
    print(ordered[0])
  else:
    print(ordered[1])
### BUGGY CODE ###

from itertools import combinations
N = int(input())
A = list(map(int,input().split()))
mod = 10**9 + 7
comb = list(combinations(A, 2))
XOR = [(i ^ j)%mod for i, j in comb]
print(sum(XOR)%mod)

### FIXED CODE ###

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

ans = 0
 
MOD = (10**9+7)
for i in range(62):
    c = 0
    for ai in a:
        if ai&(1<<i): c += 1
    
    r = c*(n-c)
    ans += (1<<i)*r
    ans %= MOD
 
 
print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(2147483647)
INF=10**10
MOD=10**9+7
input=sys.stdin.readline

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

#初期値が0の辞書
#from collections import defaultdict
#lrd = defaultdict(lambda: []) 

lrd=[[] for _ in range(n)]

for _ in range(m):
    l,r,d=map(int,input().split())
    #print("lrd",lrd)
    lrd[l-1].append((r-1,-d))
    lrd[r-1].append((l-1,+d))

#print(lrd)

def BFD(x):
    global checked,answer,lrd
    checked[x]=1
    #print("x>>>",x,lrd[x])
    for llrrdd in lrd[x]:
        #print(llrrdd,x)
        item=llrrdd[0]
        if answer[item]==-10**10:
            answer[item]=answer[x]-llrrdd[1]
        else:
            if answer[item]!=answer[x]-llrrdd[1]:
                print("No")
                exit()
        if checked[item]==0:
            BFD(item)

checked=[0]*n

for i in range(n):
    if checked[i]==0:
        answer = [-10**10]*n
        answer[i]=1
        BFD(i)

print("Yes")


### FIXED CODE ###

import sys
sys.setrecursionlimit(100000)
input=sys.stdin.readline

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

lrd=[[] for _ in range(n)]

for _ in range(m):
    l,r,d=map(int,input().split())
    lrd[l-1].append((r-1,-d))
    lrd[r-1].append((l-1,+d))

def BFD(x):
    global checked,answer,lrd
    checked[x]=1
    #print("x>>>",x,lrd[x])
    for llrrdd in lrd[x]:
        #print(llrrdd,x)
        item=llrrdd[0]
        if answer[item]=="first":
            answer[item]=answer[x]-llrrdd[1]
        else:
            if answer[item]!=answer[x]-llrrdd[1]:
                print("No")
                exit()
        if checked[item]==0:
            BFD(item)

checked=[0]*n
answer = ["first"]*n

for i in range(n):
    if checked[i]==0:
        answer[i]=1
        BFD(i)

print("Yes")
### BUGGY CODE ###

A,B=map(int,input().split())
lst=[]
for i in range(2,int(min(A,B)+1)):
    if A%i==0 and B%i==0:
        flag=1
        for l in lst:
            if i%l==0:
                flag=0
                break
        if flag:
            lst.append(i)

lst+=[1]
#print(lst)
print(len(lst))


### FIXED CODE ###

A,B=map(int,input().split())
lst=set()
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

if A==B==1:
    print(1)
else:
    print(len(set([i[0] for i in factorization(A)])&set([i[0] for i in factorization(B)]))+1)
### BUGGY CODE ###

def make_list(x,S):#x:元の配列から切り取る番号 S:リスト受け取り
    a=[]
    for i in range(0,x):#S[0]~S[x-1]までを追加
        a.append(S[i])
    if x<len(S)-2:
        for i in range(x+2,len(S)):
            a.append(S[i])
    return a
S=list(map(int,input()))
N=len(S)#S[0]~S[N-1]
count=0
j=0
while j==0 and N!=1:
    for i in range(N-1):#S[0]~S[N-2]
        if (S[i]==0 and S[i+1]==1)or(S[i]==1 and S[i+1]==0):
            count+=2
            S=make_list(i,S)#Sの書き換え
            N=len(S)#Nの書き換え
            if N==0:
                j=1
            break
        elif i==N-2:
            j=1
print(count)

### FIXED CODE ###

S=list(map(int,input()))
a=0
b=0
for i in range(len(S)):
    if S[i]==1:
        a+=1
    else:
        b+=1
print(2*min(a,b))
### BUGGY CODE ###

N, H = map(int, input().split())
A = 0
B = [0] * (N + 1)
for i in range(N):
  a, b = map(int, input().split())
  A = max(a, A)
  B[i] = b
B.sort(reverse=True)
cnt = 0
while H > 0:
  b = B[0]
  B = B[1:]
  if b > A:
    H -= b
    cnt += 1
  else:
    k = -(-H // A)
    H -= A * k
    cnt += k
print(cnt)

### FIXED CODE ###

N, H = map(int, input().split())
A = 0
B = [0] * (N + 1)
for i in range(N):
  a, b = map(int, input().split())
  A = max(a, A)
  B[i] = b
B.sort(reverse=True)
cnt = 0
i  = 0
while H > 0:
  if B[i] > A:
    H -= B[i]
    cnt += 1
    i += 1
  else:
    k = -(-H // A)
    H -= A * k
    cnt += k
print(cnt)
### BUGGY CODE ###

#!/usr/bin/env python3
import sys


def solve(N: int, W: int, w: "List[int]", v: "List[int]"):
    dp = [[float('inf') for _ in range(10**5+1)] for _ in range(N)]
    dp[0][0] = 0
    dp[0][v[0]] = w[0]

    jmax = v[0]
    for i in range(1,N):
        jmax += v[i]
        for j in range(jmax+1):
            if j - v[i] >= 0:
                dp[i][j] = min(dp[i-1][j], dp[i-1][j-v[i]] + w[i])
            else:
                dp[i][j] = dp[i-1][j]

    res = 0
    for i,j in enumerate(dp[-1]):
        if j != float("inf") and j <= W:
            res = i
    print(res)

    return


# Generated by 1.1.5 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    W = int(next(tokens))  # type: int
    w = [int()] * (N)  # type: "List[int]"
    v = [int()] * (N)  # type: "List[int]"
    for i in range(N):
        w[i] = int(next(tokens))
        v[i] = int(next(tokens))
    solve(N, W, w, v)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys


def solve(N: int, W: int, w: "List[int]", v: "List[int]"):
    dp = [[float('inf') for _ in range(10**5+1)] for _ in range(N)]
    dp[0][0] = 0
    dp[0][v[0]] = w[0]

    js = [0,v[0]]

    for i in range(1,N):
        for j in js[:]:
            js.append(j+v[i])
        js = list(set(js))

        for j in js:
            if j - v[i] >= 0:
                dp[i][j] = min(dp[i-1][j], dp[i-1][j-v[i]] + w[i])
            else:
                dp[i][j] = dp[i-1][j]

    res = 0
    for i,j in enumerate(dp[-1]):
        if j != float("inf") and j <= W:
            res = i
    print(res)

    return


# Generated by 1.1.5 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    W = int(next(tokens))  # type: int
    w = [int()] * (N)  # type: "List[int]"
    v = [int()] * (N)  # type: "List[int]"
    for i in range(N):
        w[i] = int(next(tokens))
        v[i] = int(next(tokens))
    solve(N, W, w, v)

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

import math
x,y = map(int,input().split())
sum_xy = x+y

def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 10**9+7 #出力の制限
N = 10**7
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

if sum_xy%3!=0:
    print(0)
else:
    ab_sum = sum_xy//3
    a = x-ab_sum
    b = y-ab_sum
    print(cmb(ab_sum,a,inf))
    


### FIXED CODE ###

x, y = map(int, input().split())
if (x+y)%3 != 0:
    print(0)
    exit()

def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod
 
mod = 10**9+7
N = 10**6
g1 = [1, 1]
g2 = [1, 1]
inverse = [0, 1]
 
for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )
 
 
a = (2*x-y)//3
b = (2*y-x)//3
n = a+b
r = a
res = cmb(n,r,mod)
print(res)
### BUGGY CODE ###

def resolve():
    N, K = map(int, input().split())
    P = list(map(int, input().split()))

    max_tmp = [0] * K
    for i in range(len(P) - K + 1):
        tmp = P[i: i + K]
        if sum(max_tmp) < sum(tmp):
            max_tmp = tmp

    ans = 0
    for number in max_tmp:
        ans += sum(list(range(1, number + 1))) / number

    print(ans)


resolve()

### FIXED CODE ###

import itertools


def resolve():
    N, K = map(int, input().split())
    P = list(map(int, input().split()))

    P = [(1 + p) / 2 for p in P]
    accumulate_P = [0] + list(itertools.accumulate(P))

    ans = 0
    for ii in range(N - K + 1):
        range_sum_P = accumulate_P[ii + K] - accumulate_P[ii]
        ans = max(ans, range_sum_P)

    print(ans)

resolve()
### BUGGY CODE ###

# -*- coding: utf-8 -*-
"""
@author: H_Hoshigi
"""
def main():
    H, W = map(int, input().split())
    S_lsit = [input() for i in range(H)]

    INF = 401

    node_list = []
    for i in range(H):
        node_list += [(i, j) for j in range(W)]

    dist_table = [[INF for j in range(H*W)] for i in range(H*W)]
    for i in range(H*W):
        dist_table[i][i] = 0
    #print(dist_table)

    path_list = [[] for i in range(H*W)]
    for k in range(H*W):
        node = node_list[k]
        i, j = node[0], node[1]
        if i >= 1 and S_lsit[i-1][j] == ".":
            path_list[k].append((i-1)*W + j)
        if i <= H-2 and S_lsit[i+1][j] == ".":
            path_list[k].append((i+1)*W + j)
        if j >= 1 and S_lsit[i][j-1] == ".":
            path_list[k].append(i*W + j-1)
        if j <= W-2 and S_lsit[i][j+1] == ".":
            path_list[k].append(i*W + j+1)
        for next_node in path_list[k]:
            dist_table[k][next_node] = 1
    #print(path_list)

    for k in range(H*W):
        for i in range(H*W):
            for j in range(H*W):
                dist_table[i][j] = min(
                    dist_table[i][j],
                    dist_table[i][k] + dist_table[k][j]
                )
    #print(dist_table)

    max_dist = 0
    for i in range(H*W):
        if S_lsit[i//W][i%W] == ".":
            for j in range(H*W):
                if S_lsit[j//W][j%W] == ".":
                    max_dist = max(max_dist, dist_table[i][j])
    print(max_dist)

if __name__ == "__main__":
    main()



### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
@author: H_Hoshigi
"""
def main():
    H, W = map(int, input().split())
    S_lsit = [input() for i in range(H)]

    INF = 401

    node_list = []
    for i in range(H):
        node_list += [(i, j) for j in range(W)]

    dist_table = [[INF for j in range(H*W)] for i in range(H*W)]
    for i in range(H*W):
        dist_table[i][i] = 0
    #print(dist_table)

    path_list = [[] for i in range(H*W)]
    for k in range(H*W):
        node = node_list[k]
        i, j = node[0], node[1]
        if i >= 1 and S_lsit[i-1][j] == ".":
            path_list[k].append((i-1)*W + j)
        if i <= H-2 and S_lsit[i+1][j] == ".":
            path_list[k].append((i+1)*W + j)
        if j >= 1 and S_lsit[i][j-1] == ".":
            path_list[k].append(i*W + j-1)
        if j <= W-2 and S_lsit[i][j+1] == ".":
            path_list[k].append(i*W + j+1)
        for next_node in path_list[k]:
            dist_table[k][next_node] = 1
    #print(path_list)

    for k in range(H*W):
        for i in range(H*W):
            for j in range(H*W):
                dist_table[i][j] = min(
                    dist_table[i][j],
                    dist_table[i][k] + dist_table[k][j]
                )
    #print(dist_table)

    max_dist = 0
    for i in range(H*W):
        if S_lsit[i//W][i%W] == ".":
            for j in range(H*W):
                if S_lsit[j//W][j%W] == ".":
                    max_dist = max(max_dist, dist_table[i][j])
    print(max_dist)

if __name__ == "__main__":
    main()
### BUGGY 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(key=lambda x:x[1])
d=[]
for i in range(m):
  b,c = bc[i]
  for j in range(b):
    d.append(c)
d=d[::-1]
for i in range(len(d)):
  for j in range(n):
    if a[j] < d[i]:
      a[j]=d[i]
      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 i in range(m)]
bc.sort(key=lambda x:x[1])
for b,c in bc[::-1]:
  a.extend([c]*b)
  if len(a)>2*n:
    break
a.sort(reverse=True)
print(sum(a[:n]))
### BUGGY CODE ###

K, T = map(int, input().split())
a = list(map(int, input().split()))
# print(a)
m = 10 ** 5
for situ in range(0, 2 ** T):
    block_a = 0
    block_b = 0
    for j in range(T):
        if (situ >> j) & 1:
            block_a += a[j]
        else:
            block_b += a[j]
    diff = abs(block_a - block_b)
    # print(bin(situ), block_a, block_b, diff)
    m = min(diff, m)
print(max(0, m - 1))

### FIXED CODE ###

K, T = map(int, input().split())
a = list(map(int, input().split()))

M = max(a)
ans = max(M - 1 - (K - M), 0)
print(ans)