Harryxun/stf_run huggingface dataset:
import math 
import bisect
import heapq
from collections import deque

h,w = map(int,input().split())
s = [map(int,input().split()) for _ in range(h)]
v = [ [0] * w ] * h

def bfs(i,j,s,v,count):

    if s[i][j] == '#': return 0
    else:
        v[i][j] = 1
        if i+1 < h and j+1 < w :
            if v[i+1][j+1] != 1 and s[i+1][j+1] == '.':
                count += 1
                bfs(i+1,j+1,s,v,count)

        elif i+1 < h and j-1 > 0 :
            if v[i+1][j-1] != 1 and s[i+1][j-1] == '.':
                count += 1
     
                bfs(i+1,j-1,s,v,count)

        elif i-1 < h and j+1 > 0 :
            if v[i-1][j+1] != 1 and s[i-1][j+1] == '.':
                count += 1
       
                bfs(i-1,j+1,s,v,count)

        elif i-1 < h and j-1 > 0 :
            if v[i+1][j-1] != 1 and s[i-1][j-1] == '.':
                count += 1
               
                bfs(i-1,j-1,s,v,count)

        else :return count

ans = 1000000
for i in range(h):
    for j in range(w):
        x,y = i,j
        ans = min(ans,bfs(i,j,s,v))
        

### FIXED CODE ###

import math 
import bisect
import heapq
from collections import deque

h,w=map(int,input().split())
M=[]
M=[input() for _ in range(h)]
 
def bfs(x,y):
    dist=[[-1]*w  for _ in range(h)]
    seen=[[False]*w for _ in range(h)]
    stk=[(x,y,0)]
    while stk:
        px,py,dst=stk.pop(0)
        if seen[px][py]:
            continue
        seen[px][py]=True
        
        if M[px][py]=='#':
            dist[px][py]=0
            continue
        
        for x,y in [(-1,0),(1,0),(0,-1),(0,1)]:
            if px+x<0 or px+x>=h or py+y<0 or py+y>=w:
                continue
            else:
                stk.append((px+x,py+y,dst+1))
        dist[px][py]=dst
    ans=0
 
    for i in range(h):
        ans=max(max(dist[i]),ans)
    return ans
ans = 0
for i in range(h):
    for j in range(w):
        if M[i][j]=='#':
            continue
        ans=max(bfs(i,j),ans)
print(ans)
def LCS():
    X = raw_input()
    Y = raw_input()
 
    a, b = len(X), len(Y)
    c1 = [0 for i in range(b+1)]
    for i in range(a):
        c2 = c1+[]
        for j in range(b):
            if X[i] == Y[j]:
                x1[j+1] = x2[j] + 1
            elif x1[j+1] < x1[j]:
                x1[j+1] = x1[j]
    return c1[-1]
 
n = input()
for i in range(n):
    print LCS()

### FIXED CODE ###

def LCS():
    X = raw_input()
    Y = raw_input()
 
    a, b = len(X), len(Y)
    c1 = [0 for i in range(b+1)]
    for i in range(a):
        e1 = X[i]
        c2 = c1+[]
        for j in range(b):
            if e1 == Y[j]:
                c1[j+1] = c2[j] + 1
            elif c1[j+1] < c1[j]:
                c1[j+1] = c1[j]
    return c1[-1]
 
n = input()
for i in range(n):
    print LCS()
(n,l)=map(int, input().split())
list1=[]
for i in range(n):
	list1.extend(input().split())
list1.sort()
for i in range(n):
	print(list1[i],end="")

### FIXED CODE ###

[a,b,c]=map(int, input().split())
list1=[a,b,c]
list1.sort()
if list1==[5,5,7]:
	print("YES")
else:print("NO")
import sys
n = int(input())
s = input()
a = int(len(s)/2)

if(len(a)%2 == 1):
  print("No")
  sys.exit()

for i in range(a):
  if(s[i] != s[i + a]):
    print("No")
    sys.exit()
    
print("Yes")
    
    


### FIXED CODE ###

import sys
n = int(input())
s = input()
d = int(n/2)
if(len(s)%2 == 1):
    print("No")
    sys.exit()
else:
    for i in range(d):
        if(s[i] != s[i + d]):
            print("No")
            sys.exit()

print("Yes")
import math 
n=input()
def d(n):
    return math.pi*2*n
  
print(d(n))

### FIXED CODE ###

import math
n=int(input())
def func(n):
    return math.pi*n*2
print(func(n))
import itertools
kai,av=[int(x) for x in input().rstrip().split()]
l=[int(x) for x in input().rstrip().split()]
ll=[i for i in range(1,kai+1)]
result=[]
count=0
 
 
for i in ll:
    for j in itertools.combinations(l,r=i):
        if av==(sum(j)/i):
            count+=1
print(count)

### FIXED CODE ###

a=int(input())
b=int(input())
c=int(input())
d=int(input())
ans=0
for i in range(a):
    if 0<b:
        ans+=c
    else:
        ans+=d
    b=b-1
print(ans)
#!/usr/bin/env python3

import math

n = int(input())

result = [0] * (n + 1)
border = int(math.sqrt(n - 2))
for x in range(1, border):
    for y in range(1, border):
        for z in range(1, border):
            r = ((x + y) ** 2 + (y + z) ** 2 + (z + x) ** 2) // 2
            if r > n:
                break
            else:
                result[r] += 1

for num in result[1::]:
    print(num)

### FIXED CODE ###

#!/usr/bin/env python3

import math

n = int(input())

result = [0] * (n + 1)
border = 0
if n>=3:
    border = int(math.sqrt(n - 2))
for x in range(1, border):
    for y in range(1, border):
        for z in range(1, border):
            r = ((x + y) ** 2 + (y + z) ** 2 + (z + x) ** 2) // 2
            if r > n:
                break
            else:
                result[r] += 1

for num in result[1::]:
    print(num)
n, m = map(int, input().split())
L = [[] for i in range(n)]
for i in range(m):
    a, b = map(int, input().split())
    A = a - 1
    B = b - 1
    L[A].append(B)
    L[B].append(A)
BFS = list()
BFS.append([0])
ans = [[] for i in range(n - 1)]
while [] in ans:
    BFS.append([])
    for i in BFS[-2]:
        for j in L[i]:
            BFS[-1].append(j)
            ans[j - 1].append(i + 1)
            L[j].remove(i)
for k in range(len(ans)):
    print(ans[k][0])


### FIXED CODE ###

from collections import deque
n, m = map(int, input().split())
bridge = [[] for i in range(n)]
for i in range(m):
    a, b = map(int, input().split())
    bridge[a - 1].append(b - 1)
    bridge[b - 1].append(a - 1)
queue = deque([0])
ans = [[] for i in range(n)]
ans[0].append('god')
while queue:
    now = queue.popleft()
    for factor in bridge[now]:
        if not (ans[factor]):
            ans[factor].append(now)
            queue.append(factor)
print('Yes')
for i in range(1, len(ans)):
    print(ans[i][0]+1)
import sys
N=int(input())
slist=[x=="o" for x in input()]
#print(slist)

answer_list=[0]*(N+1)

if N==3:
  if slist.count(True)==3:
    print("SSS")
  elif slist.count(False)==3:
    print("WWW")
  else:
    print(-1)
  sys.exit(0)

ok=False
for p1,p2 in [(1,1),(1,-1),(-1,1),(-1,-1)]:
  answer_list[1]=p1
  answer_list[2]=p2
  if slist[1]:
    answer_list[3]=answer_list[1]
  else:
    answer_list[3]=-answer_list[1]
  for i in range(3,N+1):
    l=i-1
    r=i%N+1
    si=slist[i-1]

    if answer_list[i]==1:
      if si:
        if answer_list[l]==1:
          answer_list[r]=1
        else:
          answer_list[r]=-1
      else:
        if answer_list[l]==1:
          answer_list[r]=-1
        else:
          answer_list[r]=1
    elif answer_list[i]==-1:
      if si:
        if answer_list[l]==1:
          answer_list[r]=-1
        else:
          answer_list[r]=1
      else:
        if answer_list[l]==-1:
          answer_list[r]=1
        else:
          answer_list[r]=-1
    
  contra=False
  if slist[0]:
    if answer_list[1]==1 and answer_list[2]!=answer_list[N]:
      contra=True
    if answer_list[1]==-1 and answer_list[2]==answer_list[N]:
      contra=True
  elif not slist[0]:
    if anser_list[1]==1 and answer_list[2]==answer_list[N]:
      contra=True
    if anser_list[1]==-1 and answer_list[2]!=answer_list[N]:
      contra=True

  if not contra:
    ok=True
    break
      
if ok:
  #print(answer_list[1:])
  sw_list=[]
  for i in range(1,N+1):
    if answer_list[i]==1:
      sw_list.append("S")
    else:
      sw_list.append("W")
  print("".join(sw_list))  
else:
  print(-1)

### FIXED CODE ###

N=int(input())
slist=[x=="o" for x in input()]
#print(slist)

answer_list=[0]*N

ok=False
for p1,p2 in [(1,1),(1,-1),(-1,1),(-1,-1)]:
  answer_list[0]=p1
  answer_list[1]=p2
  
  for i in range(2,N):
    if answer_list[i-1]==1:
      if slist[i-1]:
        answer_list[i]=answer_list[i-2]
      else:
        answer_list[i]=-answer_list[i-2]
    else:
      if slist[i-1]:
        answer_list[i]=-answer_list[i-2]
      else:
        answer_list[i]=answer_list[i-2]
        
  contra=False
  for i in range(N):
    l=(i-1)%N
    r=(i+1)%N
    if answer_list[i]==1:
      if slist[i]:
        if answer_list[l]!=answer_list[r]:
          contra=True
      else:
        if answer_list[l]==answer_list[r]:
          contra=True
    else:
      if slist[i]:
        if answer_list[l]==answer_list[r]:          
          contra=True
      else:
        if answer_list[l]!=answer_list[r]:
          contra=True

  if not contra:
    ok=True
    break
    
if ok:
  sw_list=[]
  for ans in answer_list:
    if ans==1:
      sw_list.append("S")
    else:
      sw_list.append("W")
  print("".join(sw_list))
else:
  print(-1)
s = str(input())

a = 0
z = 0

for i in range(len(s)):
    if s[i] = "A":
        a = min(a,i)

    elif s[i]  = "Z":
        z = max(z,i)

print(z - a + 1)

### FIXED CODE ###

s = str(input())

a = 199999
z = 0

for i in range(len(s)):
    if s[i] == "A":
        a = min(a,i)

    elif s[i]  == "Z":
        z = max(z,i)

print(z - a + 1)
import sympy
a, b, c = map(int, input().split())

if sympy.sqrt(a) + sympy.sqrt(b) >= sympy.sqrt(c):
    print("No")
else:
    print("Yes")

### FIXED CODE ###

from decimal import Decimal

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

a = Decimal(a)
b = Decimal(b)
c = Decimal(c)

if a.sqrt() + b.sqrt() < c.sqrt():
    print("Yes")
else:
    print("No")
if A != 0 and B == 0:
  C = math.factorial(A-2)
  E = math.factorial(A) // 2// C
  print(E)
  exit()
if A == 0 and B == 0:
  print(0)
  exit()
elif A == 1 and B != 1:
  D = math.factorial(B-2)
  F = math.factorial(B) // 2// D
  print(F)
  exit()
elif A != 1 and B == 1:
  C = math.factorial(A-2)
  E = math.factorial(A) // 2// C
  print(E)
  exit()
elif A == 1 and B == 1:
  print(0)
  exit()
C = math.factorial(A-2)
D = math.factorial(B-2)
E = math.factorial(A) // 2// C
F = math.factorial(B) // 2// D
print(E+F)

### FIXED CODE ###

A,B = list(map(int,input().split()))
import math
if A == 0 and B != 0:
  D = math.factorial(B-2)
  F = math.factorial(B) // 2// D
  print(F)
  exit()
if A != 0 and B == 0:
  C = math.factorial(A-2)
  E = math.factorial(A) // 2// C
  print(E)
  exit()
if A == 0 and B == 0:
  print(0)
  exit()
elif A == 1 and B != 1:
  D = math.factorial(B-2)
  F = math.factorial(B) // 2// D
  print(F)
  exit()
elif A != 1 and B == 1:
  C = math.factorial(A-2)
  E = math.factorial(A) // 2// C
  print(E)
  exit()
elif A == 1 and B == 1:
  print(0)
  exit()
C = math.factorial(A-2)
D = math.factorial(B-2)
E = math.factorial(A) // 2// C
F = math.factorial(B) // 2// D
print(E+F)
import networkx as nx

N, M = [int(x) for x in input().split()]
edges = [[int(x) for x in input().split()] for i in range(M)]

graph = nx.DiGraph(edges)

if True:
    import matplotlib.pyplot as plt

    nx.draw_networkx(graph)
    plt.show()

SCC = list(
    nx.algorithms.components.strongly_connected_components(graph)
)
print(len(SCC))
for comp in reversed(SCC):
    print(len(comp), *comp)


### FIXED CODE ###

import io
import os


input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
N, M = [int(x) for x in input().split()]
edges = [[int(x) for x in input().split()] for i in range(M)]

from collections import defaultdict

graph = defaultdict(list)
for u, v in edges:
    graph[u].append(v)
    graph[v]

# https://atcoder.jp/contests/practice2/submissions/16566401
def scc(G):
    preorder = {}
    lowlink = {}
    seen = [False] * N
    scc_queue = []
    i = 0  # Preorder counter
    ans = []
    for source in range(N):
        if seen[source]:
            continue
        queue = [source]
        while queue:
            v = queue[-1]
            if v not in preorder:
                i = i + 1
                preorder[v] = i
            done = True
            for w in G[v]:
                if w not in preorder:
                    queue.append(w)
                    done = False
                    break
            if done:
                lowlink[v] = preorder[v]
                for w in G[v]:
                    if seen[w]:
                        continue
                    if preorder[w] > preorder[v]:
                        lowlink[v] = min([lowlink[v], lowlink[w]])
                    else:
                        lowlink[v] = min([lowlink[v], preorder[w]])
                queue.pop()
                if lowlink[v] == preorder[v]:
                    scc = {v}
                    seen[v] = True
                    while scc_queue and preorder[scc_queue[-1]] > preorder[v]:
                        k = scc_queue.pop()
                        scc.add(k)
                        seen[k] = True
                    ans.append(scc)
                else:
                    scc_queue.append(v)
    return ans


SCC = list(scc(graph))

DEBUG = False
print(len(SCC))
if DEBUG:
    seen = set()
for comp in reversed(SCC):
    print(len(comp), *comp)
    if DEBUG:
        for u in comp:
            for v in graph[u]:
                assert v not in seen
        seen.update(comp)
import math
import sys
from operator import itemgetter

# N, K = map(int, input().split())
# h = list(map(int, input().split()))
# S = [input() for _ in range(H)]
# X = [[0 for j in range(100)] for i in range(200)]


### input
N = int(input())
a = [0]*100001
b = [0]*100001
c = [0]*100001

for i in range(N):
	a[i], b[i], c[i] = map(int, input().split())


### solve
hpns = [[0 for j in range(101)] for i in range(3)]

for i in range(1, N+1):
	hpns[0][i] = max(hpns[1][i-1], hpns[2][i-1]) + a[i-1]
	hpns[1][i] = max(hpns[2][i-1], hpns[0][i-1]) + b[i-1]
	hpns[2][i] = max(hpns[0][i-1], hpns[1][i-1]) + c[i-1]
	
print(max(hpns[0][N], hpns[1][N], hpns[2][N]))

### FIXED CODE ###

import math
import sys
from operator import itemgetter

# N, K = map(int, input().split())
# h = list(map(int, input().split()))
# S = [input() for _ in range(H)]
# X = [[0 for j in range(100)] for i in range(200)]


### input
N = int(input())
a = [0]*100001
b = [0]*100001
c = [0]*100001

for i in range(N):
	a[i], b[i], c[i] = map(int, input().split())


### solve
hpns = [[0 for j in range(100001)] for i in range(3)]

for i in range(1, N+1):
	hpns[0][i] = max(hpns[1][i-1], hpns[2][i-1]) + a[i-1]
	hpns[1][i] = max(hpns[2][i-1], hpns[0][i-1]) + b[i-1]
	hpns[2][i] = max(hpns[0][i-1], hpns[1][i-1]) + c[i-1]
	
print(max(hpns[0][N], hpns[1][N], hpns[2][N]))
n=input()
sum=1
f=0
f2=0
for i in range(1,n):
	a=input()
	if (a==0): 
		f2=1
	sum*=a
	if (sum>1000000000000000000):
		f=1;
}
if(f2==1): 
	print("0\n")
else if(f==1):
	print("-1\n")
else:
	print(sum)
	print("\n")

### FIXED CODE ###

N=int(input())
 
A=list(map(int,input().split()))
 
if 0 in A:
    print(0)
else:
    result=1
    for a in A:
        result=result*a
        if result>10**18:
            result=-1
            break
    print(result)
if n == 1:
    print(1)
    exit()
mod = 10 ** 9 + 7
now = n
big = []
for i in range(2,int(math.sqrt(n)+2)):
    d = n // i
    big.append(now - d)
    now = d
big.reverse()
l = [1] * d + big
l2 = [1] * d + big
for i in range(k-1):
    a = cumsum(l)
    a.reverse()
    count = 0
    for i,j in zip(a,l2):
        l[count] = (i * j) % mod
        count += 1
l = cumsum(l)
ans = l[-1] % mod
print(ans)

### FIXED CODE ###

import math

from itertools import accumulate

def cumsum(a):
    return list(accumulate(a))

n,k = map(int, input().split())
if n == 1:
    print(1)
    exit()
mod = 10 ** 9 + 7
now = n
big = []
for i in range(2,int(math.sqrt(n)+2)):
    d = n // i
    big.append(now - d)
    now = d
big.reverse()
l = [1] * d + big
l2 = [1] * d + big
for i in range(k-1):
    a = cumsum(l)
    a.reverse()
    count = 0
    for i,j in zip(a,l2):
        l[count] = (i * j) % mod
        count += 1
l = cumsum(l)
ans = l[-1] % mod
print(ans)
#整数a,bを入力
a,b = (int, input().split())
#計算
result = a * b
#判定
if result % 2 = 0:
  print("Even")
else
  print("Odd")

### FIXED CODE ###

a,b = map(int, input().split())
print("Even" if (a*b)%2==0 else "Odd")
n=int(input())

s = ''
for i in range(11):
  if N != 0:
    n -= 1
    s += chr(ord('a') + N % 26)
    n //= 26
print(s[::-1])

### FIXED CODE ###

n=int(input())

s = ''
for i in range(11):
  if n != 0:
    n -= 1
    s += chr(ord('a') + n % 26)
    n //= 26
print(s[::-1])
from operator import itemgetter

A, B, C, D, E, F = list(map(int,input().split()))
X = []

for a in range(31):
    for b in range(31):
        for c in range(71)       #範囲の指定がよくわからない
            for d in range(71):  #範囲の指定がよくわからない
                w = 100*A*a+100*B*b #水の質量
                s = C*c+D*d        #砂糖の質量
                if w == 0  or w + s >= F: #ダメな条件 砂糖０はあり得る
                    break
                else:
                    if s/(w+s) <= E/(100 + E):
                        ans = 100 * s/(w+s)
                        X.append([ans,w + s, s])
X = sorted(X,key=itemgetter(0),reverse = True) 
#print(X)
print(X[0][1],X[0][2])

### FIXED CODE ###

from operator import itemgetter

A, B, C, D, E, F = list(map(int,input().split()))
X = []
ans = 1000
for i in range(31):
    for j in range(31):
        for k in range(51):
            for l in range(51):
                if 100*A*i+100*B*j+C*k+D*l != 0:
                    if 100*A*i+100*B*j+C*k+D*l <= F and (C*k+D*l)/(100*A*i+100*B*j+C*k+D*l) <= E/(100 + E):
                        ans =(E/(100 + E) - (C*k+D*l)/(100*A*i+100*B*j+C*k+D*l))
                        X.append([ans , 100*A*i+100*B*j+C*k+D*l, C*k+D*l])
X = sorted(X,key=itemgetter(0),reverse = False) 

print(X[0][1],X[0][2])
N, M = map(int, input().split())
*X, = map(int, input().split())
E = []
for i in range(M):
    a, b, y = map(int, input().split())
    E.append((y, a-1, b-1))
E.sort()

*p, = range(N)
Y = [0]*N; Z = [0]*M
A = X[:]
B = [0]*M
C = [-1]*N
def root(x):
    if x == p[x]:
        return x
    p[x] = y = root(p[x])
    return y

def unite(x, y):
    px = root(x); py = root(y)
    if px == py:
        return 0
    if px < py:
        p[py] = px
        A[px] += A[py]
    else:
        p[px] = py
        A[py] += A[px]
    return 1

G = [None for i in range(M)]

ans = 0
for i, (y, a, b) in enumerate(E):
    pa = root(a); pb = root(b)
    ca = C[pa]; cb = C[pb]
    if unite(a, b):
        pa = root(a)
        Z[i] = 1
        B[i] = A[pa]
        C[pa] = i
        #print(">", i, pa, pb, A[pa], y)
        if A[pa] < y:
            G[i] = []
            if ca != -1:
                G[i].append(ca)
            if cb != -1:
                G[i].append(cb)
    else:
        if A[pa] < y:
            G[i] = []
            if ca != -1:
                G[i].append(ca)
            C[pa] = i

sx = sum(X)
#print(Z)

from collections import deque
que = deque()
if sx < E[C[0]][0]:
    que.append(C[0])
#print(G, C)
while que:
    v = que.popleft()
    #print(v)
    if G[v] is not None:
        ans += 1
        for w in G[v]:
            que.append(w)
print(ans)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)

N, M = map(int, input().split())
*X, = map(int, input().split())
E = []
for i in range(M):
    a, b, y = map(int, input().split())
    E.append((y, a-1, b-1))
E.sort()

*p, = range(N)
Z = [0]*M
A = X[:]
C = [-1]*N
def root(x):
    if x == p[x]:
        return x
    p[x] = y = root(p[x])
    return y

def unite(x, y):
    px = root(x); py = root(y)
    if px == py:
        return 0
    if px < py:
        p[py] = px
        A[px] += A[py]
    else:
        p[px] = py
        A[py] += A[px]
    return 1

G = [None for i in range(M)]

ans = 0
for i, (y, a, b) in enumerate(E):
    pa = root(a); pb = root(b)
    ca = C[pa]; cb = C[pb]
    if unite(a, b):
        pa = root(a)
        Z[i] = 1
        C[pa] = i
        #print(">", i, pa, pb, A[pa], y)
        if A[pa] < y:
            G[i] = []
            if ca != -1:
                G[i].append(ca)
            if cb != -1:
                G[i].append(cb)
    else:
        if A[pa] < y:
            G[i] = []
            if ca != -1:
                G[i].append(ca)
            C[pa] = i

sx = sum(X)
#print(Z)

if N > 1:
    from collections import deque
    que = deque()
    if sx < E[C[0]][0]:
        que.append(C[0])
    #print(G, C)
    while que:
        v = que.popleft()
        #print(v)
        if G[v] is not None:
            ans += 1
            for w in G[v]:
                que.append(w)
print(ans)
class UnionFind:
	def __init__(self, n):
		self.groups = [g for g in range(n)]

	def get_root(self, i):
		parent = self.groups[i]
		if parent == i:
			return parent
		else:
			root = self.get_root(parent)
			self.groups[i] = root
			return root
	
	def set_root(self, i, root):
		parent = self.groups[i]
		self.groups[i] = root
		if parent == i:
			return
		else:
			self.set_root(parent, root)
	
	def combine(self, i1, i2):
		self.set_root(i2, self.get_root(i1))
	
	def in_same_group(self, i1, i2):
		return self.get_root(i1) == self.get_root(i2)
	
	def to_dic(self):
		table = {}
		for i in range(len(self.groups)):
			g = self.get_root(i)
			if g in table:
				table[g].append(i)
			else:
				table[g] = [i]
		return table
	
	def to_list(self):
		table = self.to_dic()
		return [table[g] for g in table]





N, M = map(int, input().split())
ab_list = []
for i in range(N):
	a, b = map(int, input().split())
	ab_list.append((b, a))
ab_list.sort()
ab_list.reverse()

index_list = UnionFind(N)
used_list = [False] * M

reward = 0
for b, a in ab_list:
	index = M - a
	prev_index = None
	while index >= 0:
#		print(index, M, a, N)
		if not used_list[index]:
			used_list[index] = True
			reward += b
			break
		if prev_index != None:
			index_list.combine(index, prev_index)
		prev_index = index
		index = index_list.get_root(index) - 1

print(reward)


### FIXED CODE ###

class UnionFind:
	def __init__(self, n):
		self.groups = [g for g in range(n)]

	def get_root(self, i):
		parent = self.groups[i]
		if parent == i:
			return parent
		else:
			root = self.get_root(parent)
			self.groups[i] = root
			return root
	
	def set_root(self, i, root):
		parent = self.groups[i]
		self.groups[i] = root
		if parent == i:
			return
		else:
			self.set_root(parent, root)
	
	def combine(self, i1, i2):
		self.set_root(i2, self.get_root(i1))
	
	def in_same_group(self, i1, i2):
		return self.get_root(i1) == self.get_root(i2)
	
	def to_dic(self):
		table = {}
		for i in range(len(self.groups)):
			g = self.get_root(i)
			if g in table:
				table[g].append(i)
			else:
				table[g] = [i]
		return table
	
	def to_list(self):
		table = self.to_dic()
		return [table[g] for g in table]





N, M = map(int, input().split())
ab_list = []
for i in range(N):
	a, b = map(int, input().split())
	ab_list.append((b, a))
ab_list.sort()
ab_list.reverse()

index_list = UnionFind(M)
used_list = [False] * M

reward = 0
for b, a in ab_list:
	index = M - a
	prev_index = None
	while index >= 0:
#		print(index, M, a, N)
		if not used_list[index]:
			used_list[index] = True
			reward += b
			break
		if prev_index != None:
			index_list.combine(index, prev_index)
		prev_index = index
		index = index_list.get_root(index) - 1

print(reward)
inf = pow(10, 9)+7

def nCr(n, r):
    r = min(r, n - r)
    if r == 0: return 1;
    if r == 1: return n;
    numerator = [n - r + i + 1 for i in range(r)]
    denominator  = [i + 1 for i in range(r)]
    for p in range(2, r + 1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p - 1, r, p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot
    result = 1
    for k in range(r):
        if numerator[k] > 1: 
            result *= numerator[k]
    return result


n, k = map(int, input().split())
a = [int(x) for x in input().split()]
a.sort()

ans = 0
key = (nCr(n-1, k-1))
for i in range(n-k+1):
    ans += ((a[-i-1] - a[i])%inf)*(key%inf)
    ans %= inf
    key = key*(n-k-i)//(n-1-i)
print(int(ans))

### FIXED CODE ###

inf = pow(10, 9)+7

n, k = map(int, input().split())
a = [int(x) for x in input().split()]
a.sort()

ans = 0
comb = 1
for i in range(k, n+1):
    ans += (a[i-1]-a[-i])*comb
    ans %= inf
    comb = (comb * i * pow(i-k+1, inf-2, inf))%inf
print(ans)