Harryxun/stf_run huggingface dataset:
import heapq

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

queries = []
for i in range(m):
    q = list(map(int, input().split()))
    queries.append(q)
queries.sort(key=lambda x: x[1])
queries.reverse()

ans = 0
pos = 0
for q in queries:
    b, c = q
    if cards[pos + b - 1] < c:
        # print('a')
        pos = pos + b
        ans += c * b
    else:
        for i in range(b):
            if cards[pos + i] < c:
                # print('b')
                ans += c
            else:
                # print('c')
                pos += i
                for j in range(pos, n):
                    ans += cards[j]

                pos = n
                break
        break

if pos < n:
    for j in range(pos, n):
        ans += cards[j]

print(ans)



### FIXED CODE ###

import heapq

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

queries = []
for i in range(m):
    q = list(map(int, input().split()))
    queries.append(q)
queries.sort(key=lambda x: x[1])
queries.reverse()

ans = 0
pos = 0
for q in queries:
    b, c = q
    if cards[min(pos+b-1, n-1)] < c:
        # print('a')
        pos = pos + b
        ans += c * (b - max(0, pos-n))
        if pos >= n:
            break
    else:
        for i in range(b):
            if cards[pos+i] < c:
                # print('b')
                ans += c
            else:
                # print('c')
                pos += i
                for j in range(pos, n):
                    ans += cards[j]

                pos = n
                break
        break

if pos < n:
    for j in range(pos, n):
        ans += cards[j]

print(ans)
n, k = map(int,input().split())
a_list = list(map(int,input().split()))
a_list.sort()

from operator import mul
from functools import reduce

def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under

sum_val = 0
val = cmb(n-1, k-1)
for i in range(n-k+1):
    if i != 0:
        val = val*(n-i-k+1)/(n-i)
    sum_val = (sum_val + ((a_list[-(i+1)]+(10**9+7))*val) - ((a_list[i]+(10**9+7))*val))%(10**9+7)


print(int(sum_val))

### FIXED CODE ###

n, k = map(int, input().split())
a_list = list(map(int, input().split()))
a_list.sort()


mod = 10 ** 9 + 7
f_list = [1]
for i in range(1,n+1):
    f_list.append((f_list[-1] * i) % mod)
def comb(n,r):
    return f_list[n] * (pow(f_list[r], mod-2, mod) * pow(f_list[n-r], mod-2, mod) % mod) % mod


max_val = 0
min_val = 0
for i in range(n - k + 1):
    val = comb(n - i - 1, k - 1)
    max_val = (max_val + (((a_list[-(i + 1)]) * val))) % (10 ** 9 + 7)
    min_val = (min_val + ((a_list[i]) * val)) % (10 ** 9 + 7)

print(int((max_val - min_val) % (10 ** 9 + 7)))
N = int(input())
A = [0]
A.extend(list(map(int, input().split())))

buka_num = []

for i in range(1,N):
    #tmp_A = A[i:]
    buka_num.append(tmp_A.count(i))
    
buka_num.append(0)
for ele in buka_num:
    print(ele)

### FIXED CODE ###

import math
R = int(input())
print(R*2*math.pi)
n-v_odd_common[0][1]-v_even_common[1][1]

### FIXED CODE ###

from collections import Counter
 
n = int(input())
v_array = list(map(int,input().split()))
 
v_odd = v_array[0::2]
v_even = v_array[1::2]
 
v_odd_common = Counter(v_odd).most_common()
v_even_common = Counter(v_even).most_common()

v_odd_common.append((0,0))
v_even_common.append((0,0))

if v_odd_common[0] != v_even_common[0]:
    print(n-v_odd_common[0][1]-v_even_common[0][1])
else:
    print(min(n-v_odd_common[0][1]-v_even_common[1][1],n-v_odd_common[1][1]-v_even_common[0][1]))
a,b=map(int,input().split())
if(a*b%2==0){
  print("Even")
}
elif(a*b%2!=0){
  print("Odd") 
}


### FIXED CODE ###

a,b=map(int, input().split())
c=a*b%2
if c==0:
  print("Even")

else :
  print("Odd")
import math
def func(x,y,z):
    ans = x**2 + y**2 + z**2+ x*y + y*z + z*x
    return ans

N = int(input())
array_N = [0]*N
root_n = round(math.sqrt(n+1))

for x in range(1,root_n):
    for y in range(1,root_n):
        for z in range(1,root_n):
            if func(x,y,z) <= N:
                array_N[func(x,y,z)-1] =array_N[func(x,y,z)-1] +1
                
for i in range(N):
    print(array_N[i])
                
                

### FIXED CODE ###


import math
def func(x,y,z):
    ans = x**2 + y**2 + z**2+ x*y + y*z + z*x
    return ans

N = int(input())
array_N = [0]*N
root_n = round(math.sqrt(N+1))

for x in range(1,root_n):
    for y in range(1,root_n):
        for z in range(1,root_n):
            if func(x,y,z) <= N:
                array_N[func(x,y,z)-1] = array_N[func(x,y,z)-1] +1
                
for i in range(N):
    print(array_N[i])
N,K = map(int,input().split())
A = list(map(int,input().split()))
A = sorted(A)
mi = 0
zero = 0
for a in A:
  if a<0:
    mi+=1
  elif a==0:
    zero+=1
  else:
    break

plu = N-mi-zero
A_mi = A[0:mi:]
A_mi_rev = A_mi[::-1]
A_plu = A[mi+zero::]
A_plu_rev = A_plu[::-1]
num_mi = plu*mi
num_zero = (plu+mi)*zero+(zero*(zero-1))//2
r = max(A[-1]**2+10,A[0]**2+10)
l = A[0]*A[-1]-10
while l+1!=r:
  m = (l+r)//2
  num = 0
  if m>0:
    num+=num_mi+num_zero
    if num>=K:
      r=m
      continue
    cou=0
    for i in range(0,plu):
      while True:
        if cou>=plu-i-1:
          num+=plu-i-1
          break
        x = A_plu_rev[i]*A_plu[cou]
        if x<m:
          cou+=1
        else:
          num+=cou
          break
          
      if num>=K:
        break
    if num>=K:
      r=m
      continue
    cou = 0
    for i in range(0,mi):
      while True:
        if cou>=mi-i-1:
          num+=mi-i-1
          break
        x = A_mi[i]*A_mi_rev[cou]
        if x<m:
          cou+=1
        else:
          num+=cou
          break
          
      if num>=K:
        break

    if num>=K:
      r=m
    else:
      l=m
    
  elif m==0:
    num+=num_mi
    if num>=K:
      r=m
    else:
      l=m
  else:
    cou = 0
    for a in A_mi_rev:
      while True:
        if cou==plu:
          num+=cou
          break
        x = a*A_plu_rev[cou]
        if x<m:
          cou+=1
        else:
          num+=cou
          break
          
      if num>=K:
        break
    if num>=K:
      r = m
    else:
      l = m
      
print(l)

### FIXED CODE ###

S = input()[::-1]
l = len(S)
dp = [[0]*2 for _ in range(l+1)]
for i in range(l):
  dp[i+1][0]=min(dp[i][0]+int(S[i]),dp[i][1]+int(S[i])+1)
  if i!=0:
    dp[i+1][1]=min(dp[i][0]+10-int(S[i]),dp[i][1]+10-(int(S[i])+1))
  else:
    dp[i+1][1]=dp[i][0]+10-int(S[i])
print(min(dp[-1][0],dp[-1][1]+1))
import sys
 
N, M = map(int,input().split())
 
ls = []
 
L, R = map(int,input().split())
l = [k+L for k in range(R-L+1)]
 
if M == 1:
    print(len(l))
else:
    cs = []
    for i in range(M-1):
        L, R = map(int,input().split())
        if L in l:
            c = l[-1] - L + 1
            if c <= 0:
                print(0)
                sys.exit()
            cs.append(c)
 
    print(min(cs))

### FIXED CODE ###

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

Ls, Rs = [0 for _ in range(M)],  [0 for _ in range(M)]

for i in range(M):
    L, R = map(int,input().split())
    Ls[i] = L
    Rs[i] = R
    
L_prime = max(Ls)
R_peime = min(Rs)

if L_prime > R_peime:
    print(0)
else:
    print(R_peime - L_prime + 1)
while True:
    x,y = map(int, input().split())
    if x == 0 and y == 0:
        break
    if x => y:
        print (y,x)
    else:
        print (x,y)

### FIXED CODE ###

while True:
    x,y = map(int, input().split())
    if x == 0 and y == 0 :
        break
    elif x <= y :
        print (x,y)
    else :
        print (y,x)
[a, b, c] = map(int, input().split())
if(a==0 | b==0):
    Left = a+b
    Right = c
else:
    Left = 4*a*b
    Right = (c-a-b)*(c-a-b)
if(Left < Right):
    print('Yes')
else:
    print('No')

### FIXED CODE ###

L = [1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]
K = int(input())
print(L[K-1])
n=input()
for i in range(len(n)):
  if n[i]==n[i+1]:
    print('Bad')
    exit()
  else:
    print('Good')
  

### FIXED CODE ###

a,b,c,d=input();print(' GBoaodd'[a!=b!=c!=d::2])
import math
n,m = map(int, input().split())
if abs(n-m) <= 1:
    a = max(n,m)
    b = min(n,m)
    if a-b == 1:
        print((math.factorial(a)*math.factorial(b))%(10**9+7))
    else:
        print((math.factorial(a)*math.factorial(b)*2%(10**9+7))
else:
    print(0)


### FIXED CODE ###

import math
n,m = map(int, input().split())
if abs(n-m) <= 1:
    a = max(n,m)
    b = min(n,m)
    if a-b == 1:
        print((math.factorial(a)*math.factorial(b))%(10**9+7))
    else:
        print((math.factorial(a)*math.factorial(b)*2)%(10**9+7))
else:
    print(0)
nums = input().split()
a = int(nums[0])
b = int(nums[1])
c = int(nums[2])
if a < b < c:
     print("Yse")
elif:
     print("No")

### FIXED CODE ###

nums = input().split()
a = int(nums[0])
b = int(nums[1])
c = int(nums[2])
if a < b < c:
     print('Yes')
else:
     print('No')
from decimal import Decimal

def main():
    x,y = map(Decimalt,input().split())
    print(int(x*y))

if __name__ == '__main__':
    main()


### FIXED CODE ###

from decimal import Decimal


def main():
    A, B = map(Decimal, input().split())

    print(int(A*B))


if __name__ == "__main__":
    main()
x=int(input())
ans=0
if 30=<x:
    ans='Yes'
else:
    ans='No'
print(ans)

### FIXED CODE ###

x=int(input())
ans=0
if 30<=x:
    ans='Yes'
else:
    ans='No'
print(ans)
import sys
n = int(input())
a = list(map(int, input().split()))
x1, x2 = [], []
y1, y2 = [], []
for i in range(n//2):
  if not a[2*i] in x1:
    x1.append(a[2*i])
    y1.append(1)
  else:
    y1[x1.index(a[2*i])] += 1

for i in range(n//2):
  if not a[2*i+1] in x2:
    x2.append(a[2*i+1])
    y2.append(1)
  else:
    y2[x2.index(a[2*i+1])] += 1

if len(x1)==1 and len(x2)==1 and x1[0]!=x2[0]:
  print(0)
  sys.exit()

total = 0
if x1[y1.index(max(y1))]!=x2[y2.index(max(y2))]:
  total = sum(y1)-max(y1) + sum(y2) - max(y2)
elif len(x1)==1:
  y3 = y2.remove(x2.index(x1[0]))
  total = sum(y1)-max(y1) + sum(y2) - max(y3)
elif len(x2)==1:
  y3 = y1.remove(x1.index(x2[0]))
  total = sum(y1)-max(y3) + sum(y2) - max(y2)
else:
  y3 = y1.remove(max(y1))
  y4 = y2.remove(max(y2))
  if max(y3) >= max(y4):
    total = sum(y1) - max(y3) + sum(y2) - max(y2)
  else:
    total = sum(y1) - max(y1) + sum(y2) - max(y4)
print(total)

### FIXED CODE ###

from collections import Counter
 
def f(n,v):
	a=Counter(v[0::2]).most_common()
	b=Counter(v[1::2]).most_common()
	
	a.append([0,0])
	b.append([0,0])
	if a[0][0]!=b[0][0]:
		return n-(a[0][1]+b[0][1])
	else:
		return min(n-(a[1][1]+b[0][1]),n-(a[0][1]+b[1][1]))
 
if __name__=="__main__":
	x=int(input())
	data=[int(i) for i in input().split()]
	print(f(x,data))
def main():
    import numpy as np
    h,w,k = map(int,input().split())
    l = [list(input()) for i in range(h)]

    def check(lis):
        lis.append(h)
        num = [0]*(len(lis))
        ans = 0
        for i in range(w):
            ch = 0
            num2 = [0]*(len(lis))
            for j in range(h):
                
                if l[j][i] == "1":
                    if j <= lis[ch]:
                        num2[ch] += 1
                    else:
                        ch += 1
                        num2[ch] += 1
            if max(num2) > k:
                return float("INF")
            else:
                for i in range(len(num)):
                    num[i] += num2[i]
                    if num[i] > k:
                        ans += 1
                        num = num2
                        break 
            
            
        return ans

    ans = 10**9

    for i in range(2**(h-1)):
        count = 0
        lis1 = []
        for j in range(h-1):
            if (i >> j) & 1:
                lis1.append(j)
                count += 1
        
        ans = min(ans,count+check(lis1))
        
    print(ans)
if __name__ == "__main__":
    main()

### FIXED CODE ###

n,m = map(int,input().split())
print(n*(n-1)//2+m*(m-1)//2)
import math


def lcm(x, y):
    return (x * y) // math.gcd(x, y)


ab = input()
a = int(ab.split(" ")[0])
b = int(ab.split(" ")[1])

print(lcm(a, b))


### FIXED CODE ###

import fractions


def lcm(x, y):
    return (x * y) // fractions.gcd(x, y)


ab = input()
a = int(ab.split(" ")[0])
b = int(ab.split(" ")[1])

print(lcm(a, b))
#!/usr/bin/env python3
import sys
import math
import numpy as np
from functools import lru_cache

args = sys.argv
if len(args) == 2:
  import IPython

def embed():
  if len(args) == 2:
    sys.stdin = open('/dev/tty')
    IPython.embed()

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

#### functions
def discount(price_list, num_coupon):
  if num_coupon == 0:
    return price_list
  else:
    if len(price_list) == 1:
      price_list[0] = math.floor(price_list[0]  / 2** num_coupon)
      return price_list
    else:
      sorted_list = sorted(price_list)
      max1st = sorted_list[-1]
      max2nd = sorted_list[-2]
      num_div = min(num_coupon, math.floor(math.log2(max1st / max2nd)) + 1)
      max_i = np.argmax(price_list)
      price_list[max_i] = math.floor(price_list[max_i] / 2**num_div)
      price_list = discount(price_list, num_coupon - num_div)
      return price_list

print(sum(discount(A, M)))


### FIXED CODE ###

#!/usr/bin/env python3
import sys
import math
import numpy as np
import heapq
from functools import lru_cache

args = sys.argv
if len(args) == 2:
  from IPython import embed
  em = True
else:
  em = False

#### input
N, M = map(int, input().split())
A = list(map(lambda x:int(x)*(-1), input().split()))

# sys.stdin = open('/dev/tty')

heapq.heapify(A)

#### functions
def discount(num_coupon):
  max = -heapq.heappop(A) / 2
  heapq.heappush(A, -max)

#### execution
# if em: embed()
for i in range(0, M):
  max = math.floor(-heapq.heappop(A) / 2)
  heapq.heappush(A, -max)

print(-sum(A))
S, T = map(input().split())
print(S+T)


### FIXED CODE ###

X, Y = input().split()
print(Y+X)
N=int(input())
A=list(map(int,input().split()))
S=sum(A)
##print(S)
tmp=0
T=0
for i in range(N):
  T=T+[i+1]
  ##print(T)
  ##print(A[i])
  tmp=(A[i]*(S-T)+tmp)
tmp=tmp%(10**9+7)
print(tmp)

### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
S=sum(A)
##print(S)
tmp=0
T=0
for i in range(N-1):
  T=T+A[i]
  ##print(T)
  ##print(A[i])
  tmp=(A[i]*(S-T)+tmp)
tmp=tmp%(10**9+7)
print(tmp)
N,M = map(int,input().split())
A = [int(input()) for i in range(M)]

def recur(step):
  if step == N:
    return 1
  
  elif step in A or step > N:
    return 0
  
  else:
    ret1 = recur(step + 1) 
    ret2 = recur(step + 2) 
    return (ret1 + ret2) % (10 ** 9 + 7) 
    
print(recur(0))
    

### FIXED CODE ###

N,M = map(int, input().split())
A = [int(input()) for a in range(M)]
A = set(A)
	
DP = [0] * (N + 1)	
DP[0] = 1

mod = (10 ** 9) + 7

for i in range(1,N+1):
	if i in A:
		DP[i] = 0
	else:
		DP[i] = DP[i-1] + DP[i-2]

print(DP[N] % (mod))
N,K = map(int,input().split())
if K == 1:
    ans = 0
else:
    if N >= K:
        N -= (N//K)*K
        ans = min(N,abs(N-K))
    else:
        min(N,abs(N-K))
print(ans)


### FIXED CODE ###

N,K = map(int,input().split())
if K == 1:
    ans = 0
else:
    if N >= K:
        N -= (N//K)*K
        ans = min(N,abs(N-K))
    else:
        ans = min(N,abs(N-K))
print(ans)
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush
from bisect import bisect_left,bisect_right 
import sys,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

h,w,m = inpl()
yd = []
for i in range(h):
    yd.append([i,0])
xd = []
for i in range(w):
    xd.append([i,0])
s = [False] * w*h
def ind(i,j):
    return i*w + j
for _ in range(m):
    a,b = inpl()
    yd[a-1][1] += 1
    xd[b-1][1] += 1
    s[ind(a-1,b-1)] = True
yd.sort(key = lambda x:x[1], reverse = True)
xd.sort(key = lambda x:x[1], reverse = True)
ymax = yd[0][1]
yl = []
for i,x in yd:
    if x != ymax: break
    yl.append(i)
xmax = xd[0][1]
xl = []
for i,x in xd:
    if x != xmax: break
    xl.append(i)
res = ymax + xmax - 1
# print(yl,xl,res)
for i in yl:
    for j in xl:
        if not s[ind(i,j)]:
            res += 1
            print(res)
            quit()
print(res)

### FIXED CODE ###

from collections import Counter,defaultdict,deque
from heapq import heappop,heappush
from bisect import bisect_left,bisect_right 
import sys,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

h,w,m = inpl()
yd = []
for i in range(h):
    yd.append([i,0])
xd = []
for i in range(w):
    xd.append([i,0])
se = set()
def ind(i,j):
    return i*w + j
for _ in range(m):
    a,b = inpl()
    yd[a-1][1] += 1
    xd[b-1][1] += 1
    se.add((a-1,b-1))
yd.sort(key = lambda x:x[1], reverse = True)
xd.sort(key = lambda x:x[1], reverse = True)
ymax = yd[0][1]
yl = []
for i,x in yd:
    if x != ymax: break
    yl.append(i)
xmax = xd[0][1]
xl = []
for i,x in xd:
    if x != xmax: break
    xl.append(i)
res = ymax + xmax - 1
# print(yl,xl,res)
for i in yl:
    for j in xl:
        if not (i,j) in se:
            res += 1
            print(res)
            quit()
print(res)
num = int(input())
col = input()
r = clo.count("R")
b = num - r
if r > b :
    ans = "Yes"
else :
    ans = "No"
print (ans)

### FIXED CODE ###

num = int(input())
col = input()
r = col.count("R")
b = num - r
if r > b :
    ans = "Yes"
else :
    ans = "No"
print (ans)
r=input()
print(r*r*3)

### FIXED CODE ###

r = int(input())

print(3*r*r)
from collections import deque
n=int(input())
g=[[] for i in range(n)]
for i in range(n):
    p=list(str(input()))
    for j in range(n):
        if p[j]=='1':
            g[i].append(j)
q=deque([0])
v=[-1]*n
v[0]=0
while q:
    p=q.popleft()
    for i in g[p]:
        if v[i]==-1:
            v[i]=1-v[p]
            q.append(i)
        else:
            if v[i]!=1-v[p]:
                print(-1)
                exit()
ana=0
for s in range(n):
    q=deque([s])
    v=[0]*n
    v[s]=1
    while q:
        p=q.popleft()
        for i in g[p]:
            if v[i]==0:
                v[i]=1+v[p]
                q.append(i)
    ans=max(ans,max(v))
print(ans)


### FIXED CODE ###

from collections import deque
n=int(input())
g=[[] for i in range(n)]
for i in range(n):
    p=list(str(input()))
    for j in range(n):
        if p[j]=='1':
            g[i].append(j)
q=deque([0])
v=[-1]*n
v[0]=0
while q:
    p=q.popleft()
    for i in g[p]:
        if v[i]==-1:
            v[i]=1-v[p]
            q.append(i)
        else:
            if v[i]!=1-v[p]:
                print(-1)
                exit()
ans=0
for s in range(n):
    q=deque([s])
    v=[0]*n
    v[s]=1
    while q:
        p=q.popleft()
        for i in g[p]:
            if v[i]==0:
                v[i]=1+v[p]
                q.append(i)
    ans=max(ans,max(v))
print(ans)
X = int(input())
if X == 3,5,7:
  print('YES')
else:
  print('NO')

### FIXED CODE ###

X = int(input())
if X == 3 or X == 5 or X ==7:
  print('YES')
else:
  print('NO')
INFTY = 10**10
N,W = map(int,input().split())
X = [list(map(int,input().split())) for _ in range(N)]
dp = [[[-INFTY for _ in range(3*N+1)] for _ in range(N+1)] for _ in range(N+1)]
for i in range(N+1):
    dp[i][0][0] = 0
for i in range(1,N+1):
    for j in range(1,i+1):
        for k in range(3*N+1):
            dp[i][j][k] = dp[i-1][j][k]
            if k>=X[i-1][0]-X[0][0]:
                dp[i][j][k] = max(dp[i][j][k],dp[i-1][j-1][k-X[i-1][0]+X[0][0]]+X[i-1][1])
cmax = 0
for j in range(1,N+1):
    if W-j*X[0][0]>=0:
        for k in range(W-j*X[0][0]+1):
            cmax = max(cmax,dp[N][j][k])
print(cmax)

### FIXED CODE ###

INFTY = 10**10
N,W = map(int,input().split())
X = [list(map(int,input().split())) for _ in range(N)]
dp = [[[-INFTY for _ in range(3*(N-1)+1)] for _ in range(N+1)] for _ in range(N+1)]
for i in range(N+1):
    dp[i][0][0] = 0
for i in range(1,N+1):
    for j in range(1,i+1):
        for k in range(3*(N-1)+1):
            dp[i][j][k] = dp[i-1][j][k]
            if k>=X[i-1][0]-X[0][0]:
                dp[i][j][k] = max(dp[i][j][k],dp[i-1][j-1][k-X[i-1][0]+X[0][0]]+X[i-1][1])
cmax = 0
for j in range(1,N+1):
    for k in range(3*(N-1)+1):
        if j*X[0][0]+k<=W:
            cmax = max(cmax,dp[N][j][k])
print(cmax)
n, m = map(int, input().split())

lrds = [tuple(map(int, input().split())) for _ in range(m)]

xs = [None for _ in range(n)]

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

for lrd in lrds:
    l, r, d = lrd
    ps[l-1].append((l-1, r-1, d))
    ps[r-1].append((l-1, r-1, d))

not_decided = set(range(n))

def f(t):
    for lrd in ps[t]:
        l, r, d = lrd
        if l == t:
            another = r
            position = d
        else:
            another = l
            position = -d
        if xs[another] is None:
            xs[another] = xs[t] + position
            not_decided.remove(another)
            f(another)
        else:
            if xs[another] != xs[t] + position:
                return False
    return True

def solve():
    while len(not_decided) != 0:
        t = not_decided.pop()
        xs[t] = 0

        if not f(t):
            return False
    return True

if solve():
    print("Yes")
else:
    print("No")


### FIXED CODE ###

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

lrds = [tuple(map(int, input().split())) for _ in range(m)]

xs = [None for _ in range(n)]

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

for lrd in lrds:
    l, r, d = lrd
    ps[l-1].append((r-1, d))
    ps[r-1].append((l-1, -d))

not_decided = set(range(n))

def solve():
    while len(not_decided) != 0:
        t = not_decided.pop()
        xs[t] = 0

        stack = [t]
        while len(stack) != 0:
            c = stack.pop()
            for p in ps[c]:
                another, relative_position = p
                if another in not_decided:
                    xs[another] = xs[c] + relative_position
                    not_decided.remove(another)
                    stack.append(another)
                else:
                    if xs[another] != xs[c] + relative_position:
                        return False
    return True

if solve():
    print("Yes")
else:
    print("No")
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**4
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 )

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

a.sort()
ans1 = 0
ans2 = 0
for h in range(m-k+1):

    n = (m-h-1)
    r = (k-1)
    cmb1 = cmb(n, r, mod)
    ans1 += (a[m - h - 1]) * cmb1 % mod
    ans2 += (a[h]) * cmb1 % mod

ans = (ans1 - ans2) % mod

print(ans)

### FIXED CODE ###


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**5
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 )

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

a.sort()
ans1 = 0
ans2 = 0
for h in range(m-k+1):

    n = (m-h-1)
    r = (k-1)
    cmb1 = cmb(n, r, mod)
    ans1 += (a[m - h - 1]) * cmb1 % mod
    ans2 += (a[h]) * cmb1 % mod

ans = (ans1 - ans2) % mod

print(ans)