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

import sys
from io import StringIO
import unittest


def resolve():
    N, K = [int(i) for i in input().split()]
    H = [int(i) for i in input().split()]
    for i in range(K):
        if len(H) > 0:
            idx = H.index(max(H))
            H[idx] = 0
        else:
            break
    sumH = 0
    if len(H) > 0:
        sumH = sum(H)
    print(sumH)


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)

    def test_入力例_1(self):
        input = """3 1
4 1 5"""
        output = """5"""
        self.assertIO(input, output)

    def test_入力例_2(self):
        input = """8 9
7 9 3 2 3 8 4 6"""
        output = """0"""
        self.assertIO(input, output)

    def test_入力例_3(self):
        input = """3 0
1000000000 1000000000 1000000000"""
        output = """3000000000"""
        self.assertIO(input, output)


if __name__ == "__main__":
    # unittest.main()
    resolve()


### FIXED CODE ###

import sys
from io import StringIO
import unittest


def resolve():
    N, K = [int(i) for i in input().split()]
    H = sorted([int(i) for i in input().split()])
    if N <= K:
        H = [0]
    else:
        # if K < (N - K):
        for i in range(K):
            H[len(H) - 1 - i] = 0
        # else:
        #     Hs = []
        #     for i in range(N - K):
        #         Hs.append(H[i])
        #     H = Hs
    print(sum(H))


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)

    def test_入力例_1(self):
        input = """3 1
4 1 5"""
        output = """5"""
        self.assertIO(input, output)

    def test_入力例_2(self):
        input = """8 9
7 9 3 2 3 8 4 6"""
        output = """0"""
        self.assertIO(input, output)

    def test_入力例_3(self):
        input = """3 0
1000000000 1000000000 1000000000"""
        output = """3000000000"""
        self.assertIO(input, output)


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

# https://atcoder.jp/contests/abc051/tasks/abc051_b

# n n,
K, S = map(int, input().split())

# initialize
ans = 0

# logic: 全探索: 基本形
for i in range(K + 1):
    if i + K+1 + K+1 < S:
        continue
    for j in range(K + 1):
        if i + j + K+1 < S:
            continue
        for k in range(K + 1):
            if i+j+k == S:
                ans += 1

print(ans)


### FIXED CODE ###

k,s=map(int,input().split())
count=0
for a in range(k+1):
  for b in range(k+1):
    if 0<=s-a-b<=k:
      count+=1
print(count)
### BUGGY CODE ###

N = int(input())
alist = [int(input()) for i in range(N)]
MOD = 998244353

asum = [0] 
for i in range(N):
    asum += [asum[-1] + alist[i]]
S = asum[-1]
Sharf = S / 2
#dptable[i番目を振り分ける][Rの合計][Gの合計] -> そこから成立する三角形の数
tbsize = int(Sharf//1)+1
dptable = [[[0 for i in range(tbsize)] for j  in range(tbsize)] for k in range(N)]
dpflag = [[[False for i in range(tbsize)] for j  in range(tbsize)] for k in range(N)]

def ddp(cur_N, R, G):
    B = asum[cur_N] - R - G
    if cur_N == N: #末端
        return 1
    if dpflag[cur_N][R][G]: #DPテーブルにある
        return dptable[cur_N][R][G]
    #そうではない場合は計算が必要
    ai = alist[cur_N]
    #aiをRGBのどれかに振り分ける
    retR = 0 if (R+ai) >= Sharf else ddp(cur_N+1, R+ai, G) #Rに振り分ける, 三角形ができない場合は0
    retG = 0 if (G+ai) >= Sharf else ddp(cur_N+1, R, G+ai)
    retB = 0 if (B+ai) >= Sharf else ddp(cur_N+1, R, G)
    ret = (retR+retG+retB) % MOD
    #DPテーブルに記憶
    dpflag[cur_N][R][G] = True
    dptable[cur_N][R][G] = ret
    return ret
print(ddp(0, 0, 0))

### FIXED CODE ###

N = int(input())
alist = [int(input()) for i in range(N)]
import numpy as np
### 三角形が成立しない場合を数える
alist.sort(reverse=False) #大きい方からチェックするとS/2に早く到達しやすい
MOD = 998244353
asum = [0]
for i in range(N):
    asum += [asum[-1] + alist[i]]
S = asum[-1]
Sharf = S / 2

#dptableA[i番目までは振り分けた][Rの合計] -> そこからR>=S/2となる数
dptableA = np.zeros((N+1, S+1), dtype=np.int) #[[0 for i in range(S+1)] for j in range(N+1)]
dptableA[N, int(np.ceil(Sharf)):] = 1
#dptableB[i番目までは振り分けた][Rの合計] -> そこからR=G=S/2, B=0となる数
dptableB = np.zeros((N+1, S+1), dtype=np.int) #[[0 for i in range(S+1)] for j in range(N+1)]
if S %2 == 0:
    dptableB[N, int(Sharf)] = 1 

#dpの計算をまとめて行う
for i in range(N, 0, -1): #後ろから見ていく
    n = i - 1
    an = alist[n]
    asn = asum[n]
    dptableA[n, 0:asn+1] = (2*dptableA[n+1, 0:asn+1] + dptableA[n+1, an:an+asn+1])%MOD
    #dptableA[n] = [(2*dptableA[n+1][k]+dptableA[n+1][k+alist[n]]) % MOD for k in range(asum[n]+1)]
    dptableB[n, 0:asn+1] = (dptableB[n+1, 0:asn+1] + dptableB[n+1, an:an+asn+1])%MOD
    #dptableB[n] = [(dptableB[n+1][k]+dptableB[n+1][k+alist[n]]) %MOD for k in range(asum[n]+1)]
retA, retB = dptableA[0,0], dptableB[0,0]
#全体 - (ある辺がS/2以上) + (2辺がS/2)
ans = (pow(3, N, MOD) - retA*3 + retB*3) % MOD
print(ans)
### BUGGY CODE ###

import sys
import threading
sys.setrecursionlimit(10**9)
threading.stack_size(128*1024*1024)
x, y = map(int, input().split())
MOD = 10**9+7
cnt = 0

def move(i, j):
    if i > x or j > y:
        return 0

    if i == x and j == y:
        return 1
    else:
        cnt =  ( move(i+1, j+2) ) % MOD + ( move(i+2, j+1) ) % MOD
        return cnt

if (x+y) % 3 != 0:
    print(0)
    sys.exit()
print(move(0, 0))


### FIXED CODE ###

import sys
input = sys.stdin.readline

x, y = map(int, input().split())
MOD = 10**9+7

def nck_tables(mod, n):
    fac = [1, 1] # 階乗テーブル
    ifac = [1, 1] #階乗の逆元テーブル
    inverse = [0, 1] #逆元テーブル

    for i in range(2, n+1):
        fac.append((fac[-1] * i) % mod)
        inverse.append((-inverse[mod % i] * (mod//i)) % mod)
        ifac.append((ifac[-1] * inverse[-1]) % mod)
    return fac, ifac

def nck(n, k, mod, fac, ifac):
    """
    nCkを計算する
    """
    k = min(k, n-k)
    return fac[n] * ifac[k] * ifac[n-k] % mod

if (x+y) % 3 != 0 or x > 2*y or y > 2*x:
    print(0)
    sys.exit()

times = (x+y)//3
k = max(x, y) - times
fac, ifac = nck_tables(MOD, times)
ans = nck(times, k, MOD, fac, ifac)
print(ans)
### BUGGY CODE ###

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

## 種類数の求め方
# 1. A内の要素を取り出して、それがA内に存在するとき：種類＋１
# 2. その要素を重複数だけAから削除してループ

kinds = 0
A = sorted(A)
duplicatedList = []
while len(A) > 0:
    if A[0] in A:
        kinds += 1
        duplicatedList.append(A.count(A[0]))
        for j in range(A.count(A[0])):
            A.remove(A[0])

if kinds <= K:
    print('0')
else:
    duplicatedList = sorted(duplicatedList)
    i = 0
    tmp = 0
    a = kinds
    while a > K:
        a -= 1
        tmp += duplicatedList[i]
        i += 1
    print(tmp)

### FIXED CODE ###

n,k=map(int,input().split())
a=list(map(int,input().split()))
d={}
l=[]
for i in range(n):
    try:
        l[d[a[i]]]+=1
    except:
        d[a[i]]=len(l)
        l.append(1)
ans=0
l.sort()
for i in range(len(l)-k):
    ans+=l[i]
print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10 ** 7)

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N = int(readline())
PATH = [[] for _ in range(N + 1)]
MOD = 10 ** 9 + 7

fact = [0] * (N + 10)
t = 1
for i in range(1, N + 1):
    t *= i
    t %= MOD
    fact[i] = t

for _ in range(N - 1):
    x, y = map(int, readline().split())
    PATH[x].append(y)
    PATH[y].append(x)


def dfs(x, parent, isBlack=True):
    ret = 1
    for v in PATH[x]:
        if v == parent:
            continue

        cnt = dfs(v, x, False)

        if not isBlack:
            cnt += dfs(v, x, True)

        ret *= cnt
        ret %= MOD

    ret %= MOD

    return ret


ans = dfs(1, -1, True) + dfs(1, -1, False)
ans %= MOD
print(ans)


### FIXED CODE ###

import sys
from functools import lru_cache
sys.setrecursionlimit(10 ** 7)

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# TLE

N = int(readline())
PATH = [[] for _ in range(N + 1)]
MOD = 10 ** 9 + 7

for _ in range(N - 1):
    x, y = map(int, readline().split())
    PATH[x].append(y)
    PATH[y].append(x)


dp = [[1] * 2 for _ in range(N+1)]


def dfs(x, parent):
    for v in PATH[x]:
        if v == parent:
            continue
        dfs(v, x)

        dp[x][0] *= (dp[v][0] + dp[v][1])
        dp[x][0] %= MOD
        dp[x][1] *= dp[v][0]
        dp[x][1] %= MOD

    return 0


dfs(1, -1)
ans = sum(dp[1])
ans %= MOD
print(ans)
### BUGGY CODE ###

N=int(input())
H=list(map(int,input().split()))
max_ans=0
for i in range(len(H)):
    A=i
    ans=0
    for j in range(i+1,len(H)):
        if H[A]>=H[j]:
            ans=ans+1
        elif H[A]<H[j]:
            break
        A=A+1
    max_ans=max(ans,max_ans)
print(max_ans)

### FIXED CODE ###

N=int(input())
H=list(map(int,input().split()))
max_ans=0
ans=0
for i in range(N-1):
    if H[i]>=H[i+1]:
        ans=ans+1
    else:
        max_ans=max(ans,max_ans)
        ans=0
max_ans=max(ans,max_ans)
print(max_ans)
### BUGGY CODE ###

x,n = map(int,input().split())
l = [int(x) for x in input().split()]
mp = [False]*101
for i in range(n):
    mp[l[i]] = True



queue = [x]
while(len(queue)>0):
    now = queue.pop(0)
    if(now <= 0 or now >=101):
        print(now)
        break
    if(mp[now]==False):
        print(now)
        break
    
    
    queue.append(now-1)
    queue.append(now+1)


### FIXED CODE ###

x,n = map(int,input().split())
l = [int(x) for x in input().split()]
mp = [False]*101
for i in range(n):
    mp[l[i]] = True



queue = [x]
while(len(queue)>0):
    now = queue.pop(0)
    if(now <= 0 or now >=101):
        print(now)
        break
    if(mp[now]==False):
        print(now)
        break
    
    if(now==x):
        queue.append(now-1)
        queue.append(now+1)
    if(now < x):
        queue.append(now-1)
    if(now > x):
        queue.append(now+1)
### BUGGY CODE ###

as_ = []
for _ in range(int(input())):
    a = int(input())
    if a in as_:
        as_.remove(a)
    else:
        as_.append(a)

print(len(as_))

### FIXED CODE ###

as_ = set()
for _ in range(int(input())):
    a = int(input())
    if a in as_:
        as_.remove(a)
    else:
        as_.add(a)
 
print(len(as_))
### BUGGY CODE ###

def main():
    n, k = map(int, input().split())
    p = list(map(int, input().split()))

    m = 0
    a = 0
    for i in range(n-k+1):
        wa = 0
        for j in range(k):
            wa += p[i+j]
        if m < wa:
            a = i
            m = wa

    ans = 0
    for i in range(a, a+k):
        x = p[i]
        ans += (1/2*x*(x+1))/x

    print(ans)


main()


### FIXED CODE ###

def main():
    n, k = map(int, input().split())
    p = list(map(int, input().split()))

    wa = 0
    for i in range(k):
        wa += p[i]

    m = 0
    a = 0
    for i in range(1, n-k+1):
        wa -= p[i-1]
        wa += p[i+k-1]
        if m < wa:
            a = i
            m = wa

    ans = 0
    for i in range(a, a+k):
        x = p[i]
        ans += (1/2*x*(x+1))/x

    print(ans)


main()
### BUGGY CODE ###

#!/usr/bin/env python3
from itertools import product, permutations, combinations
from bisect import bisect_right,bisect_left
INF = float('inf')

N, K=map(int, input().split())
h=list(map(int, input().split()))
dp = [10**5] * N
dp[0] = 0
for i in range(1, N):
    x = max(0, i-K)
    dp[i] = min([dp[j]+abs(h[j]-h[i]) for j in range(x, i)])
print(dp[-1])

### FIXED CODE ###

N, K=map(int, input().split())
h=list(map(int, input().split()))
dp = [10**5] * N
dp[0] = 0
for i in range(1, N):
    x = max(0, i-K)
    dp[i] = min([dp[j]+abs(h[j]-h[i]) for j in range(x, i)])
print(dp[-1])
### BUGGY CODE ###

import re
q = int(input().split(' ')[1])
s = input()

for i in range(q):
    lr = [int(i) for i in input().split(' ')]
    print(len(re.findall('AC', s[lr[0] - 1:lr[1]])))


### FIXED CODE ###

n, q = tuple(int(i) for i  in input().split(' '))
s = input()

c = [0] * (n + 1)

for i in range(n):
    c[i + 1] = c[i] + (1 if s[i:i + 2] == 'AC' else 0)

for i in range(q):
    l, r = tuple(int(i) for i  in input().split(' '))
    print(c[r - 1] - c[l - 1])
### BUGGY CODE ###

A, B, K = map(int, input().split())

for i in range(K):
    if A >= 1:
        A -= 1
    elif B >= 1:
        B -= 1
    elif A == 0 and B == 0:
        continue

print('{} {}' .format(A, B))

### FIXED CODE ###

A, B, K = map(int, input().split())

if A >= K:
    A -= K
elif A + B >= K:
    B -= K - A
    A = 0
else:
    A = 0
    B = 0

print('{} {}' .format(A, B))
### BUGGY CODE ###

from collections import Counter
n = int(input())
str_list = [input() for i in range(n)]
ans = 0
for i in range(n):
  first = Counter(str_list[i])
  for j in range(n-i-1):
    second = Counter(str_list[j+i+1])
    if first == second:
      ans +=1
print(ans)

### FIXED CODE ###

from collections import Counter
import sys

input = sys.stdin.readline
n = int(input())
str_list = [''.join(sorted(input().rstrip())) for i in range(n)]
ans = 0
count_list = list(Counter(str_list).values())
for i in count_list:
  sum = 0
  for j in range(int(i)):
    sum += j
  ans +=sum
print(ans)
### BUGGY CODE ###

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

L = 50*50
dp = [[0 for _ in range(L+1)] for _ in range(N+1)]
dp[0][0] = 1

for i in range(N):
    a = A[i]
    for j in reversed(range(N)):
        for l in range(L+1):
            if l < a: continue
            dp[j+1][l] += dp[j][l-a]

ans = 0
for j in range(N):
    ans += dp[j+1][(j+1)*K]
print(ans)

### FIXED CODE ###

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

dp = [[[0 for _ in range((N+1)*(L+1))] for _ in range(N+1)] for _ in range(N+1)]
dp[0][0][0] = 1

for j in range(1, N+1):
    for k in range(N+1):
        for s in range((N+1)*(L+1)):
            if s < X[j-1]:
                dp[j][k][s] = dp[j-1][k][s]
            if k >= 1 and s >= X[j-1]:
                dp[j][k][s] = dp[j-1][k][s] + dp[j-1][k-1][s-X[j-1]]
ans = 0
for k in range(1, N+1):
    ans += dp[N][k][k*A]
print(ans)
### BUGGY CODE ###

from heapq import heappush, heappop
from collections import deque
N = int(input())
G = [[] for i in range(N)]
for i in range(N - 1):
    a, b, c = map(int, input().split())
    a, b = a - 1, b - 1
    G[a].append((b, c))
    G[b].append((a, c))

Q, K = map(int, input().split())
K -= 1

INF = float("inf")
d = [INF] * N
d[K] = 0
for i in range(N):
    que = [(0, K)]
    while que:
        cost, v = heappop(que)
        if d[v] < cost:
            continue
        for w, c in G[v]:
            if d[v] + c < d[w]:
                d[w] = d[v] + c
                heappush(que, (d[w], w))

for i in range(Q):
    x, y = map(int, input().split())
    print(d[x - 1] + d[y - 1])


### FIXED CODE ###

from heapq import heappush, heappop
from collections import deque
N = int(input())
G = [[] for i in range(N)]
for i in range(N - 1):
    a, b, c = map(int, input().split())
    a, b = a - 1, b - 1
    G[a].append((b, c))
    G[b].append((a, c))

Q, K = map(int, input().split())
K -= 1

INF = float("inf")
d = [INF] * N
d[K] = 0
que = [(0, K)]
while que:
    cost, v = heappop(que)
    if d[v] < cost:
        continue
    for w, c in G[v]:
        if d[v] + c < d[w]:
            d[w] = d[v] + c
            heappush(que, (d[w], w))

for i in range(Q):
    x, y = map(int, input().split())
    print(d[x - 1] + d[y - 1])
### BUGGY CODE ###

N = int(input())

a_list = list(map(int, input().split()))

cnt = 0
for i in range(N):
  if min(a_list[:i+1]) >= a_list[i]:
    cnt += 1
    
print(cnt)

### FIXED CODE ###

import sys
input = sys.stdin.readline

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

cnt = 0
min_a  = 10 ** 9
for i in range(N):
  min_a  =  min(min_a,a_list[i])
  if min_a >= a_list[i]:
    cnt += 1
    
print(cnt)
### BUGGY CODE ###

n,m=map(int,input().split())
a=list(map(int,input().split()))
for i in range(m):
    b,c=map(int,input().split())
    a+=[c]*b
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 i in range(m)]
bc.sort(key=lambda x:x[1],reverse=True)
for b,c in bc:
    a.extend([c]*b)
    if len(a)>2*n:
        break
a.sort(reverse=True)
print(sum(a[:n]))
### BUGGY CODE ###

from operator import itemgetter


class BIT():
    """一点加算、区間取得クエリをそれぞれO(logN)で答える
    add: i番目にvalを加える
    get_sum: 区間[l, r)の和を求める
    i, l, rは0-indexed
    """
    def __init__(self, n):
        self.n = n
        self.bit = [0] * (n + 1)

    def _sum(self, i):
        s = 0
        while i > 0:
            s += self.bit[i]
            i -= i & -i
        return s

    def add(self, i, val):
        """i番目にvalを加える"""
        i = i + 1
        while i <= self.n:
            self.bit[i] += val
            i += i & -i

    def get_sum(self, l, r):
        """区間[l, r)の和を求める"""
        return self._sum(r) - self._sum(l)



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

def solve(val):
    ruiseki = [0] * (n + 1)
    for i, num in enumerate(a):
        if num >= val:
            ruiseki[i + 1] = ruiseki[i] + 1
        else:
            ruiseki[i + 1] = ruiseki[i] - 1
    b = sorted(enumerate(ruiseki), key = itemgetter(1))
    for i in range(n + 1):
        bit.bit[i] = 0
    res = 0
    for i, _ in b:
        bit.add(i, 1)
        res += bit.get_sum(0, i)
        if res >= cnt:
            return True
    return False


cnt = 0
for i in range(n):
    cnt += n - i
cnt = (cnt + 1) // 2

bit = BIT(n + 1)
ok = 0
ng = 10**9 + 1
while abs(ok - ng) > 1:
    mid = (ok + ng) // 2
    if solve(mid):
        ok = mid
    else:
        ng = mid
print(ok)

### FIXED CODE ###

from operator import itemgetter
import sys
input = sys.stdin.readline


class BIT():
    """一点加算、区間取得クエリをそれぞれO(logN)で答える
    add: i番目にvalを加える
    get_sum: 区間[l, r)の和を求める
    i, l, rは0-indexed
    """
    def __init__(self, n):
        self.n = n
        self.bit = [0] * (n + 1)

    def _sum(self, i):
        s = 0
        while i > 0:
            s += self.bit[i]
            i -= i & -i
        return s

    def add(self, i, val):
        """i番目にvalを加える"""
        i = i + 1
        while i <= self.n:
            self.bit[i] += val
            i += i & -i

    def get_sum(self, l, r):
        """区間[l, r)の和を求める"""
        return self._sum(r) - self._sum(l)



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


def solve(val):
    val = a_sorted[val]
    ruiseki = [0] * (n + 1)
    for i, num in enumerate(a):
        if num >= val:
            ruiseki[i + 1] = ruiseki[i] + 1
        else:
            ruiseki[i + 1] = ruiseki[i] - 1
    b = sorted(enumerate(ruiseki), key = itemgetter(1))
    for i in range(n + 1):
        bit.bit[i] = 0
    res = 0
    for i, _ in b:
        bit.add(i, 1)
        res += bit.get_sum(0, i)
        if res >= cnt:
            return True
    return False


cnt = 0
for i in range(n):
    cnt += n - i
cnt = (cnt + 1) // 2

bit = BIT(n + 1)
ok = 0
ng = n
while abs(ok - ng) > 1:
    mid = (ok + ng) // 2
    if solve(mid):
        ok = mid
    else:
        ng = mid
print(a_sorted[ok])
### BUGGY CODE ###

n, m = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(n)]

s = set([])
ans = n
for _ in range(m):
    memo = [0] * (m + 1)
    flag = [0] * (n + 1)
    for j in range(m):
        for i in range(n):
            if flag[i] == 0 and a[i][j] not in s:
                memo[a[i][j]] += 1
                flag[i] = 1
    idx = 0
    mmax = 0
    for i, me in enumerate(memo):
        if me > mmax:
            idx = i
            mmax = me

    ans = min(ans, mmax)
    s.add(idx)

print(ans)





### FIXED CODE ###

n, m = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(n)]

s = set([])
ans = n
for _ in range(m):
    memo = [0] * (m + 1)
    flag = [0] * (n + 1)
    for j in range(m):
        for i in range(n):
            if flag[i] == 0 and a[i][j] not in s:
                memo[a[i][j]] += 1
                flag[i] = 1
    idx = 0
    mmax = 0
    for i, me in enumerate(memo):
        if me > mmax:
            idx = i
            mmax = me

    ans = min(ans, mmax)
    s.add(idx)

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

n,m=[int(_) for _ in input().split()]
a=[int(_) for _ in input().split()]
for iii in range(m):
  b,c=[int(_) for _ in input().split()]
  for jjj in range(b):
    ma=min(a)
    if ma<c:
      a[a.index(ma)]=c
    else:
      break
print(sum(a))

### FIXED CODE ###

from heapq import heappush, heappop
n,m=map(int,input().split())
hq=[]
for _ in input().split():
  heappush(hq,(-int(_),1))
for iii in range(m):
  b,c=map(int,input().split())
  heappush(hq,(-c,b))
s=0
for iii in range(n):
  a=heappop(hq)
  s-=a[0]
  if a[1]!=1:
    heappush(hq,(a[0],a[1]-1))
print(s)
### BUGGY CODE ###

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

    m = 10 ** 9 + 7
    ans = 0
    for i in range(n):
        for j in range(i + 1, n):
            ans += a[i] % m * a[j] % m
            # seki = a[i] * a[j]
            # ans += seki % m
            if ans >= m:
                ans = ans % m
    print(ans)

if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    n = int(input())
    a = list(map(int, input().split()))
    ans = 0
    m = 10 ** 9 + 7
    tmp_sum = 0
    for i in range(n - 1):
        tmp_sum += a[i]
        tmp_sum %= m
        ans += tmp_sum * a[i+1]
        ans %= m
    
    print(ans)


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

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

ct = [0] * (n + 1)
target = [[i] for i in range(n + 1)]

for _ in range(n - 1):
    a, b = map(int, input().split())
    for t in target:
        if a in t:
            t.append(b)

for _ in range(q):
    p, q = map(int, input().split())
    t = target[p]
    for ti in t:
        ct[ti] += q

print(*ct[1:])

### FIXED CODE ###

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

ct = [0] * (n + 1)
e = [[] for _ in range(n + 1)]

for _ in range(n - 1):
    a, b = map(int, input().split())
    e[a].append(b)

qs = [0] * (n + 1)
for _ in range(q):
    p, q = map(int, input().split())
    qs[p] += q

target = [1]
while len(target):
    t = target.pop()
    ct[t] += qs[t]
    for nt in e[t]:
        target.append(nt)
        ct[nt] += ct[t]

print(*ct[1:])
### BUGGY CODE ###

from collections import deque
S=input()
q=int(input())
Q=[]
state=True
ans=deque(S)
for _ in range(q):
    t = input().split()
    if t[0] == "1":
        Q.append(int(t[0]))
    elif t[0] == "2":
        Q.append((int(t[0]),int(t[1]),t[2]))
for que in Q:
    if que == 1:
        state = not state
    else:
        if state:
            if que[1] == 1:
                ans.appendleft(que[2])
            else:
                ans.append(que[2])
        else:
            if que[1] == 2:
                ans.appendleft(que[2])
            else:
                ans.append(que[2])
anss=""
if not state:
    while len(ans) >0:
        anss += ans.pop()
else:
    while len(ans) >0:
        anss += ans.popleft()
print(anss)


### FIXED CODE ###

from collections import deque
S=input()
q=int(input())
Q=[]
state=True
ans=deque(S)
for _ in range(q):
    t = input().split()
    if t[0] == "1":
        Q.append(int(t[0]))
    elif t[0] == "2":
        Q.append((int(t[0]),int(t[1]),t[2]))
for que in Q:
    if que == 1:
        state = not state
    else:
        if state:
            if que[1] == 1:
                ans.appendleft(que[2])
            else:
                ans.append(que[2])
        else:
            if que[1] == 2:
                ans.appendleft(que[2])
            else:
                ans.append(que[2])
anss=""
if not state:
    while len(ans) >0:
        anss += ans.pop()
else:
    while len(ans) >0:
        anss += ans.popleft()
print(anss)