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

N,M=map(int,input().split())
A=list(map(int,input().split()))
B=[0]*M
C=[0]*M
for i in range(M):
    B[i],C[i]=map(int,input().split())

for i in range(M):
    A.sort()
    for j in range(B[i]):
        if A[j] < C[i]:
            A[j]=C[i]
        else:
            break
        if j==N-1:
            break
print(sum(A))      




### FIXED CODE ###

#!/usr/bin/env python3
import bisect
import numpy as np

N, M = list(map(int, input().split()))
a_list = list(map(int, input().split()))
bc_list = []

for i in range(M):
    b, c = list(map(int, input().split()))
    bc_list.append((b, c))

bc_list = sorted(bc_list, key=lambda x: x[1], reverse=True)
a_list = sorted(a_list)

fix_list = []
s = 0
b, c = bc_list[0]
bc_index = 0
count_b = 0

for a in a_list:
    if count_b >= b:
        bc_index += 1
        if bc_index >= len(bc_list):
            s += a
            continue
        count_b = 0
        b, c = bc_list[bc_index]

    if a < c:
        s += c
    else:
        s += a
    count_b += 1

ans = s
print(ans)
### BUGGY CODE ###

N,M = map(int,input().split())
count = 0
while(1):
    if N>=1:
        if M>=2:
            N -= 1
            M -= 2
            count += 1
        else:
            break
    elif M >= 4 :
        M -= 4
        count += 1
    else:
        break
        
print(count)


### FIXED CODE ###

import math
N,M = map(int,input().split())
count = 0
if N*2>M:
    count = math.floor(M/2)
else:
    temp=M-2*N
    count = N+math.floor(temp/4)

print(count)
### BUGGY CODE ###

#!/usr/bin/env python
import sys
import re
from collections import deque, defaultdict
from itertools import combinations, combinations_with_replacement
import bisect
from math import factorial, sqrt, log, ceil, floor
sys.setrecursionlimit(1000000)


def main():
    #N, M = map(int, input().split())
    #N, K = map(int, input().split())
    #ps = list(map(int, input().split()))

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

    dp = [defaultdict(int)]
    dp[0][0] = 0
    for i in range(N):
        w, v = map(int, input().split())
        keys = list(dp[i].keys())
        new_dp = defaultdict(int)
        for key in keys:
            new_dp[key] = max([new_dp[key], dp[i][key]])
            new_w = key + w
            if new_w <= W:
                new_dp[new_w] = max([new_dp[new_w], dp[i][key] + v])
        dp.append(new_dp)
    print(max(dp[N].values()))


if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python
import sys
import re
from collections import deque, defaultdict
from itertools import combinations, combinations_with_replacement
import bisect
from math import factorial, sqrt, log, ceil, floor
sys.setrecursionlimit(1000000)


def main():
    #N, M = map(int, input().split())
    #N, K = map(int, input().split())
    #ps = list(map(int, input().split()))

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

    dp = [defaultdict(int)]
    dp[0][0] = 0
    for i in range(N):
        w, v = map(int, input().split())
        keys = sorted(list(dp[i].keys()))
        new_dp = defaultdict(int)
        for key in keys:
            new_dp[key] = max([new_dp[key], dp[i][key]])
            new_w = key + w
            if new_w <= W:
                new_dp[new_w] = max([new_dp[new_w], dp[i][key] + v])

        max_value = 0
        for key in sorted(new_dp.keys()):
            if max_value > new_dp[key]:
                del new_dp[key]
            else:
                max_value = new_dp[key]

        dp.append(new_dp)
    print(max(dp[N].values()))


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

n,k=[int(i) for i in input().split()]
step=[int(i) for i in input().split()]
dp=[0]*n
for i in range(1,n):
  cost=min([dp[j] + abs(step[i]-step[j]) for j in range(max(i-k,0),i)])
  dp[i]=cost
print(dp[n-1])

### FIXED CODE ###

def solve():
  n,k=[int(i) for i in input().split()]
  step=[int(i) for i in input().split()]
  dp=[0]*n
  for i in range(1,n):
    dp[i]=min([dp[j] + abs(step[i]-step[j]) for j in range(max(i-k,0),i)])
  return dp[n-1]
print(solve())
### BUGGY CODE ###

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

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

for i in range(n):
    if b[i]<=0:
        c[i]='No'
    else:
        c[i]='Yes'

for i in range(n):
    print(c[i])


### FIXED CODE ###

n,k,q = map(int,input().split())
a=[int(input()) for i in range(q)]
b=[k-q]*n
c=[0]*n

for i in range(q):
    b[a[i]-1] +=1
    
for i in range(n):
    if b[i]<=0:
        c[i]='No'
    else:
        c[i]='Yes'

for i in range(n):
    print(c[i])
### BUGGY CODE ###

#!/usr/bin/env python3

# from numba import njit
import sys
sys.setrecursionlimit(10**8)
# input = stdin.readline

# @njit
def solve(n,k,r,s,p,t):
  winHand = {"r":"p", "s":"b", "p":"s"}
  bestHandMemo = [""]*(n+1) # i手目の勝ち手
  
  def calcPoint(char):
    if char == "r":
      return p
    elif char == "s":
      return r
    elif char == "p":
      return s
    else:
      raise ValueError
  def dp(i):
    if i == 0:
      return 0
    elif i <= k:
      bestHandMemo[i-1] = winHand[t[i-1]] # 自由に出せる
      return dp(i-1) + calcPoint(t[i-1])
    elif winHand[t[i-1]] == bestHandMemo[i-k-1]:
      bestHandMemo[i-1] = "" # あいこでも負けても同じこと
      return dp(i-1)
    else: # 勝てる
      bestHandMemo[i-1] = winHand[t[i-1]]
      return dp(i-1) + calcPoint(t[i-1])
  
  memo = [0]*(n+1)
  for i in range(n+1):
    memo[i] = dp(i)

  return memo[n]
    



def main():
  N,K = map(int,input().split())
  R,S,P = map(int,input().split())
  T = input()
  print(solve(N,K,R,S,P,T))
  return

if __name__ == '__main__':
  main()


### FIXED CODE ###

#!/usr/bin/env python3

# from numba import njit
import sys
sys.setrecursionlimit(10**8)
# input = stdin.readline

# @njit
def solve(n,k,r,s,p,t):
  winHand = {"r":"p", "s":"b", "p":"s"}
  bestHandMemo = [""]*(n+1) # i手目の勝ち手
  
  memo = [-1]*(n+1)
  def calcPoint(char):
    if char == "r":
      return p
    elif char == "s":
      return r
    elif char == "p":
      return s
    else:
      raise ValueError
  def dp(i):
    if i == 0:
      return 0
    elif memo[i] != -1:
      return memo[i]
    elif i <= k:
      bestHandMemo[i-1] = winHand[t[i-1]] # 自由に出せる
      return dp(i-1) + calcPoint(t[i-1])
    elif winHand[t[i-1]] == bestHandMemo[i-k-1]:
      bestHandMemo[i-1] = "" # あいこでも負けても同じこと
      return dp(i-1)
    else: # 勝てる
      bestHandMemo[i-1] = winHand[t[i-1]]
      return dp(i-1) + calcPoint(t[i-1])
  
  for i in range(n+1):
    memo[i] = dp(i)

  return memo[n]
    



def main():
  N,K = map(int,input().split())
  R,S,P = map(int,input().split())
  T = input()
  print(solve(N,K,R,S,P,T))
  return

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

def countAC(s):
    index = []
    for i in range(N-1):
        if s[i] == 'A':
            if s[i+1] == 'C':
                index.append(i)
                continue
    return index

N,Q = (int(_) for _ in input().split())
S = input()
SIndex = countAC(S)
out = 0
for i in range(Q):
    l,r = (int(_) for _ in input().split())
    for index in SIndex:
        if l-1 <= index < r-1:
            out += 1
    print(out)
    out = 0


### FIXED CODE ###

def countAC(s):
    counter = 0
    index = [0]
    for i in range(1,N):
        if s[i-1] == 'A':
            if s[i] == 'C':
                counter += 1
                index.append(counter)
                continue
        index.append(counter)
    return index

N,Q = (int(_) for _ in input().split())
S = input()
SIndex = countAC(S)
out = 0
for i in range(Q):
    l,r = (int(_) for _ in input().split())
    print(SIndex[r-1] - SIndex[l-1])
### BUGGY CODE ###

from collections import deque
h, w = map(int, input().split())
s = [list(input()) for i in range(h)]
ans = 0
for i in range(h):
    for j in range(w):
        if s[i][j] == ".":
            ans += 1
s = [["#"] + i + ["#"] for i in s]
s = [["#"]*(w+2)] + s + [["#"]*(w+2)]
pos = [[1, 1, 0]]
pos=deque(pos)
while len(pos) > 0:
    x, y, cnt = pos.popleft()
    if x == h and y == w:
        print(ans-(cnt+1))
        exit()
    s[x][y] =0
    if s[x-1][y] == ".":
        pos.append([x-1, y, cnt+1])
    if s[x+1][y] == ".":
        pos.append([x+1, y, cnt+1])
    if s[x][y-1] == ".":
        pos.append([x, y-1, cnt+1])
    if s[x][y+1] == ".":
        pos.append([x, y+1, cnt+1])
print(-1)

### FIXED CODE ###

import sys
H,W=map(int,input().split())
L = [[0 for j in range(W)] for i in range(H)]
c=0
for i in range(H):
  a=list(input())
  c+=a.count(".")
  L[i]=a
#幅優先探索？
subete=[[0,0]]
ans = [[] for i in range(H*W+1)]
ans[0].append([0,0])
for i in range(H*W+1):
  for j in range(len(ans[i-1])):
    a,b=ans[i-1][j][0],ans[i-1][j][1]
    if a+1!=H:
      if [a+1,b] not in subete and L[a+1][b]==".":
        ans[i].append([a+1,b])
        subete.append([a+1,b])
    if a!=0:
      if [a-1,b] not in subete and L[a-1][b]==".":
        ans[i].append([a-1,b])
        subete.append([a-1,b])
    if b+1!=W:
      if [a,b+1] not in subete and L[a][b+1]==".":
        ans[i].append([a,b+1])
        subete.append([a,b+1])
    if b!=0:
      if [a,b-1] not in subete and L[a][b-1]==".":
        ans[i].append([a,b-1])
        subete.append([a,b-1])
  if [H-1,W-1] in subete:
    print(c-i-1)
    sys.exit()
print(-1)
### BUGGY CODE ###

k, s = map(int, input().split())
ans = 0
for i in range(k + 1):
    for j in range(i + 1):
        for l in range(j + 1):
            if i + j + l == s:
                if i == j == l:
                    ans += 1
                elif i == j or j == l or l == i:
                    ans += 3
                else:
                    ans += 6
print(ans)


### FIXED CODE ###

k, s = map(int, input().split())
ans = 0
for i in range(k + 1):
    for j in range(i + 1):
        l = s - (i + j)
        if 0 <= l <= k and l <= j <= i:
            if i == j == l:
                ans += 1
            elif i == j or j == l or l == i:
                ans += 3
            else:
                ans += 6
print(ans)
### BUGGY CODE ###

import sys
n = int(input())

print(0)
sys.stdout.flush()
s = input()

if s == "Vacant":
    exit()

low = 1
high = n-1
tmp = 0

while low+1 < high:
    mid = (low + high) //2
    
    print(mid)
    sys.stdout.flush()
    t = input()
    
    if mid % 2 == 0:
        if t[0] == s[0]:
            low = mid
        elif t[0] == "V":
            exit()
        else:
            high = mid
    else:
        if t[0] == s[0]:
            high = mid
        elif t[0] == "V":
            exit()
        else:
            low = mid
print(high)
sys.stdout.flush()
s = input()
exit()

### FIXED CODE ###

import sys
n = int(input())

print(0)
sys.stdout.flush()
s = input()

if s == "Vacant":
    exit()

low = 1
high = n-1
tmp = 0
cnt = 1

while low+1 < high:
    mid = (low + high) //2
    
    print(mid)
    sys.stdout.flush()
    t = input()
    cnt += 1
    
    if mid % 2 == 0:
        if t[0] == s[0]:
            low = mid
        elif t[0] == "V":
            exit()
        else:
            high = mid
    else:
        if t[0] == s[0]:
            high = mid
        elif t[0] == "V":
            exit()
        else:
            low = mid

print(high)
sys.stdout.flush()
s = input()
if s[0] == "V":
    exit()
else:
    print(low)
    sys.stdout.flush()
    s = input()
    exit()
### BUGGY CODE ###

R, G, B ,N = map(int, input().split())

cnt = 0
NR = N//R
NG = N//G
for r in range(NR + 1):
  for g in range(NG + 1):
    NrRgG = N - (r*R + g*G)
    if NrRgG < 0:
      break
    elif NrRgG >= 0:
      if NrRgG % B == 0:
        cnt += 1
print(cnt)

### FIXED CODE ###

R, G, B ,N = map(int, input().split())

if R==1 and G==1 and B==1:
  print(int((N+2)*(N+1)*(1/2)))
else:
  RGB = [R, G, B]
  RGB.sort(reverse=True)

  R = RGB[0]
  G = RGB[1]
  B = RGB[2]

  cnt = 0
  NR = N//R
  NG = N//G
  for r in range(NR + 1):
    for g in range(NG + 1):
      NrRgG = N - (r*R + g*G)
      if NrRgG < 0:
        break
      elif NrRgG >= 0:
        if NrRgG % B == 0:
          cnt += 1
  print(cnt)
### BUGGY CODE ###

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

M = 1
for i in range(N):
  M = M * A[i]
  
if M >10**18:
  print(-1)
else:
  print(M)

### FIXED CODE ###

import sys

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

M = 1
for i in range(N):
  M = M * A[i]
  if M >10**18:
    print(-1)
    sys.exit()
  
print(M)
### BUGGY CODE ###

r,g,b,n=map(int,input().split())
l=[r,g,b,n]
R=n//r
G=n//g
B=n//b
count=0
l=[r,g,b]
l.sort()
a=n//l[0]
b=n//l[1]
c=n//l[2]
for _a in range(a+1):
  for _b in range(b+1):
    for _c in range(c+1):
      if _a+_b+_c<=n:
        if l[0]*_a + l[1]*_b + l[2]*_c == n:
          count+=1
print(count)

### FIXED CODE ###

r,g,b,n=map(int,input().split())
l=[r,g,b,n]
count=0
for i in range(n+1):
  for j in range(n+1):
    if (n-(i*r+j*g))/b==int((n-(i*r+j*g))/b) and (n-(i*r+j*g))/b>=0:
      count+=1
print(count)
### BUGGY CODE ###

X = int(input())

X += 1
while True:
    std = X**0.5
    for i in range(1,int(std)):
        if X%i == 0:
            break
    X += 1

print(X)


### FIXED CODE ###

import math
n=int(input())

def prime(n):
    if n <= 1:
        return False
    
    for k in range(2, int(math.sqrt(n))+1):
        if n%k ==0:
            return False
    return True
    
while not(prime(n)):
    n += 1

    
print(n)
### BUGGY CODE ###

n, m = map(int, input().split())
a = [int(input()) for _ in range(m)]
MOD = 10**9+7
INF = MOD-1
dp = [INF]*(n+1)
if n == 1:
    if 1 in a:
        print(0)
    else:
        print(1)
    exit()

dp[0] = dp[1] = 1

if 0 in a:
    dp[0] = INF
if 1 in a:
    dp[1] = INF

for i in range(2, n+1):
    if i in a:
        dp[i] = INF
        continue
    if dp[i-1] == INF or dp[i-2] == INF:
        dp[i] = min(dp[i-1], dp[i-2])
    else:
        dp[i] = dp[i-1]+dp[i-2]
    dp[i] %= MOD


print(dp[n] if dp[n] != INF else 0)


### FIXED CODE ###

n, m = map(int, input().split())
a = [int(input()) for _ in range(m)]
MOD = 10**9+7
INF = MOD-1
dp = [INF]*(n+1)
if n == 1:
    if 1 in a:
        print(0)
    else:
        print(1)
    exit()

dp[0] = dp[1] = 1

if 0 in a:
    dp[0] = INF
if 1 in a:
    dp[1] = INF

for x in a:
    dp[x] = 0

for i in range(2, n+1):
    if dp[i] == 0:
        continue

    if dp[i-1] == INF and dp[i-2] == INF:
        break
    elif dp[i-1] == INF or dp[i-2] == INF:
        dp[i] = max(dp[i-1], dp[i-2])
    else:
        dp[i] = dp[i-1]+dp[i-2]
    dp[i] %= MOD


print(dp[n] if dp[n] != INF else 0)
### BUGGY CODE ###

MAX_A = 10**6 + 1
MAX_P = MAX_A // 2
is_prim = [i%2==1 for i in range(MAX_P)]
is_prim[1] = False; is_prim[2] = True
for i in range(3, MAX_P):
    if not is_prim[i]: continue
    for j in range(i+i, MAX_P, i): is_prim[j] = False

def solve():
    c = 0
    C = [0] * MAX_A
    for a in A:
        for p in range(MAX_P):
            if not is_prim[p]: continue
            if a%p: continue
            if a < p*p: break
            C[p] += 1
            c = max(c, C[p])
    if c <= 1: return "pairwise"
    elif c <= n-1: return "setwise"
    return "not"

n = int(input())
A = [*map(int, input().split())]
print(solve(), 'coprime')


### FIXED CODE ###

n = int(input())
A = [*map(int, input().split())]
def solve():
    MAX_A = 10**6 + 1
    C = [0] * MAX_A
    for a in A: C[a] += 1
    pairwise = True
    for i in range(2, MAX_A):
        if sum(C[i:MAX_A:i]) > 1: pairwise = False
    if pairwise: return 'pairwise'
    from math import gcd
    g = 0
    for a in A: g = gcd(g, a)
    if g == 1: return 'setwise'
    return 'not'
print(solve(), 'coprime')
### BUGGY CODE ###

class Union:
  def __init__(s, num):
    s.T = [-1 for i in range(num)]
 
  def root(s, x):
    if s.T[x] < 0: return x, -s.T[x]
    t, k = s.root(s.T[x])
    s.T[x] = t
    return t, k
 
  def merge(s, x, y):
    an, am = s.root(x)
    bn, bm = s.root(y)
    if an == bn: return False
    if am < bm: an, bn  = bn, an
    s.T[an] += s.T[bn]
    s.T[bn] = an
    return True
 
  def size(s, x):
    return s.root(x)[1]

  def same(s, x, y):
    return s.root(x)[0] == s.root(y)[0]

import heapq
pop = heapq.heappop
push = heapq.heappush
q  = []

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

uni = Union(N)

xyn = [[0] * 3 for _ in range(N)]
for i in range(N):
  x, y = xy[i]
  xyn[i] = [x, y, i]

xyn.sort()

push(q, [xyn[0][1], xyn[0][2]])
for i in range(1, N):
  x, y, n = xyn[i]
  m = pop(q)
  yy, nn = m
  if yy < y:
    uni.merge(nn, n)
    while q:
      yy, nn = pop(q)
      if yy < y:
        uni.merge(nn, n)
      else:
        push(q, [yy, nn])
        break
  else:
    push(q, [y, n])
  push(q, m)

for i in range(N):
  print(uni.root(i)[1])


### FIXED CODE ###

class Union:
  def __init__(s, num):
    s.T = [-1 for i in range(num)]
 
  def root(s, x):
    if s.T[x] < 0: return x, -s.T[x]
    t, k = s.root(s.T[x])
    s.T[x] = t
    return t, k
 
  def merge(s, x, y):
    an, am = s.root(x)
    bn, bm = s.root(y)
    if an == bn: return False
    if am < bm: an, bn  = bn, an
    s.T[an] += s.T[bn]
    s.T[bn] = an
    return True
 
  def size(s, x):
    return s.root(x)[1]

  def same(s, x, y):
    return s.root(x)[0] == s.root(y)[0]

import heapq
pop = heapq.heappop
push = heapq.heappush
q  = []

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

uni = Union(N)

xyn = [[0] * 3 for _ in range(N)]
for i in range(N):
  x, y = xy[i]
  xyn[i] = [x, y, i]

xyn.sort()
x, y, n = xyn[0]
push(q, (y << 20) + n)
for i in range(1, N):
  x, y, n = xyn[i]
  m = pop(q)
  yy, nn = m >> 20, m % (1 << 20)
  if yy < y:
    uni.merge(nn, n)
    while q:
      p = pop(q)
      yy, nn = p >> 20, p % (1 << 20)
      if yy < y:
        uni.merge(nn, n)
      else:
        push(q, (yy << 20) + nn)
        break
  else:
    push(q, (y << 20) + n)
  push(q, m)

for i in range(N):
  print(uni.root(i)[1])
### BUGGY CODE ###

if __name__ == "__main__":
    N = int(input())
    S = input()

    dp = [[0] * 5005 for i in range(5005)]

    for i in range(N, 0, -1):
        for j in range(N, 0, -1):
            if S[i-1] != S[j-1]:
                dp[i][j] = 0
            else:
                dp[i][j] = dp[i+1][j+1] + 1

    result = 0
    for i in range(N):
        for j in range(N):
            if i >= j:
                continue
            now = min(dp[i][j], j-i)
            result = max([now, result])

    print(result)


### FIXED CODE ###

if __name__ == "__main__":
    N = int(input())
    S = input()

    dp = [[0] * 5005 for i in range(5005)]

    for i in range(N, 0, -1):
        for j in range(N, 0, -1):
            if S[i-1] != S[j-1]:
                dp[i][j] = 0
            else:
                dp[i][j] = dp[i+1][j+1] + 1

    result = 0
    for i in range(N):
        for j in range(N):
            if i >= j:
                continue
            now = min(dp[i][j], j-i)
            result = max([now, result])

    print(result)
### BUGGY CODE ###

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

ans = 0
i = 0
j = 1
c = 0
while j < N:
    c = 0
    for k in range(j, N):
        cnt = 0
        while k+cnt < N and i+cnt < j and S[i+cnt] == S[k+cnt]:
            cnt += 1
        c = max(c, cnt)
    if j-i > c:
        i += 1
        j = i+c
    else:
        j += 1
    ans = max(c, ans)
    
print(ans)

### FIXED CODE ###

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

def z_algo(S):
    N = len(S)
    Z = [0]*N
    i = 1
    j = 0
    Z[0] = N
    while i < N:
        while i+j < N and S[j] == S[i+j]:
            j += 1
        if j == 0:
            i += 1
            continue
        Z[i] = j
        k = 1
        while i+k < N and k < j-Z[k]:
            Z[i+k] = Z[k]
            k += 1
        i += k
        j -= k
    return Z

ans = 0
l = 0
while l < N:
    temp = S[l:]
    z = z_algo(temp)
    for i in range(1, len(temp)):
        ans = max(ans, min(i, z[i]))
    l += 1
    
print(ans)
### BUGGY CODE ###

n=int(input())
s=input()
li=[]

for i in range(n):
    cnt=0
    for j in range(n):
        if j>i and s[j]=="E":
            cnt+=1
        if j<i and s[j]=="W":
            cnt+=1
    li.append(cnt)
print(min(li))

### FIXED CODE ###

n=int(input())
s=input()
li=[]
w,e=0,0
wli,eli=[],[]
ans=[]

for i in range(n):
    if s[i]=="W":
        w+=1
    wli.append(w)
for i in reversed(range(n)):
    if s[i]=="E":
        e+=1
    eli.append(e)
for i in range(n):
    if i!=0 and i!=n-1:
        ans.append(wli[i-1]+eli[n-i-2])
    elif i==0:
        ans.append(eli[n-2])
    elif i==n-1:
        ans.append(wli[n-2])

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

N, K = map(int, input().split())
lis = list(map(int, input().split()))
p = 10**9+7
fac_lis = [[0] for i in range(N)]
fac_lis[0] = 1
max_ans = 0
min_ans = 0

for i in range(1,N):
  fac_lis[i] = fac_lis[i-1]*(i+1)

def combi(n,k):
  if n == k:
    return 1
  else:
  	return fac_lis[n-1]*pow(fac_lis[k-1], p-2, p)*pow(fac_lis[n-k-1], p-2, p) % p

lis.sort()
for i in range(K-1,N):
  max_ans += lis[i]*combi(i, K-1)
  max_ans %= p
  
for i in range(N-K+1):
  min_ans += lis[i]*combi(N-(i+1), K-1)
  min_ans %= p

ans = (max_ans - min_ans) % p
print(ans)

### FIXED CODE ###

# フェルマーの小定理
N, K = map(int, input().split())
A = list(map(int, input().split()))
 
m = 1000000007
 
fac = [0] * (N + 1)
fac[0] = 1
for i in range(N):
    fac[i + 1] = fac[i] * (i + 1) % m
 
 
def mcomb(n, k):
    if n == 0 and k == 0:
        return 1
    if n < k or k < 0:
        return 0
    return fac[n] * pow(fac[n - k], m - 2, m) * pow(fac[k], m - 2, m) % m
 
 
A.sort(reverse=True)
maxX = 0
for i in range(N - K + 1):
    maxX += A[i] * mcomb(N - (i + 1), K - 1)
    maxX %= m

A.sort()
minX = 0
for i in range(N - K + 1):
    minX += A[i] * mcomb(N - (i + 1), K - 1)
    minX %= m

print((maxX - minX) % m)
### BUGGY CODE ###

n=int(input())
a = list(map(int, input("").split()))
b = list(map(int, input("").split()))
c = list(map(int, input("").split()))
out=0
for i in a:
    for j in b:
        for k in c:
            if k > j and j > i:
                out+=1
print(out)

### FIXED CODE ###

import bisect
n=int(input())
a = list(map(int, input("").split()))
b = list(map(int, input("").split()))
c = list(map(int, input("").split()))
out=0
a.sort()
b.sort()
c.sort()
for i in b:
    na = bisect.bisect_left(a,i)
    nc = bisect.bisect(c,i)
    out += na * (len(c)-nc)
print(out)
### BUGGY CODE ###

import sys
x=input()
tmp=x.split("ST")
tmp=''.join(tmp)
a=len(tmp)
for i in range(2000000):
    tmp=tmp.split("ST")
    tmp=''.join(tmp)
    if len(tmp)==a:
        print(len(tmp))
        break
    elif len(tmp)==0:
        print(0)
        break
    else:
        a=len(tmp)


### FIXED CODE ###

if __name__ == '__main__':
    x = list(input())
    sl = []
    ans = 0
    for i in x:
        if i == "S":
            sl.append(1)
        else:
            if len(sl) != 0:
                ans += sl.pop()

    print(len(x) - ans * 2)
### BUGGY CODE ###

n = int(input())
ls = [int(input()) for _ in range(n)]

pp = [max(ls[i:])-x for i, x in enumerate(ls, 1) if i != len(ls)]

print(max(pp))


### FIXED CODE ###

n = int(input())
m = [int(input()) for _ in range(n)]

def fx(raw):
    min_n = raw[0]
    max_n = raw[1] - raw[0]
    for i in raw[1:]:
        if i - min_n >= max_n:
            max_n = i - min_n
        if i < min_n:
            min_n = i
    return max_n


if __name__ == '__main__':
    print(fx(m))