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

import math
from functools import reduce

def gcd(nums):
    return reduce(math.gcd, nums)

K = int(input())

a = []
for i in range(1, K+1):
    for j in range(1, K+1):
        for k in range(1, K+1):
            a.append([i,j,k])

ans = 0
for i in a:
    ans += gcd(i)

print(ans)

### FIXED CODE ###

import math
from functools import reduce
 
def gcd(nums):
    return reduce(math.gcd, nums)
 
K = int(input())
 
ans = 0
for i in range(1, K+1):
    for j in range(1, K+1):
        for k in range(1, K+1):
            ans += gcd([i, j, k])
 
print(ans)
### BUGGY CODE ###

N = int(input())

a = [int(N) for N in input().split()]
b = len(a)

count = 0

for i in range(1,N+1):
    for k in range(0,b):
        if(i == a[k]):
            count += 1
    print(count)
    count = 0

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
 
ans = [0]*n
for i in range(n-1):
    ans[a[i]-1] += 1
for j in range(n):
    print(ans[j])
### BUGGY CODE ###

S = input()
S = list(S)
cnt  = 0

while True:
    i = 0
    _cnt = 0
    while i<len(S)-1:
        if S[i] == 'B' and S[i+1] == 'W':
            S[i] = 'W'
            S[i+1] = 'B'
            _cnt += 1
            i += 1
        else:
            i += 1
    cnt += _cnt
    if _cnt == 0:
        break

print(cnt)


### FIXED CODE ###

S = input()
cnt  = 0
nb = 0
for i in range(len(S)):
    if S[i] == 'B':
        nb += 1
    else:
        cnt += nb
print(cnt)
### BUGGY CODE ###

def factoring(n):
    if n == 1:
        return dict()
    p = 2
    tmp1 = int(n**0.5)
    ret = {}
    tmp = 0
    while n != 1:
        if n % p == 0:
            n //= p
            tmp += 1
        elif p > tmp1:
            ans_dic[p] = max(ans_dic.get(p, 0), tmp)
            p = n
            tmp = 0
        else:
            ans_dic[p] = max(ans_dic.get(p, 0), tmp)
            p += 1
            tmp = 0
    ans_dic[p] = max(ans_dic.get(p, 0), tmp)
    return ret


N = int(input())
A = [int(input()) for _ in range(N)]
ans_dic = {}
for a in A:
    factoring(a)

ret = 1
for k, v in ans_dic.items():
    ret *= k**v
print(ret)

### FIXED CODE ###

def gcd(a, b):
    sm = min(a, b)
    la = max(a, b)
    if la % sm == 0:
        return sm
    else:
        return gcd(sm, la % sm)


N = int(input())
A = [int(input()) for _ in range(N)]

ans = 1
for a in A:
    ans = a * ans // gcd(a, ans)
print(ans)
### BUGGY CODE ###

#D
from collections import deque
n,q=map(int,input().split())
data=[[] for i in range(n+1)]
counter=deque([0 for i in range(n+1)])
for i in range(n-1):
    a,b=map(int,input().split())
    data[a].append(b)
    data[b].append(a)
for i in range(q):
    p,x=map(int,input().split())
    counter[p]+=x
h=deque([1])
while h:
    a=h.popleft()
    for i in range(len(data[a])):
        counter[data[a][i]]+=counter[a]
        h.append(data[a][i])
        data[data[a][i]].remove(a)
counter.popleft()
print(*counter)

### FIXED CODE ###

#D
n,q=map(int,input().split())
data=[[] for i in range(n+1)]
counter=[0]*(n+1)
for i in range(n-1):
    a,b=map(int,input().split())
    data[a].append(b)
    data[b].append(a)
for i in range(q):
    p,x=map(int,input().split())
    counter[p]+=x
h=[1]
done=[0]*(n+1)
while h:
    a=h.pop()
    for l in data[a]:
        if done[l]==0:
            counter[l]+=counter[a]
            h.append(l)
    done[a]=1
print(*counter[1:])
### BUGGY CODE ###

N,K,L=map(int,input().split())
PQ=[list(map(int,input().split())) for i in range(K)]
RS=[list(map(int,input().split())) for i in range(L)]

import sys

def find_root(root,x):
    y = root[x]
    if x == y:
        return x
    z = find_root(root,y)
    root[x] = z
    return z
 
def merge(root,size,x,y):
    x = find_root(root,x)
    y = find_root(root,y)
    if x == y:
        return
    sx,sy = size[x],size[y]
    if sx < sy:
        sx,sy = sy,sx
        x,y = y,x
    root[y] = x
    size[x] += sy
    
def UF_make(graph,n):
    Root=list(range(n+1))
    Size=[1] * (n+1)
    for i in range(len(graph)):
        merge(Root,Size,graph[i][0],graph[i][1])
    for i in range(n+1):
        Root[i] = find_root(Root,i)
    Root.pop(0)
    return Root

PQN=UF_make(PQ,N)
RSN=UF_make(RS,N)

if N<=10:
    PQRS=[]
    for i in range(N):
        PQRS.append([PQN[i],RSN[i]])
    ans=[1]*N
    for i in range(N):
        ans[i]=PQRS.count(PQRS[i])
    print(*ans)
    sys.exit()

PQRS=[PQN[i]*10**6+RSN[i] for i in range(N)]
D=len(set(PQRS))
PQRS=[[PQRS[i],i,0] for i in range(N)]
PQRS.sort()

p=0
if D==1:
    PPQQ=[]
    for i in range(K):
        PPQQ.append(PQ[i][0])
        PPQQ.append(PQ[i][1])
    T=[PPQQ.count(i)+1 for i in range(1,N+1)]
    print(*T)
else:
    while p<N:
        i=1
        c=0
        if p+i>=N-1:
            break
        while PQRS[p][0]==PQRS[p+i][0]:
            c+=1
            i+=1
        for j in range(p,p+i):
            PQRS[j][2]=c
        p+=i
    PQRS.sort(key=lambda x:x[1])
    for i in range(N):
        print(PQRS[i][2]+1,end=' ')

### FIXED CODE ###

N,K,L=map(int,input().split())
PQ=[list(map(int,input().split())) for i in range(K)]
RS=[list(map(int,input().split())) for i in range(L)]

def find_root(root,x):
    y = root[x]
    if x == y:
        return x
    z = find_root(root,y)
    root[x] = z
    return z
 
def merge(root,size,x,y):
    x = find_root(root,x)
    y = find_root(root,y)
    if x == y:
        return
    sx,sy = size[x],size[y]
    if sx < sy:
        sx,sy = sy,sx
        x,y = y,x
    root[y] = x
    size[x] += sy
    
def UF_make(graph,n):
    Root=list(range(n+1))
    Size=[1] * (n+1)
    for i in range(len(graph)):
        merge(Root,Size,graph[i][0],graph[i][1])
    for i in range(n+1):
        Root[i] = find_root(Root,i)
    Root.pop(0)  #
    return Root

PQN=UF_make(PQ,N)
RSN=UF_make(RS,N)
PQRS=[PQN[i]*10**6+RSN[i] for i in range(N)]
D=len(set(PQRS))
PQRS=[[PQRS[i],i,0] for i in range(N)]
PQRS.sort()

p=0
while p<N:
    i=1
    c=0
    if p+i>N-1:
        break
    while PQRS[p][0]==PQRS[p+i][0]:
        c+=1
        i+=1
        if p+i>N-1:
            break
    for j in range(p,p+i):
        PQRS[j][2]=c
    p+=i
PQRS.sort(key=lambda x:x[1])
for i in range(N):
    print(PQRS[i][2]+1,end=' ')
### BUGGY CODE ###

def resolve():
    N = int(input())

    ans = 0
    for n in range(1, N+1):
        for m in range(n, N+1, n):
            ans += m
    print(ans)

if __name__ == "__main__":
    resolve()

### FIXED CODE ###

def resolve():
    N = int(input())

    ans = 0
    for i in range(1, N+1):
        n = N // i
        ans += i * (n + 1) * n // 2
    print(ans)

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

N = int(input())
tmp_A = list(map(int, input().split()))
A = [0] + tmp_A

tmp_A = sorted(tmp_A)
min_h = sum(tmp_A[0:2])
max_h = sum(tmp_A[-2:])

ans = 0
for n in range(1, N + 1):
    now_h = A[n]
    min_i = max(n + 1, min(min_h, N))
    max_i = min(max_h + n + 1, N + 1)
    for i in range(min_i, max_i):
        if A[n] + A[i] is abs(n - i):
            ans += 1

print(ans)


### FIXED CODE ###

from collections import defaultdict

N = int(input())
A = [0] + list(map(int, input().split()))
d = defaultdict(int)

ans = 0
for i in range(1, N + 1):
    d[A[i] + i] += 1  # Ai + iを数える
    ans += d[i - A[i]]

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

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

A.sort()

for i in range(M):
    A[-1] = A[-1]//2
    A.sort()

print(sum(A))


### FIXED CODE ###

import heapq

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

heapq.heapify(A)

for i in range(M):
    a = -heapq.heappop(A)//2
    heapq.heappush(A, -a)
    
print(-sum(A))
### BUGGY CODE ###

import sys
import queue
#+++++
		
def main():
	n,q = map(int, input().split())
	tree=[[] for _ in range(n+1)]
	hh=[ 0 for _ in range(n+1)]
	ret=[0 for _ in range(n+1)]
	
	for i in range(n-1):
		pa,ch = map(int, input().split())
		tree[pa].append(ch)
		
	for v in range(q):
		nd, hv = map(int, input().split())
		hh[nd] += hv
		
	ol = queue.Queue()
	ret[1]=hh[1]
	vv=hh[1]
	for cc in tree[1]:
		ol.put((vv,cc))
		
	while not ol.empty():
		ph,nd=ol.get()
		ret[nd]=hh[nd]+ph
		vv=ret[nd]
		for cc in tree[nd]:
			ol.put((vv,cc))

	print(' '.join([str(v) for v in ret[1:]]))
	
	
#+++++

if __name__ == "__main__":
	if sys.platform =='ios':
		sys.stdin=open('inputFile.txt')
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

### FIXED CODE ###

import sys
import queue
#+++++
		
def main():
	n,q = map(int, input().split())
	tree=[[] for _ in range(n+1)]
	hh=[0 for _ in range(n+1)]
	ret=[0 for _ in range(n+1)]
	
	for i in range(n-1):
		pa,ch = map(int, input().split())
		tree[pa].append(ch)
		
	for v in range(q):
		nd, hv = map(int, input().split())
		hh[nd] += hv
		
	ol = queue.Queue(n+1)
	ret[1]=hh[1]
	vv=hh[1]
	for cc in tree[1]:
		ol.put((vv,cc))
		
	while not ol.empty():
		ph,nd=ol.get()
		ret[nd]=hh[nd]+ph
		vv=ret[nd]
		for cc in tree[nd]:
			ol.put((vv,cc))

	rets=' '.join([str(v) for v in ret[1:]])
	print(rets)
	
	
#+++++

if __name__ == "__main__":
	if sys.platform =='ios':
		sys.stdin=open('inputFile.txt')
	else:
		pass
		input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)
### BUGGY CODE ###

N = int(input())
S = list(input())
Q = []
for i in range(0,N) :
    if i == 0 :
        A = S[0:i]
        B = S[i+1:N]
        Q.append(A.count("W")+B.count("E"))
    elif S[i-1] == "E" :
        A = S[0:i]
        B = S[i+1:N]
        Q.append(A.count("W")+B.count("E"))
print(min(Q))



### FIXED CODE ###

N = int(input())
S = list(input())
ANS = []
ans = 0
for i in range(0,N) :
    if i == 0 :
        ans += S[1:].count("E")
        ANS.append(ans)
    elif S[i-1] == "E" and S[i] == "E" :
        ans -= 1
        ANS.append(ans)
    elif S[i-1] == "W" and S[i] == "W" :
        ans += 1
        ANS.append(ans)
print(min(ANS))
### BUGGY CODE ###

S = input()
mod_bucket = [0] * 2019
mod_bucket[0] += 1

_S = S[::-1]
mod = 0
p = 1
for i in range(len(S)):
    mod = (p * int(_S[i]) + mod) % 2019
    mod_bucket[mod] += 1
    p *= 10

ans = sum([mod*(mod-1)/2 for mod in mod_bucket])
print(int(ans))


### FIXED CODE ###

S = input()
mod_bucket = [0] * 2019
mod_bucket[0] += 1

_S = S[::-1]
mod = 0
p = 1
for i in range(len(S)):
    mod = (p * int(_S[i]) + mod) % 2019
    mod_bucket[mod] += 1
    p *= 10
    p %= 2019

ans = sum([mod*(mod-1)/2 for mod in mod_bucket])
print(int(ans))
### BUGGY CODE ###

N, W = map(int, input().split())
items = []
for _ in range(N):
    items.append(tuple(map(int, input().split())))
dp = {i: {j: 0 for j in range(W+1)} for i in range(N+1)}
for i in range(1, N+1):
    w, v = items[i-1]
    for j in range(W+1):
        if j - w >= 0:
            dp[i][j] = max(dp[i-1][j-w] + v, dp[i-1][j])
        else:
            dp[i][j] = dp[i-1][j]
print(max(dp[N].values()))

### FIXED CODE ###

import numpy as np

N, W = map(int, input().split())
items = []
for _ in range(N):
    items.append(tuple(map(int, input().split())))
dp = np.array([[0 for j in range(W+1)] for _ in range(N+1)])
for i in range(1, N+1):
    w, v = items[i-1]
    dp[i, :w] = dp[i-1, :w]
    dp[i, w:] = np.maximum(dp[i-1, :-w] + v, dp[i-1, w:])
print(dp[N, W])
### BUGGY CODE ###

from collections import deque  
d = deque()

S = input()
Q = int(input())
Query = [input() for i in range(Q)]

#最初の文字列をdに追加
for i in range(len(S)):
    d.append(S[i])

# 先頭から読むか，末尾から読むかを判定する
# 偶数 -> 先頭から，奇数 -> 末尾から
isReadOrientation = 0

for i in range(Q):
    if len(Query[i]) == 1:
        isReadOrientation += 1
    else:
        #先頭に追加
        if Query[i][2] == "1":
            #先頭に追加
            if isReadOrientation % 2 == 0:
                d.appendleft(Query[i][4])
            #末尾に追加
            else:
                d.append(Query[i][4])
        #末尾に追加
        else:
            #末尾に追加
            if isReadOrientation % 2 == 0:
                d.append(Query[i][4])
            #先頭に追加
            else:
                d.appendleft(Query[i][4])

ans = ""
#先頭から文字列に記録
if isReadOrientation % 2 == 0:
    for i in range(len(d)):
        ans += d[i]
#末尾から文字列に記録
else:
    for i in range(len(d)-1,-1,-1):
        ans += d[i]
print(ans)

### FIXED CODE ###

from collections import deque  
d = deque(input())
Q = int(input())
Query = [input() for i in range(Q)]

# 先頭から読むか，末尾から読むかを判定する
# 偶数 -> 先頭から，奇数 -> 末尾から
isReadOrientation = 0

for i in range(Q):
    if len(Query[i]) == 1:
        isReadOrientation += 1
    else:
        #先頭に追加
        if Query[i][2] == "1":
            #先頭に追加
            if isReadOrientation % 2 == 0:
                d.appendleft(Query[i][4])
            #末尾に追加
            else:
                d.append(Query[i][4])
        #末尾に追加
        else:
            #末尾に追加
            if isReadOrientation % 2 == 0:
                d.append(Query[i][4])
            #先頭に追加
            else:
                d.appendleft(Query[i][4])

#先頭から文字列に記録
if isReadOrientation % 2 != 0:
    d.reverse()
print("".join(d))
### BUGGY CODE ###

#!/usr/bin/env python

import sys

s= sys.stdin.readline().strip()
n= len(s)
#
MOD=10**9+7
#
base = 1
dp= [ [0]*13 for _ in range(n+1) ]
dp[0][0] = 1
for i,c in enumerate(reversed(s)):
    prev= dp[i]
    now = dp[i+1]
    #
    if c=="?":
        for b in [ base*i for i in range(10) ]:
            for m,num in enumerate(prev):
                if num==0: continue
                idx= (m+b)%13
                now[idx]= now[idx]+num
        #
        for i in range(13): now[i] %= MOD
    else:
        b= base*int(c)
        for m in range(13):
            idx= (m+b)%13
            now[idx]= prev[m]
    #
    base = base*10
#
print(dp[n][5])


### FIXED CODE ###

import sys
 
s= sys.stdin.readline().strip()
#
MOD=10**9+7
mmap= []
for i in range(6):
    b = 10**i % 13
    mmap.append( [ [ (b*i+j)%13 for i in range(1,10) ] for j in range(13) ] )
#
dp= [ 0 ] * 13
dp[0] = 1
j= 0
for c in reversed(s):
    tmp = dp.copy()
    #
    if c=="0": pass
    elif c=="?":
        bset = mmap[j]
        for m,num in enumerate(tmp):
            if num==0: continue
            for idx in bset[m]: dp[idx]+=num
        #
        for i in range(13): dp[i]%=MOD
    else:
        b= mmap[j][0][int(c)-1]
        for m in range(13):
            idx= (m+b)%13
            dp[idx]= tmp[m]
    #
    if j==5: j=0
    else: j+=1
#
print(dp[5])
### BUGGY CODE ###

import itertools
import math

n, k = map(int, input().split())
alist = sorted(list(map(int, input().split())))
divide = 10**9 + 7

def comb(n, k):
    return math.factorial(n) // (math.factorial(n-k) * math.factorial(k))

amax = 0
i = n-1
while i >= k-1:
    amax += alist[i] * comb(i, k-1)
    i -= 1

amin = 0
i = 0
while i <= n-k:
    amin += alist[i] * comb(n-i-1, k-1)
    i += 1

print((amax - amin) % divide)

### FIXED CODE ###

n, k = map(int, input().split())
alist = sorted(map(int, input().split()))
mod = 10**9 + 7

def comb(n, r, p=mod):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p

fact = [1, 1]
factinv = [1, 1]
inv = [0, 1]
p = mod
N = n
for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)

amax = 0
amin = 0
i = 0
while i <= n-k:
    cnt = comb(n-i-1, k-1)
    amax += (alist[n-i-1] * cnt)%mod
    amin += (alist[i] * cnt)%mod
    i += 1

print((amax - amin) % mod)
### BUGGY CODE ###

X,Y,Z,K=map(int,input().split())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
C=list(map(int,input().split()))

A.sort(reverse=True)
B.sort(reverse=True)
C.sort(reverse=True)

K=min(K,3000)

AB=[a+b for a in A for b in B]
AB.sort(reverse=True)

ABC=[ab+c for ab in AB[:K] for c in C]
ABC.sort(reverse=True)

for k in range(K):
	print(ABC[k])


### FIXED CODE ###

X,Y,Z,K=map(int,input().split())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
C=list(map(int,input().split()))

A.sort(reverse=True)
B.sort(reverse=True)
C.sort(reverse=True)

K=min(K,3000)

AB=[a+b for a in A for b in B]
AB.sort(reverse=True)

ABC=[ab+c for ab in AB[:K] for c in C[:K]]
ABC.sort(reverse=True)

for k in range(K):
	print(ABC[k])
### BUGGY CODE ###

n = int(input())
s = input()
ans = 0

for i in range(n):
    for j in range(i,n):
        for k in range(j,n):
            if s[i] != s[j] and s[j] != s[k] and s[k] != s[i] and j-i != k-j:
                ans += 1

print(ans)

### FIXED CODE ###

n = int(input())
s = input()

r_cnt = s.count('R')
g_cnt = s.count('G')
b_cnt = s.count('B')

# print(r_cnt, g_cnt, b_cnt)
ans = r_cnt * g_cnt * b_cnt
# print(ans)

for i in range(n):
    for d in range(n):
        j = i + d
        k = j + d
        # print(i,j,k)
        if k >= n: 
            # print('/')
            break
        if s[i] != s[j] and s[j] != s[k] and s[k] != s[i]:
            ans -= 1

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

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

ans = 0

for i in range(N):
    for j in range(i,N+1):
        if i != j:
            if sum(A[i:j]) == 0:
                ans += 1

print(ans)


### FIXED CODE ###

from itertools import accumulate
from collections import Counter

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

B = [0] + list(accumulate(A))
C = Counter(B)

ans = 0
for i in set(B):
    p = C[i]
    ans += p*(p-1)//2

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

Q = int(input())
Y = []
D = []
S = [0] * Q
s = 0
for i in range(Q):
    a = list(map(int, input().split()))
    Y.append(a)
    if a[0] == 1:
        D.append(a[1])
        s += a[2]
    S[i] = s

D = sorted(list(set(D)))
INV = {}
for i in range(len(D)):
    INV[D[i]] = i

N = 17
X = [0] * (2**(N+1)-1)
C = [0] * (2**(N+1)-1)

def add(j, x):
    i = 2**N + j - 1
    while i >= 0:
        X[i] += x
        C[i] += 1
        i = (i-1) // 2

def rangeof(i):
    s = (len(bin(i+1))-3)
    l = ((i+1) - (1<<s)) * (1<<N-s)
    r = l + (1<<N-s)
    return (l, r)

def rangesum(a, b):
    l = a + (1<<N)
    r = b + (1<<N)
    s = 0
    while l < r:
        if l%2:
            s += X[l-1]
            l += 1
        if r%2:
            r -= 1
            s += X[r-1]
        l >>= 1
        r >>= 1
    return s
def rangecnt(a, b):
    l = a + (1<<N)
    r = b + (1<<N)
    s = 0
    while l < r:
        if l%2:
            s += C[l-1]
            l += 1
        if r%2:
            r -= 1
            s += C[r-1]
        l >>= 1
        r >>= 1
    return s

c = 0
su = 0
CC = [0] * (2**N)
for i in range(Q):
    y = Y[i]
    if y[0] == 1:
        add(INV[y[1]], y[1])
        CC[INV[y[1]]] += 1
        c += 1
        su += y[1]
    else:
        l, r = 0, 2**N
        while True:
            m = (l+r)//2
            rc = rangecnt(0, m)
            if rc >= (c+1)//2:
                r = m
            elif rc + CC[m] <= (c-1)//2:
                l = m
            else:
                break
        rs = rangesum(0, m)
        print(D[m], D[m]*rc-rs+(su-rs)-(c-rc)*D[m]+S[i])


### FIXED CODE ###

import sys
input = sys.stdin.readline
from heapq import *
Q = int(input())
L, R = [], []
ans = 0
for _ in range(Q):
    a = [int(a) for a in input().split()]
    if a[0] == 1:
        ans += a[2]
        if len(L) == 0 or a[1] <= -L[0]:
            heappush(L, -a[1])
            ans += -L[0] - a[1]
        else:
            heappush(R, a[1])
            ans += a[1] + L[0]
        if len(R) > len(L):
            ans -= R[0] + L[0]
            heappush(L, -heappop(R))
        elif len(L) - len(R) >= 2:
            heappush(R, -heappop(L))
    else:
        print(-L[0], ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(100000000)

memo={}
def c(n,k):
    if (n,k) in memo:
        return memo[(n,k)]
    else:
        memo[(n,k)] = 1 if(k<=0 or n<=k) else ( c(n-1, k-1) + c(n-1, k) ) 
    return memo[(n,k)]

n,k=map(int,input().split())
a=sorted(map(int,input().split()))
num=c(n,k)
hoge=[]
while True:
    hoge.append(c(n-1,k-1))
    if n-1==k-1:
        break
    n-=1

ans=0
for i in range(len(hoge)):
    ans-=hoge[i]*a[i]
    ans+=hoge[i]*a[-i-1]
    ans%=1000000007
print(ans)

### FIXED CODE ###

def modpow(x,p,mod):
    ret=1
    for i in range(64):
        if (1<<i)&p:
            ret=ret*x%mod
        x=x*x%mod
    return ret

def inverse_table(n,mod):
    table=[]
    for i in range(0,n+1):
        table.append(modpow(i,mod-2,mod))
    return table

def factorial_table(n,mod):
    table=[1]
    for i in range(1,n+1):
        table.append(table[-1]*i%mod)
    return table

def inverse_factorial_table(n,it,mod):
    table=[1]
    for i in range(1,n+1):
        table.append(table[-1]*it[i]%mod)
    return table

it=inverse_table(10**5,1000000007)
ft=factorial_table(10**5,1000000007)
ift=inverse_factorial_table(10**5,it,1000000007)
def c(n,k,it,ft,mod):
    return ft[n]*ift[k]*ift[(n-k)]%mod
n,k=map(int,input().split())
a=sorted(map(int,input().split()))
hoge=[]
while True:
    hoge.append(c(n-1,k-1,it,ft,1000000007))
    if n-1==k-1:
        break
    n-=1
ans=0
for i in range(len(hoge)):
    ans-=hoge[i]*a[i]%1000000007
    ans+=hoge[i]*a[-i-1]%1000000007
    ans%=1000000007
print(ans)
### BUGGY CODE ###

#!/usr/bin/env python3
import sys


def solve(N: int, M: int, p: "List[int]", S: "List[str]"):
    ac_list = []
    for (pi, si) in zip(p, S):
        if si=="AC":
            ac_list.append(pi)
    ac_list = sorted(list(set(ac_list)))
    num_ans = len(ac_list)

    num_penalty = 0
    for (pi, si) in zip(p, S):
        # check ac
        if pi in ac_list:
            if si == "WA":
                num_penalty += 1
            else:
                tmp = ac_list.remove(pi)
        if len(ac_list) == 0:
            break

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

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys


def solve(N: int, M: int, p: "List[int]", S: "List[str]"):
    wa_flag = [0] * N
    num_penalty = 0
    for i in range(M):
        if S[i] == "WA":
            if wa_flag[p[i]-1] != -1:
                wa_flag[p[i]-1] += 1
        else:
            if wa_flag[p[i]-1] != -1:
                num_penalty += wa_flag[p[i]-1]
                wa_flag[p[i]-1] = -1
    num_ac = wa_flag.count(-1)
    print(num_ac, num_penalty)
# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    N, M = map(int, input().split())
    p = [None] * M
    S = [None] * M
    for i in range(M):
        pi, si = input().split()
        p[i] = int(pi)
        S[i] = str(si)
    solve(N, M, p, S)

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

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

count = 0

x = 0
while (x <= K):
    if x > S:
        break
    y = 0
    while (y <= K):
        if y > S:
            break
        if 0 <= S - (x + y) <= K:
            count += 1
        y += 1
    x += 1



print(count)

### FIXED CODE ###

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

count = 0

x = 0
while (x <= K):
    y = 0
    while (y <= K):
        if 0 <= S - (x + y) <= K:
            count += 1
        y += 1
    x += 1



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

N,M=map(int,input().split())
sum=0
A=[int(i) for i in range(N)]
B=[int(i) for i in range(N)]
for i in range(N):
  A[i],B[i]=map(int,input().split())
while True:
  K=B[A.index(min(A))]
  if K>=M:
    print(sum+min(A)*M)
    break
  else:
    sum+=K*min(A)
  M-=K
  A[A.index(min(A))]=max(A)+1

### FIXED CODE ###

N,M=map(int,input().split())
sum=0
A=[[int(i) for i in input().split()]for j in range(N)]
A.sort()
i=0
while True:
  if A[i][1]>=M:
    sum+=A[i][0]*M
    break
  else:
    sum+=A[i][0]*A[i][1]
  M-=A[i][1]
  i+=1
print(sum)