Harryxun/stf_run huggingface dataset:
n=int(input())

nodes=[]
for i in range(n+1):
    nodes.append([])
for i in range(n-1):
    s,e,w = map(int,input().split())
    nodes[s].append((e,w))
    nodes[e].append((s,w))

col=[-1]*(n+1)

def dfs(now,color):
    col[now]=color
    for n,w in nodes[now]:
        if col[n]!=-1:
            continue
        if w%2==0:
            dfs(n,color)
        else:
            dfs(n,1-color)

dfs(1,1)

for i in range(1,n+1):
    print(col[i])

### FIXED CODE ###


import sys
sys.setrecursionlimit(1000000)
def dfs(now,color):
    col[now]=color
    for n,w in nodes[now]:
        if col[n]!=-1:
            continue
        if w%2==0:
            dfs(n,color)
        else:
            dfs(n,1-color)

n=int(input())

nodes=[]
for i in range(n+1):
    nodes.append([])
for i in range(n-1):
    s,e,w = map(int,input().split())
    nodes[s].append((e,w))
    nodes[e].append((s,w))

col=[-1]*(n+1)

dfs(1,1)

for i in range(1,n+1):
    print(col[i])
a,b,c,d = map(input().split(), int())

if a+b < c+d :
    print("Left")
elif a+b > c+d:
    print("Right")
else:
    print("Balanced")
    

### FIXED CODE ###

a,b,c,d = map(int, input().split())

if a+b < c+d :
    print("Right")
elif a+b > c+d:
    print("Left")
else:
    print("Balanced")
n,q=map(int,input().split())
ans=[0 for _ in range(n)]
gra=[[] for _ in range(n)]
visited=[0 for _ in range(n)]
for _ in range(n-1):
  a,b=map(int,input().split())
  gra[a-1].append(b-1)
  gra[b-1].append(a-1)
  
for _ in range(q):
  p,x=map(int,input().split())
  ans[p-1]+=x
  
def dfs(st):
  temp=gra[st]
  for i in temp:
    if visited[i]==0:
      visited[i]+=1
      ans[i]+=ans[st]
      dfs(i)
      
visited[0]+=1
dfs(0)

for h in range(n):
  ans[h]=str(ans[h])
  
print(' '.join(ans))

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)

n,q=map(int,input().split())
ans=[0 for _ in range(n)]
gra=[[] for _ in range(n)]
visited=[0 for _ in range(n)]

for _ in range(n-1):
  a,b=map(int,input().split())
  gra[a-1].append(b-1)
  gra[b-1].append(a-1)
  
for _ in range(q):
  p,x=map(int,input().split())
  ans[p-1]+=x
  
def dfs(st):
  temp=gra[st]
  for i in temp:
    if visited[i]==0:
      visited[i]+=1
      ans[i]+=ans[st]
      dfs(i)
      
visited[0]+=1
dfs(0)

for h in range(n):
  ans[h]=str(ans[h])
  
print(' '.join(ans))
a, b = int(input())
c = a*b
if c % 2 == 0:
  print("Even")
  else:
    print("Odd")


### FIXED CODE ###

a,b = input().split()
result = int(a) * int(b)
     
if result % 2 == 0:
	print("Even")
else :
	print("Odd")
from collections import deque

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

up = [[] for _ in range(n)] # [[]]*nした後にappendするのはNG
down = [[] for _ in range(n)]
used = [0]*n # これならOK
res = [0]*n
cnt = 0

for _ in range(n+m-1):
    p, c = map(int, input().split())
    up[c-1].append(p)
    down[p-1].append(c)

for i in range(n):
    if up[i] == []:
        root = i+1
        res[root-1] = 0
        used[root-1] = 1
        cnt += 1
        break

ptank = deque([root])
ctank = deque([root])

def find_c(p):
    for i in down[p-1]:
        if all([used[j-1]==1 for j in up[i-1]]) & (used[i-1]==0):
            res[i-1] = p
            ctank.append(i)

while cnt < n:
    ptank = ctank.copy()
    while len(ctank) != 0:
        used[ctank.popleft()-1] = 1
    while len(ptank) != 0:
        find_c(ptank.popleft())
    cnt += len(ctank)
    

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

### FIXED CODE ###

from collections import deque

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

up = [[] for _ in range(n)] # [[]]*nした後にappendするのはNG
down = [[] for _ in range(n)]
used = [0]*n # これならOK
res = [0]*n
cnt = 0

for _ in range(n+m-1):
    p, c = map(int, input().split())
    up[c-1].append(p)
    down[p-1].append(c)

for i in range(n):
    if up[i] == []:
        root = i+1
        res[root-1] = 0
        used[root-1] = 1
        cnt += 1
        break

ptank = deque([root])
ctank = deque([root])
clist = list()

def is_p_used(i):
    for j in up[i-1]:
        if used[j-1]==0:
            return False
    return True

def find_c(p):
    for i in down[p-1]:
        if (is_p_used(i)) & (used[i-1]==0):
            res[i-1] = p
            ctank.append(i)
            clist.append(i)

while cnt < n:
    ptank = ctank
    ctank = deque()
    while len(ptank) != 0:
        find_c(ptank.popleft())
    cnt += len(ctank)
    for i in clist:
        used[i-1] = 1
    clist = list()
    

for i in range(n):
    print(res[i])
n,m=map(int,input().split())
cnt=0
acc=0
ac={}
for i in range(m):
	p,s= map(str,input().split())
	if ac[p]==0:
		if s=='AC':
			acc+=1
			ac[p]=1
		else:
			cnt+=1
print(acc,cnt)

### FIXED CODE ###

import sys
input = sys.stdin.readline

def main():
    n,m=map(int,input().split())
    w=[0]*(n+1)
    a=[0]*(n+1)
    for i in range(m):
        p,s=map(str,input().split())
        p=int(p)
        if a[p]==0:
            if s=='WA':
                w[p]+=1
            else:
                a[p]=1
    wa=0
    for i in range(1,n+1):
        wa=wa+a[i]*w[i]
    print(sum(a),wa)

if __name__ == '__main__':
    main()
n=int(input())
l=sorted(list(map(int,input().split()))reverse=True)

if l[0]<sum(l[1:]):
  print("Yes")
else:
  print("No")

### FIXED CODE ###

n=int(input())
l=sorted(list(map(int,input().split())),reverse=True)

if l[0]<sum(l[1:]):
  print("Yes")
else:
  print("No")
n,m = [int(i) for i in input().split()]
if m == 1:
    print(1)
else:
    s1,e2  = {int(i) for i in input().split()}
    num_set = {i for i in range(s1,e2+1)}
    for i in range(m-1):
        s,e = [int(i) for i in input().split()]
        card_set = {i for i in range(s,e+1)}
        num_set = num_set & card_set
    
    print(len(num_set))

### FIXED CODE ###

n,m = [int(i) for i in input().split()]

l = 0
r = n
for i in range(m):
    s,e = [int(i) for i in input().split()]
    l = max(l,s)
    r = min(r,e)
    
print(max(0,r-l + 1))
N = int(input())
A = [int(i) for i in input().split()]
B = [int(i) for i in input().split()]
C = [int(i) for i in input().split()]
r = 0
a = 0
for i in range(N):
    r += B[A[i]]
    if A[i] == a+1:
        r += C[i]
    a = A[i]
print(r)

### FIXED CODE ###

N = int(input())
A = [int(i) for i in input().split()]
B = [int(i) for i in input().split()]
C = [int(i) for i in input().split()]
r = 0
a = 0
for i in range(N):
    r += B[A[i]-1]
    if  A[i]-1 > len(C):
        continue
    elif A[i] == a+1 and A[i] != 1:
        r += C[a-1]
    a = A[i]
print(r)
import sys
import math
import itertools
import collections
import heapq
import numpy as np

rl = sys.stdin.readline

h1, m1, h2, m2, k = map(int, rl().split())
m = h260 + m2 - h160 - m1
print(m-k)

### FIXED CODE ###

import sys
import math
import itertools
import collections
import heapq
import numpy as np

rl = sys.stdin.readline

h1, m1, h2, m2, k = map(int, rl().split())
m = h2*60 + m2 - h1*60 - m1
print(m-k)
n = int(input())
A = list(map(int,input().split()))
cnt = 0
B = [False for _ in range(n)]
for i,a in enumerate(A):
    print(A[a-1],i)
    print(B)
    if A[a-1] == i+1 and B[i] == False:
        cnt+=1
        B[a-1] = True
    B[i] = True
print(cnt)


### FIXED CODE ###

n = int(input())
A = list(map(int,input().split()))
cnt = 0
B = [False for _ in range(n)]
for i,a in enumerate(A):
    if A[a-1] == i+1 and B[i] == False:
        cnt+=1
        B[a-1] = True
    B[i] = True
print(cnt)
import math

n,k=map(int,input().split())
for i in range(1,k+1):
  if n-k<i-1:
      print(0)
  else :
    a=math.factorial(k-1)
    b=math.factorial(i-1)
    c=math.factorial(k-i)
    d=math.factorial(n-k+1)
    e=math.factorial(i)
    f=math.factorial(n-k-i+1)
    g=a/b/c
    h=d/e/f
    print(g*h%1000000007)
    

### FIXED CODE ###

import math

n,k=map(int,input().split())
for i in range(1,k+1):
  if n-k<i-1:
      print(0)
  else :
    a=math.factorial(k-1)
    b=math.factorial(i-1)
    c=math.factorial(k-i)
    d=math.factorial(n-k+1)
    e=math.factorial(i)
    f=math.factorial(n-k-i+1)
    g=a//b//c
    h=d//e//f
    print(g*h%1000000007)
import numpy as np
import sys
sys.setrecursionlimit(1000000)

def dfs(cost, i, A):
    if i == n-1:
        global ans
        if cost < ans and all([ai>=x for ai in A]):
            ans = cost
        return
    i += 1
    dfs(cost, i, A)
    dfs(cost+c[i], i, A+a[i])

    

if __name__ == "__main__":
    n, m, x = map(int, input().split())
    c, a = [None]*n, np.array([None]*n)
    for i in range(n):
        c[i], *a[i] = map(int, input().split())
    ans = 10**10
    dfs(0, -1, np.array([0]*m))
    if ans == 10**10:
        print(-1)
    else:
        print(ans)
    

### FIXED CODE ###

import numpy as np
import sys
sys.setrecursionlimit(100000)

def dfs(cost, i, ratio):
    if i == n:
        global ans
        if cost < ans and all([r >= x for r in ratio]):
            ans = cost
        return
    dfs(cost, i+1, ratio)
    dfs(cost+c[i], i+1, ratio+a[i])

if __name__ == "__main__":
    n, m, x = map(int, input().split())
    c = [None]*n
    a = np.array([None]*n)
    for i in range(n):
        c[i], *a[i] = map(int, input().split())
    ans = 10**8
    dfs(0, 0, np.array([0]*m))
    if ans == 10**8:
        print(-1)
    else:
        print(ans)
# import sys
from collections import defaultdict
# sys.setrecursionlimit(10**9)
n,m = map(int,input().split())
d = defaultdict(list)
for i in range(m):
    x,y = map(int,input().split())
    d[x-1].append(y-1)

dp = [-1]*n

def rec(v):
    if dp[v] != -1:
        return dp[v]
    res = 0
    for nv in d[v]:
        res = max(res,rec(nv)+1)
    dp[v] = res
    return res

res = 0
for v in range(n):
    res = max(res,rec(v))
print(res)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**9)
from collections import defaultdict

n,m = map(int,input().split())
d = defaultdict(list)
for i in range(m):
    x,y = map(int,input().split())
    d[x-1].append(y-1)

dp = [-1]*n

def rec(v):
    if dp[v] != -1:
        return dp[v]
    res = 0
    for nv in d[v]:
        res = max(res,rec(nv)+1)
    dp[v] = res
    return res

res = 0
for v in range(n):
    res = max(res,rec(v))
print(res)
import sympy
n = int(input())
ans = 0
for i in range(1,n):
    ans += sympy.divisor_count(i)
print(ans)

### FIXED CODE ###

n = int(input())
ans = 0
for i in range(1,n):
    ans += (n-1)//i
print(ans)
n, m = map(int, input.split())

print((n-1) * (m-1))

### FIXED CODE ###

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

print((n-1) * (m-1))
#!/mnt/c/Users/moiki/bash/env/bin/python
H,W      = list(map(int, input().split()))
S        =  [ list(input()) for _ in range(H)]
NUM_GRID = [ [-1] * W for _ in range(H) ]


united_count = [ ]
# [ (黒1個、白2個) ,... k 個] 

directions = [(1,0), (0,1), (-1,0), (0,-1)] # y,x の順番
def dfs(pos, c, now_k):
    # pos : (1,2)
    # 引数は現在の連結成分の番号
    # 座標と、現在の1,0 が渡される
    # 渡されたnow_kで塗りつぶす
    y,x = pos
    for d in directions:
        if y+d[0] < 0 or x+d[1] < 0 or y+d[0] >= H or x+d[1] >= W:
            continue

        content = S[y+d[0]][x+d[1]] 

        if c != content and NUM_GRID[y+d[0]][x+d[1]] == -1:

            NUM_GRID[y+d[0]] [x+d[1]] = now_k  # 塗る
            inplace_tuple     = united_count[now_k]
            united_count[now_k]     = ( inplace_tuple[0] + 1, inplace_tuple[1]) if content == "#" else \
                                ( inplace_tuple[0]    , inplace_tuple[1]+1) # タプルなので新しく作る

            dfs( (y+d[0], x+d[1]),  content,  now_k)  # DFSかける

        else:
            continue



now_k = 0
for y in range(H):
    for x in range(W):
        c = S[y][x]  
        if NUM_GRID[y][x] == -1:

            united_count.append( (1,0) if  c == "#" else (0,1) ) # now_k番目
            NUM_GRID[y][x] = now_k  # cの値は黒だったら、1 を入れてdfsに投げる

            pos = (y,x)
            dfs(pos, c, now_k)
            now_k         += 1

        else:
            continue # もう数字が入っている場合は、パス

# for y in range(H):
#     for x in range(W):
#         print(NUM_GRID[y][x], end="")
#     print("")


answer = 0
mod    = int(1e9)+7
for uni in united_count:
    answer = ((uni[0]*uni[1])%mod + answer) % mod

print(answer)




### FIXED CODE ###

#!/mnt/c/Users/moiki/bash/env/bin/python
H,W      = list(map(int, input().split()))
S        =  [ list(input()) for _ in range(H)]

import sys
sys.setrecursionlimit(2600000)

united_count = [ ]
# [ (黒1個、白2個) ,... k 個] 

directions = [(1,0), (0,1), (-1,0), (0,-1)] # y,x の順番


def dfs(pos, c, now_k):
    # pos : (1,2)
    # 引数は現在の連結成分の番号
    # 座標と、現在の1,0 が渡される
    # 渡されたnow_kで塗りつぶす
    y,x = pos
    for d in directions:
        try:
            if y+d[0] < 0 or x+d[1] < 0:
                continue
            content = S[y+d[0]][x+d[1]] 

            if c != content and (content == "#" or content == ".") :
                S[y+d[0]][x+d[1]] = now_k
                inplace_tuple     = united_count[now_k]
                united_count[now_k]     = ( inplace_tuple[0] + 1, inplace_tuple[1]) if content == "#" else \
                                    ( inplace_tuple[0]    , inplace_tuple[1]+1) # タプルなので新しく作る

                dfs( (y+d[0], x+d[1]),  content,  now_k)  # DFSかける

            else:
                continue
        except:
            continue



now_k = 0
for y in range(H):
    for x in range(W):
        c = S[y][x]  
        if c == "#" or c == "." :
            united_count.append( (1,0) if  c == "#" else (0,1) ) # now_k番目
            S[y][x] = now_k  # cの値は黒だったら、1 を入れてdfsに投げる

            pos = (y,x)
            dfs(pos, c, now_k)
            now_k         += 1

        else:
            continue # もう数字が入っている場合は、パス


answer = 0
for uni in united_count:
    answer = ((uni[0]*uni[1]) + answer) 

print(answer)
H, W = map(int, input().split())
S = [input() for _ in range(H)]

x = [[0 for _ in range(W)] for _ in range(H)]
y = [[0 for _ in range(W)] for _ in range(H)]

for i, j in ((i, j) for i in range(H) for j in range(W) if S[i][j] == '.'):
    if x[i][j] == 0:
        w = len(list(takewhile(lambda k: S[i][k] == '.', range(j, W))))
        for k in range(j, j + w):
            x[i][k] = w
    if y[i][j] == 0:
        h = len(list(takewhile(lambda k: S[k][j] == '.', range(i, H))))
        for l in range(i, i + h):
            y[l][j] = h

ans = max(
    x[i][j] + y[i][j] - 1
    for i in range(H)
    for j in range(W)
)
# 出力
print(ans)

### FIXED CODE ###

from itertools import takewhile

H, W = map(int, input().split())
S = [input() for _ in range(H)]

x = [[0 for _ in range(W)] for _ in range(H)]
y = [[0 for _ in range(W)] for _ in range(H)]

for i, j in ((i, j) for i in range(H) for j in range(W) if S[i][j] == '.'):
    if x[i][j] == 0:
        w = len(list(takewhile(lambda k: S[i][k] == '.', range(j, W))))
        for k in range(j, j + w):
            x[i][k] = w
    if y[i][j] == 0:
        h = len(list(takewhile(lambda k: S[k][j] == '.', range(i, H))))
        for l in range(i, i + h):
            y[l][j] = h

ans = max(
    x[i][j] + y[i][j] - 1
    for i in range(H)
    for j in range(W)
)
# 出力
print(ans)
if (a * b) % 2 == 1:
    print("Odd")
else:
    print("Even")

### FIXED CODE ###

a,b = map(int,input().split())
if (a * b) % 2 == 1:
    print("Odd")
else:
    print("Even")
import math

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

fac = [1]
caf = [1]


def pow(n, p):
    res = 1
    while p > 0:
        if p % 2 == 0:
            n = n ** 2 % mod
            p //= 2
        else:
            res = res * n % mod
            p -= 1
    return res % mod


n = (x + y) // 3 + 1

for i in range(1, n):
    fac.append((fac[i - 1] * i) % mod)
    caf.append(pow(fac[i], mod - 2))


def ncr(n, r):
    if n < r:
        return 0
    return (fac[n] * caf[r] * caf[n - r]) % mod


if (x + y) % 3 != 0:
    print(0)
else:
    n = (x + y) // 3
    r = (2 * x - y) // 3
    print(ncr(n, r))



### FIXED CODE ###

import math
import sys

sys.setrecursionlimit(10 ** 7)


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

fac = [1]
caf = [1]


def pow(n, p):
    res = 1
    while p > 0:
        if p % 2 == 0:
            n = n ** 2 % mod
            p //= 2
        else:
            res = res * n % mod
            p -= 1
    return res % mod


n = (x + y) // 3 + 10

for i in range(1, n):
    fac.append((fac[i - 1] * i) % mod)
    caf.append(pow(fac[i], mod - 2))


def ncr(n, r):
    if n < r or r < 0:
        return 0
    return (fac[n] * caf[r] * caf[n - r]) % mod


if (x + y) % 3 != 0:
    print(0)
else:
    n = (x + y) // 3
    r = (2 * x - y) // 3
    print(ncr(n, r))
L, R = map(int, input().split())
import numpy as np
min = 2019
for i in range(L, R+1):
    for j in range(i+1, R+1):
        if (i*j)%2019 < min:
            min = (i*j)%2019

print(min)


### FIXED CODE ###

import sys
import fractions
from collections import Counter, deque, defaultdict
from math import factorial
import heapq, bisect
import math
import itertools
sys.setrecursionlimit(10 ** 5 + 10)
INF = 10**15 +5
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))

a,b,c = MAP()
print(min(a*b,c))
import math
import sys
import itertools
import queue
from fractions import gcd

def lcm(a, b):
    return a * b // gcd(a, b)

mod = 1000000007

"""
# 0埋め, 小数点出力桁指定時のときの出力
a = 100
b = 0.987654321
print("{0:06d}-{1:6f}".format(a,b))
000100-0.987654

# 文字列をリストに格納
char_list = list("abcd") # ["a","b","c","d"]

# 標準入力取得
## 文字列
    = sys.stdin.readline().rstrip()
    = list(sys.stdin.readline().rstrip())

## 数値
    = int(sys.stdin.readline())
    = map(int, sys.stdin.readline().split())
    = list(map(int, sys.stdin.readline().split()))
    = [list(map(int,list(sys.stdin.readline().split()))) for i in range(h)]  # 二次元配列入力　二次元マップみたいな入力のとき
"""

from math import factorial

if __name__ == "__main__":
    N = int(sys.stdin.readline())
    #mng = [][]
    sl = []
    mng = []
    for _ in range(N):
        s = set(sys.stdin.readline().rstrip())
        if s in sl:
            i = sl.index(s)
            mng[i] += 1
        else:
            sl.append(s)
            mng.append(0)

    ans = 0
    r = 2
    #print(mng)
    for n in mng:
        if n > 0:
            n += 1
            ans += factorial(n) / factorial(r) / factorial(n - r)

    print(int(ans))

### FIXED CODE ###

import math
import sys
import itertools
import queue
from fractions import gcd

import sys
sys.setrecursionlimit(10000)

def lcm(a, b):
    return a * b // gcd(a, b)

mod = 1000000007

"""
# 0埋め, 小数点出力桁指定時のときの出力
a = 100
b = 0.987654321
print("{0:06d}-{1:6f}".format(a,b))
000100-0.987654

# 文字列をリストに格納
char_list = list("abcd") # ["a","b","c","d"]

# 標準入力取得
## 文字列
    = sys.stdin.readline().rstrip()
    = list(sys.stdin.readline().rstrip())

## 数値
    = int(sys.stdin.readline())
    = map(int, sys.stdin.readline().split())
    = list(map(int, sys.stdin.readline().split()))
    = [list(map(int,list(sys.stdin.readline().split()))) for i in range(h)]  # 二次元配列入力　二次元マップみたいな入力のとき
"""

from math import factorial
import collections

if __name__ == "__main__":
    N = int(sys.stdin.readline())
    #mng = [][]
    sl = []
    for _ in range(N):
        tmp = sorted(sys.stdin.readline().rstrip())
        #print(''.join(tmp))
        sl.append(''.join(tmp))
    #print(sl)
    c = collections.Counter(sl)
    ans = 0
    for n in c.values():
        r = 2
        if n > 1:
            ans += factorial(n) // (factorial(n - r) * factorial(r))

    print(int(ans))
#%%
N = int(input())
A = [0 for i in range(N)]
for i in range(N):
    A[i] = list(map(int,input().split()))

print(A)

### FIXED CODE ###


N = int(input())
A = [0 for i in range(N)]
for i in range(N):
    A[i] = list(map(str,input().split()))
for i in range(N):
    A[i].append(str(i+1))
for i in range(N):
    A[i][1] = int(A[i][1]) 


B = sorted(A, key=lambda x: x[1], reverse=True)

C = sorted(B, key=lambda x: x[0])

for i in range(N):
    print(int(C[i][2]))
y,m,d = input().split()
print("Heisei" if int(y+m+d) <= 20190430 else "TBD")

### FIXED CODE ###

y,m,d = input().split('/')
print("Heisei" if int(y+m+d) <= 20190430 else "TBD")
a=list(int(input()) for i in range(5))

b=[-(-a[i]//10)*10 for i in range(5)]
c=[a[i]%10 for i in range(5) if a[i]%10 != 0]

print(sum(b) + min(c) -10)


### FIXED CODE ###

a=list(int(input()) for i in range(5))

b=[-(-a[i]//10)*10 for i in range(5)]
c=[a[i]%10 for i in range(5) if a[i]%10 != 0]

if c != []:
    print(sum(b) + min(c) -10)
else:
    print(sum(b))
from bisect import bisect_left
import numpy


def main():
    def isOK(score):
        count = 0
        for a in reversed(A):
            border_score = score - a
            index = bleft(A, border_score)
            count += N - index
            if count >= M:
                return True
        return False

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

    ng = A[-1] + A[-1] + 1
    ok = A[0] + A[0]
    bleft = bisect_left

    while(abs(ok-ng) > 1):
        #print(ok, ng)
        mid = (ok+ng) // 2
        f = isOK(mid)
        if f:
            ok = mid
        else:
            ng = mid
        #print(f)
        #print(ok, ng)
    C = [0,] + A
    C = numpy.cumsum(C[::-1])
    #print(C)
    min_score = float('inf')
    count = 0
    for a in reversed(A):
        index = bleft(A, ok-a)
        if index < N:
            min_score = min(a+A[index], min_score)
            ans += C[N-index-1] + (N-index) * a
            count += N-index

    ans -= min_score * (count-M)
    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

from bisect import bisect_left
import numpy


def main():
    def isOK(score):
        count = 0
        for a in reversed(A):
            border_score = score - a
            index = bleft(A, border_score)
            count += N - index
            if count >= M:
                return True
        return False

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

    ng = A[-1] + A[-1] + 1
    ok = A[0] + A[0]
    bleft = bisect_left

    while(abs(ok-ng) > 1):
        #print(ok, ng)
        mid = (ok+ng) // 2
        f = isOK(mid)
        if f:
            ok = mid
        else:
            ng = mid
        #print(f)
        #print(ok, ng)
    C = [0,] + A
    C = numpy.cumsum(C[::-1])
    #print(C)
    min_score = float('inf')
    count = 0
    for a in reversed(A):
        index = bleft(A, ok-a)
        if index < N:
            min_score = min(a+A[index], min_score)
            ans += C[N-index-1] + (N-index) * a
            count += N-index

    ans -= min_score * (count-M)
    print(ans)


if __name__ == '__main__':
    main()
S = input()
if S == "ABC":
  print("ARC")
 else:
  print("ABC")

### FIXED CODE ###

S = input()
if S == "ABC":
  print("ARC")
else:
  print("ABC")
a = int(input())
b = int(input())
if a%500 <= b:
  print(Yes)
else:
  print(No)

### FIXED CODE ###

a = int(input())
b = int(input())
if a%500 <= b:
  print("Yes")
else:
  print("No")
A, B = map(int, input())

if A%2 != B%2:
  print("IMPOSSIBLE")
else:
  print((A+B)/2)

### FIXED CODE ###

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

if A%2 != B%2:
  print("IMPOSSIBLE")
else:
  print(int((A+B)/2))
a,b,c=map(string,input().split("/"))
print("2018/"+b+"/"+c)

### FIXED CODE ###

a,b,c=map(str,input().split("/"))
print("2018/"+b+"/"+c)
n = input()
s = 0
for i in range(n+1):
  l = list(int(i))
  if len(l) % 2 == 1:
    s += 1
print(s)

### FIXED CODE ###

n = int(input())
s = 0
for i in range(1,n+1):
  l = list(str(i))
  if len(l) % 2 == 1:
    s += 1
print(s)
n, m = map(int, input().split())
a = []
for _ in range(n):
    a.append(list(map(int, input().split())))
a.sort()
pm = s = 0
m_minus_1 = m - 1
for item in a:
    pm += item[1]
    if tmp > m_minus_1:
        print(s + item[0] * (m - pm + item[1]))
        break
    else:
        s += item[0] * item[1]


### FIXED CODE ###

n, m = map(int, input().split())
a = []
for _ in range(n):
    a.append(list(map(int, input().split())))
a.sort()
pm = s = 0
for item in a:
    if pm + item[1] >= m:
        print(s + item[0] * (m - pm))
        break
    else:
        pm += item[1]
        s += item[0] * item[1]