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

# https://atcoder.jp/contests/abc054/tasks/abc054_c

import copy
import sys
input = sys.stdin.readline

# 頂点, 辺の数
N, M = map(int, input().split())

# グラフのリスト
# 各頂点からどこの頂点に向かう辺があるかどうかという情報
Graph_list = [[] for i in range(N)]

# 入力
for i in range(M):
    a, b = map(int, input().split())
    a += -1
    b += -1

    # 無向グラフなのでa, b両方
    Graph_list[a].append(b)
    Graph_list[b].append(a)

ans_count = 0
ans_point_list = []
throwgh_point_list = [-1 for i in range(N)]

def dfs(i, current, throwgh_point_list):   
    # 頂点をN個通ったら終了処理
    if i >= N-1:
        # 最後の点を追加
        throwgh_point_list[i] = current

        global ans_point_list
        # すでにカウント済の経路である場合
        if throwgh_point_list in ans_point_list:
            return

        # すでにカウント済ではないかつ全ての点に到達している場合
        # 順不同で比較
        if set(throwgh_point_list) == set(list(range(N))):
            global ans_count
            ans_count += 1
            ans_point_list.append(copy.copy(throwgh_point_list))
        return

    for j in Graph_list[current]:
        # 現在地を書き込む
        throwgh_point_list[i] = current

        # 次の点に移動する        
        dfs(i + 1, j, throwgh_point_list)

dfs(0, 0, throwgh_point_list)
print(ans_count)

### FIXED CODE ###

# https://atcoder.jp/contests/abc054/tasks/abc054_c

import copy
import sys
input = sys.stdin.readline

# 頂点, 辺の数
N, M = map(int, input().split())

# グラフのリスト
# 各頂点からどこの頂点に向かう辺があるかどうかという情報
Graph_list = [[] for i in range(N)]

# 入力
for i in range(M):
    a, b = map(int, input().split())
    a += -1
    b += -1

    # 無向グラフなのでa, b両方
    Graph_list[a].append(b)
    Graph_list[b].append(a)

ans_count = 0           # 正解の経路の数
visited = [False] * N
visited[0] = True

def dfs(i, current, visited):   
    # 頂点をN個通ったら終了処理
    if i >= N-1:

        # 全ての点に到達している場合
        if all(visited):
            global ans_count
            ans_count += 1
            return 
        return 

    for j in Graph_list[current]:
        if visited[j] == False:
            # 現在地を書き込む
            visited[j] = True
            # 次の点に移動する        
            dfs(i + 1, j, visited)

            visited[j] = False

dfs(0, 0, visited)
print(ans_count)
### BUGGY CODE ###

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

def d_or_n(N, A):

    while True:
        for i in range(N-1):
            for j in range(i+1, N):
                if A[i] == A[j]:
                    print('NO')     
                    return False      
        print('YES')
        break

d_or_n(N, A)


### FIXED CODE ###

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

if len(A) != len(set(A)):
    print('NO')
else:
    print('YES')
### BUGGY CODE ###

import sys
import numpy as np

read = sys.stdin.buffer.read

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

hw = []
w = np.zeros(3*10**5,dtype=np.int64)
h = np.zeros(3*10**5,dtype=np.int64)
 
for i in range(M):
    h_i, w_j = map(int, input().split())
    hw.append([h_i-1, w_j-1])
    h[h_i-1] += 1
    w[w_j-1] += 1

a = 0
d = 0
for i in np.where(h==h.max())[0]:
    for j in np.where(w==w.max())[0]:
        mxh_v = h[i]
        mxw_v = w[j]

        if [i,j] in hw:
            a = max(a, mxh_v + mxw_v - 1)
        else:
            a = max(a, mxh_v + mxw_v)
            d = 1
    if d == 1:
        break

print(a)

### FIXED CODE ###

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

hw = set()
w = [0] * 3*10**5
h = [0] * 3*10**5

for i in range(M):
    h_i, w_j = map(int, input().split())
    hw.add((h_i-1) + (w_j-1)*3*10**6)
    h[h_i-1] += 1
    w[w_j-1] += 1

a = 0
d = 1
mxh_v = max(h)
mxw_v = max(w)

x = [i for i,j in enumerate(h) if j == mxh_v]
y = [i for i,j in enumerate(w) if j == mxw_v]

for i in x:
    for j in y:
        if not(i + j*3*10**6 in hw):
            print(mxh_v+mxw_v)
            exit()
print(mxh_v+mxw_v-d)
### BUGGY CODE ###

a_num = int(input())
b_num = int(input())
c_num = int(input())
x = int(input())

tried = []
coins = []

def dfs(a, b, c):
  if (a, b, c) in tried:
    return None
  tried.append((a, b, c))
  total = a*500 + b*100 + c*50  
  if total > x or a > a_num or b > b_num or c > c_num:
    return None
  elif total == x:
    coins.append((a, b, c))
  else:
    dfs(a+1, b, c)
    dfs(a, b+1, c)
    dfs(a, b, c+1)
    
dfs(0, 0, 0)
print(len(coins))

### FIXED CODE ###

a_num = int(input())
b_num = int(input())
c_num = int(input())
x = int(input())

total = []

for a in range(0, a_num+1):
  for b in range(0, b_num+1):
    for c in range(0, c_num+1):
      total.append(a*500+b*100+c*50)

print(total.count(x))
### BUGGY CODE ###

n, k = map(int, input().split())
p = list(map(lambda x: int(x) - 1, input().split()))
c = list(map(int, input().split()))
    
visited = [False] * n
ans = max(c)

for i in range(n):
    if visited[i]:
        continue
    arr = []
    u = i
    while not visited[u]:
        arr.append(c[u])
        visited[u] = True
        u = p[u]
    s = sum(arr) * (k // len(arr))
    rem = k % len(arr)
    arr += arr
    for f in range(len(arr) // 2):
        ans = max(ans, s + sum(arr[f:f + rem]))
        for g in range(f + 1, len(arr) + 1):
            if g - f > k:
                break
            ans = max(ans, sum(arr[f:g]))
print(ans)
    


### FIXED CODE ###

n, k = map(int, input().split())
p = list(map(lambda x: int(x) - 1, input().split()))
c = list(map(int, input().split()))
    
visited = [False] * n
ans = max(c)

for i in range(n):
    if visited[i]:
        continue
    arr = []
    u = i
    while not visited[u]:
        arr.append(c[u])
        visited[u] = True
        u = p[u]
    s = sum(arr) * (k // len(arr))
    rem = k % len(arr)
    if k // len(arr) >= 1:
        s -= sum(arr)
        rem += len(arr)
        
    arr += arr + arr
    pref_sum = [0]
    for i in arr:
        pref_sum.append(pref_sum[-1] + i)
    # print(pref_sum, s, rem) 
            
    for f in range(len(arr) // 2):
        # ans = max(ans, s + sum(arr[f:f + rem])) 
        for g in range(f + 1, len(pref_sum)):
            if g - f <= k:
                ans = max(ans, pref_sum[g] - pref_sum[f])
            if g - f <= rem:
                ans = max(ans, s + pref_sum[g] - pref_sum[f])
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

def binToInt(X):
    ret = 0
    for s in X:
        ret <<= 1
        if s == '1':
            ret += 1
    return ret

def cnt(n):
    ret = 0
    while n > 0:
        n, r = divmod(n, 2)
        ret += r
    return ret

def f(n):
    ret = 0
    while n > 0:
        ret += 1
        n %= cnt(n)
    return ret

N = int(input())
X = binToInt(input().rstrip())

for i in range(N)[::-1]:
    print(f(X ^ (1 << i)))


### FIXED CODE ###

N = int(input())
X = input()

cnt = X.count('1')
if cnt == 1:
    for x in X[:-1]:
        if x == '0':
            print(1)
        else:
            print(0)
    if X[-1] == '1':
        print(0)
    else:
        print(2)
    exit()

M = 0
for x in X:
    M <<= 1
    if x == '1':
        M += 1

def solve(n):
    ret = 1
    while n > 0:
        ret += 1
        n %= bin(n).count('1')
    return ret

ans = []
p = M % (cnt + 1)
m = M % (cnt - 1)

for i in range(N):
    if X[i] == '0':
        ans.append(solve((p + pow(2, N - i - 1, cnt + 1)) % (cnt + 1)))
    else:
        ans.append(solve((m - pow(2, N - i - 1, cnt - 1)) % (cnt - 1)))
print(*ans, sep='\n')
### BUGGY CODE ###

import bisect
N, K = [int(_) for _ in input().split()]
A = sorted([int(_) for _ in input().split()])
il = bisect.bisect_left(A, 0)
ir = bisect.bisect_right(A, 0)
Am = [-a for a in A[:il][::-1]]
Ap = A[ir:]
A0 = ir - il


def calc(B, x):
    c = 0
    for i, b in enumerate(B):
        c += bisect.bisect_left(B[i + 1:], x // b + 1)
    return c


def check(x):
    #積がx以下になるような組み合わせの個数がK個以上であればTrue
    if x < 0:
        c = 0
        for a in Am:
            b = (-x - 1) // a + 1
            c += bisect.bisect_left(Ap, b)
        return len(Ap) * len(Am) - c >= K
    elif x == 0:
        return len(Ap) * len(Am) + len(A) * (len(A) - 1) // 2 - (
            len(A) - A0) * (len(A) - A0 - 1) // 2 >= K
    else:
        return len(Ap) * len(Am) + len(A) * (
            len(A) - 1) // 2 - (len(A) - A0) * (len(A) - A0 - 1) // 2 + calc(
                Ap, x) + calc(Am, x) >= K


#答えは[-10^18,10^18]の間
lb = -10**18 - 1
rb = 10**18 + 1
# Min x for check(x) == True
while rb - lb > 1:
    mid = (rb + lb) // 2
    if check(mid):
        rb = mid
    else:
        lb = mid
print(rb)


### FIXED CODE ###

import numpy as np
from numba import njit
N,K=[int(_) for _ in input().split()]
A = np.array([int(_) for _ in input().split()],dtype=int)
A.sort()


@njit
def main(N,K,A):
    lb = -10**18-1
    rb = 10 ** 18 + 1
    while rb - lb > 1:
        target = (rb + lb) // 2
        if 1:
            cnt=0
            for i, a in enumerate(A):
                if a==0:
                    d = i if target >= 0 else 0
                elif a < 0:
                    il = np.searchsorted(A,0- (-target)//a,side='left')
                    d = max(i - il, 0)
                else:
                    ir = np.searchsorted(A,target//a,side='right')
                    d = min(ir, i)
                cnt+=d
        if cnt>=K:
            rb = target
        else:
            lb = target
    return rb

print(main(N,K,A))
### BUGGY CODE ###

import numpy as np
from numba import njit, i8, u1, void, b1
import heapq
import math

@njit(void(i8,i8,i8,i8,b1[:,:]),cache=True)
def solve(ch,cw,dh,dw,road_map):

    h,w = road_map.shape

    queue = [[0,ch,cw]]
    used_map = np.full((h,w),-1,dtype=np.int64)

    #move walk
    while used_map[dh][dw] == -1 and len(queue) != 0:
        dot = heapq.heappop(queue)
        if dot[1] < 0 or dot[2] < 0 or dot[1] >= h or dot[2] >= w:
            continue
        if used_map[dot[1]][dot[2]] > -1 and used_map[dot[1]][dot[2]] <= dot[0]:
            continue
        if road_map[dot[1]][dot[2]] == True:
            continue
        used_map[dot[1]][dot[2]] = dot[0]

        for x in range(-2,3,1):
            for y in range(-2,3,1):
                if not(dot[1]+ x < 0 or dot[2]+y < 0 or dot[1]+x >= h or dot[2]+y >= w):
                    if used_map[dot[1]+x][dot[2]+y] == -1 and road_map[dot[1]+x][dot[2]+y] == False:
                        if abs(x)+abs(y) <= 1:
                            heapq.heappush(queue,[dot[0],dot[1]+x,dot[2]+y])
                        else:
                            heapq.heappush(queue,[dot[0]+1,dot[1]+x,dot[2]+y])

    print(used_map[dh,dw])

h,w = map(int,input().split())
ch,cw = map(int,input().split())
ch,cw = ch-1,cw-1
dh,dw = map(int,input().split())
dh,dw = dh-1,dw-1
road_map = np.array([[c=="#" for c in input()] for _ in range(h)])

solve(ch,cw,dh,dw,road_map)



### FIXED CODE ###

#shotoyooさんのコードをお借りしてテスト

import numpy as np
from numba import njit, b1, i4, i8, f8
from heapq import heappop as hpp, heappush as hp

@njit((b1[:, :],i8,i8,i8,i8), cache=True)
def main(ss,ch,cw,dh,dw):
    inf = 1<<30
    h,w = ss.shape
    start = ch*w+cw
    goal = dh*w+dw
    n = h*w
    seen = np.full(n, inf, np.int64)
    seen[start] = 0
    q = [(0, start)] # ワープ回数, 現在位置, 最後の道の位置
    while q:
        pnum,pu = hpp(q)
        ux,uy = divmod(pu,w)
        if pu==goal:
            break
        for xx in range(-2, 3):
            for yy in range(-2, 3):
                if xx==yy==0:
                    continue
                if abs(xx)+abs(yy)<=1:
                    vv = 0
                else:
                    vv = 1
                x,y = ux+xx, uy+yy
                u = x*w + y
                num = pnum+vv
                if x<0 or y<0 or x>=h or y>=w or ss[x][y]:
                    continue
        #         print(x,y)
                if seen[u]>num:
                    seen[u] = num
                    hp(q,(num, u))
                
    val = seen[goal]
    if val==inf:
        return -1
    else:
        return val
      

h,w = map(int, input().split())
ch,cw = map(int, input().split())
dh,dw = map(int, input().split())
ch -= 1
cw -= 1
dh -= 1
dw -= 1
ss = np.array([[c=="#" for c in input()] for _ in range(h)])

print(main(ss,ch,cw,dh,dw))
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
amini = a.index(min(a))
a = a[amini:]+a[:amini]


for i in range(a[0]+1):
    b = [i*2]
    for j in range(1,n):
        c = a[j-1]*2-b[-1]
        if not (c<0):
            b.append(c)
        else:
            break
    if len(b)==n and (b[0]+b[-1] == a[-1]*2):
        b = b[-amini:]+b[:-amini]
        print(*b)
        exit(0)

### FIXED CODE ###

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

suma = sum(a)
suma2 = sum([a[x] for x in range(1,n,2)])
b = [suma-suma2*2]
for i in range(1,n):
    b.append(a[i-1]*2-b[i-1])
print(*b)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
# abc127/abc127_d
import sys

s2nn = lambda s: [int(c) for c in s.split(' ')]
ss2nn = lambda ss: [int(s) for s in list(ss)]
ss2nnn = lambda ss: [s2nn(s) for s in list(ss)]
i2s = lambda: sys.stdin.readline().rstrip()
i2n = lambda: int(i2s())
i2nn = lambda: s2nn(i2s())
ii2ss = lambda n: [i2s() for _ in range(n)]
ii2nn = lambda n: ss2nn(ii2ss(n))
ii2nnn = lambda n: ss2nnn(ii2ss(n))

def main():
    N, M = i2nn()
    A = i2nn()
    for j in range(M):
        B, C = i2nn()
        A += [C] * B
    A.sort(reverse=True)
    print(sum(A[:N]))
    return

main()


### FIXED CODE ###

# -*- coding: utf-8 -*-
# abc127/abc127_d
import sys
from operator import itemgetter

s2nn = lambda s: [int(c) for c in s.split(' ')]
ss2nn = lambda ss: [int(s) for s in list(ss)]
ss2nnn = lambda ss: [s2nn(s) for s in list(ss)]
i2s = lambda: sys.stdin.readline().rstrip()
i2n = lambda: int(i2s())
i2nn = lambda: s2nn(i2s())
ii2ss = lambda n: [i2s() for _ in range(n)]
ii2nn = lambda n: ss2nn(ii2ss(n))
ii2nnn = lambda n: ss2nnn(ii2ss(n))

      


def main():
    N, M = i2nn()
    A = [(1, x) for x in i2nn()]
    S = [0] * M
    for j in range(M):
        S[j] = tuple(i2nn())
    S.extend(A)
    R = sorted(S, key=itemgetter(1))
    sum = 0
    while True:
        p = R.pop()
        if N - p[0] > 0:
            sum += p[0] * p[1]
            N -= p[0]
        else:
            sum += p[1] * N
            break
    print(sum)
    return

main()
### BUGGY CODE ###

S = input()
N = len(S)

a = 0
while a == 0:
    S = S.replace("01", "")
    S = S.replace("10", "")
    if "01" in S or "10" in S:
        a = 0
    else:
        a = 1

print(str(N - len(S)))

### FIXED CODE ###

S = input()
N = len(S)
c0 = S.count("0")
c1 = S.count("1")
 
print(2*min(c0, c1))
### BUGGY CODE ###

#!/mnt/c/Users/moiki/bash/env/bin/python
N,K = map(int, input().split())
A = [ [int(j) for j in input().split()] for i in range(N)]
# I = [ [j for j in range(1,N+1) if Ai[j]] for Ai in A]
MOD = 10**9 + 7

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

# import numpy as np
# npA = np.array(A).astype(np.uint64)

def prod2(A,B):
    global N
    C = [ [0]*N for _ in range(N)]
    for i in range(N):
        for j in range(N):
            tmp = 0
            for k in range(N):
                tmp += A[i][k] * B[k][j]
            C[i][j] = tmp
    return C


def prod(A,n):
    if n == 0:
        C = [ [0]*(N) for _ in range(N)]
        for i in range(N):
                C[i][i] = 1
        return C

    elif n == 1:
        return A

    elif n % 2 == 1:
        return prod2( A , prod(A,n-1))

    elif n % 2 == 0:
        return prod2( prod(A,n//2), prod(A,n//2))
    
    

ans = 0
# M = np.linalg.matrix_power(A, K)
M = prod(A,K)
for i in range(1,N+1):
    for j in range(1,N+1):
        # dp[i][j] = np.linalg.matrix_power(A, K)[i-1][j-1].item()
        # ans += dp[i][j] % MOD
        # ans += np.linalg.matrix_power(A, K)[i-1][j-1].item() % MOD
        # ans += M[i-1,j-1].item() % MOD
        ans += M[i-1][j-1] % MOD

print(ans%MOD)



### FIXED CODE ###

#!/mnt/c/Users/moiki/bash/env/bin/python
N,K = map(int, input().split())
A = [ [int(j) for j in input().split()] for i in range(N)]
# I = [ [j for j in range(1,N+1) if Ai[j]] for Ai in A]
MOD = 10**9 + 7

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

S = [[1]*N]
KDIG = [0]*70

for i in range(1,61):
    if K % (1<<i) :
        KDIG[i-1] = 1
        K -= K%(1<<i)


def prod(A,B,k,l,m):#A:k*l,B:l*m
 
    C=[[None for i in range(m)] for j in range(k)]
 
    for i in range(k):
        for j in range(m):
            ANS=0
            for pl in range(l):
                ANS=(ANS+A[i][pl]*B[pl][j])%MOD
 
            C[i][j]=ANS
 
    return C



for i in range(60):
    if KDIG[i] == 1:
        S = prod(S,A,1,N,N)

    A = prod(A,A,N,N,N)
print(sum(S[0])%MOD)

# for i in range(1,N+1):
#     for j in range(1,N+1):
#         # dp[i][j] = np.linalg.matrix_power(A, K)[i-1][j-1].item()
#         # ans += dp[i][j] % MOD
#         # ans += np.linalg.matrix_power(A, K)[i-1][j-1].item() % MOD
#         # ans += M[i-1,j-1].item() % MOD
#         ans += M[i-1][j-1] % MOD

# print(ans%MOD)
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
ans = a[0]
for i in a[1:]:
  ans *= i
if ans > 10**18:
  print(-1)
else:
  print(ans)

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
if 0 in a:
  print(0)
  exit()
ans = a[0]
for i in a[1:]:
  ans *= i
  if ans > 10**18:
    ans = -1
    break
print(ans)
### BUGGY CODE ###

import heapq
def SME(start,end):
    if end > N : end = N
    count = 0
    for i,x in enumerate(Whole[start:end]):
        heapq.heappush(A,[x,i])
    for j in range(start,end):
        a = heapq.heappop(A)
        if None not in ANS[a[1]:a[1]+L] : continue
        for i in range(L):
            idx = a[1] + i
            try :
                if ANS[idx] : continue
                else :
                    ANS[idx] = a[0]
                    count += 1
            except IndexError : continue
        if count > N * parameter : break
    for i in range(L):
        if ANS[i] : continue
        else : ANS[i] = min(Whole[:i+1])
    i = L
    while i < N :
        if None not in ANS[i:i+L] :
            i += L
            continue
        if ANS[i] : 
            i += 1
            continue
        else : 
            ANS[i] = min(Whole[i+1-L:i+1])
            i+=1
    return ANS
[N,L] = [int(x) for x in input().split()]
Whole = [int(x) for x in input().split()]
A = []
parameter = 0.999
ANS = [None]*N
ANS = SME(0, N)
for i in ANS[L-1:-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 ###

n = int(input())
l = list(map(int,input().split(" ")))
l.sort()
l.reverse()
cnt = 0 
flag = False
for i in range(0,n-2):
    a = l[i]
    for j in range(i+1,n-1):
        b = l[j]
        if i == j:
            continue
        for k in range(j+1,n):
            if i == k and j == k:
                continue
            c = l[k]
            if a >= b + c:
                break
            if a < b + c and b < a + c and c < a + b:
                cnt+=1
            else:
                flag=True
                break
print(cnt)

### FIXED CODE ###

n = int(input())
l = list(map(int,input().split(" ")))
l.sort()
cnt = 0 
import bisect
for i in range(0,n-2):
    a = l[i]
    for j in range(i+1,n-1):
        b = l[j]
        target = a + b 
  #      print("#",a,b)
        f1 = bisect.bisect_left(l,target,j+1,n)
        cnt+= f1 - 1- j
   #     print("cnt: ",cnt)
print(cnt)
### BUGGY CODE ###

N, C = map(int, input().split())
xs = []
vs = []
for i in range(N):
    x, v = map(int, input().split())
    xs += [x]
    vs += [v]

sumVtos = [vs[0]]
for i in range(1, N):
    sumVtos += [sumVtos[-1] + vs[i]]

sumV = sumVtos[-1]
sumVfrs = [sumV]
for i in range(1, N):
    sumVfrs += [sumVfrs[-1] - vs[i - 1]]

# 初手：時計回り
ans = 0
for i in range(N):
    ans1 = sumVtos[i] - xs[i]

    # 2手目：反時計回り
    ans2 = 0
    for j in range(i + 1, N):
        ans2 = max(ans2, sumVfrs[j] - (xs[i] + C - xs[j]))

    ans = max(ans, ans1 + ans2)

# 初手：反時計回り
for i in range(N):
    ans1 = sumVfrs[i] - (C - xs[i])

    # 2手目：時計回り
    ans2 = 0
    for j in range(i):
        ans2 = max(ans2, sumVtos[j] - (C - xs[i] + xs[j]))

    ans = max(ans, ans1 + ans2)

print(ans)


### FIXED CODE ###

N, C = map(int, input().split())
xs = []
vs = []
for i in range(N):
    x, v = map(int, input().split())
    xs += [x]
    vs += [v]


fAs = [0] * N
fAs[0] = vs[0]
for A in range(1, N):
    fAs[A] = fAs[A - 1] + vs[A]
for A in range(N):
    fAs[A] -= xs[A]

gAs = [0] * N
gAs[0] = 0
for A in range(1, N):
    gAs[A] = max(gAs[A - 1], fAs[A - 1])


fBs = [0] * N
fBs[N - 1] = vs[N - 1]
for B in range(0, N - 1)[::-1]:
    fBs[B] = fBs[B + 1] + vs[B]

for B in range(N):
    fBs[B] -= C - xs[B]

gBs = [0] * N
gBs[N - 1] = 0
for B in range(0, N - 1)[::-1]:
    gBs[B] = max(gBs[B + 1], fBs[B + 1])


ans = 0

# 初手：時計回り
for A in range(N):
    ans1 = fAs[A]

    # 2手目：反時計回り
    ans2 = max(0, gBs[A] - xs[A])

    ans = max(ans, ans1 + ans2)


# 初手：反時計回り
for B in range(N):
    ans1 = fBs[B]

    # 2手目：時計回り
    ans2 = max(0, gAs[B] - (C - xs[B]))

    ans = max(ans, ans1 + ans2)

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

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

ans = 0

# 処理系
for i in range(n):
    if min(data[:i+1]) == data[i]:
        ans += 1

print(ans)


### FIXED CODE ###

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

ans = 0

min_ = data[0]
for i in range(n):
    # min_ の更新ができれば ans を更新
    if min_ >= data[i]:
        min_ = data[i]
        ans += 1

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

import numpy

tmp=input()
list=input().split(" ")
array=numpy.zeros(len(list),dtype=">i4")
for i in range(len(list)):
  array[i]=int(list[i])

a=int(input())
sum=numpy.sum(array)

for i in range(a):
  b=input().split(" ")
  if int(b[0]) in array:
    b0=int(b[0])
    b1=int(b[1])
    pos=len(numpy.where(array==b0)[0])
    array=numpy.where(array==b0,b1,array)
    diff=pos*(b1-b0)
    sum+=diff
    print(sum)
  else:
    sum=numpy.sum(array)
    print(sum)
  

### FIXED CODE ###

import numpy

tmp=input()
list=input().split(" ")
list=[int(x) for x in list]
array=numpy.array(list,dtype=">i4")
sum=numpy.sum(array)
all=numpy.zeros(100001,dtype=">i4")
for i in array:
  all[i]+=1
#for i in range(len(list)):
#  array[i]=int(list[i])

a=int(input())

for i in range(a):
  b=input().split(" ")
  b0=int(b[0])
  b1=int(b[1])
  diff=all[b0]*(b1-b0)
  sum+=diff
  all[b1]+=all[b0]
  all[b0]=0
  print(sum)
### BUGGY CODE ###

N, M = map(int, input().split())
A_LIST = sorted(map(int, input().split()))
C_LIST = []
for i in range(M):
    b, c = map(int, input().split())
    for _ in range(b):
        C_LIST.append(c)
C_LIST.sort(reverse=True)
for i in range(min(N, len(C_LIST))):
    A_LIST[i] = max(A_LIST[i], C_LIST[i])
print(sum(A_LIST))


### FIXED CODE ###

import heapq

N, M = map(int, input().split())
A_LIST = list(map(int, input().split()))
BC_LIST = []
heapq.heapify(A_LIST)
for i in range(M):
    b, c = map(int, input().split())
    BC_LIST.append([b, c])
BC_LIST.sort(reverse=True, key=lambda x: x[1])  # C降順にソート
for b, c in BC_LIST:
    for _ in range(b):
        tmp = heapq.heappop(A_LIST)
        if tmp < c:
            heapq.heappush(A_LIST, c)
        else:
            heapq.heappush(A_LIST, tmp)
            break
print(sum(A_LIST))