Harryxun/stf_run huggingface dataset:
n,m,c = map(int,input().split())
b = list(map(int,input().split()))
ans = 0
for i in range(n):
    a = list(map(int,input().split()))
    num = 0
    for j in range(m):
        num += a[j]*b[j]
    num += C
    if num > 0:
        ans += 1
print(ans)

### FIXED CODE ###

n,m,c = map(int,input().split())
b = list(map(int,input().split()))
cnt = 0
for i in range(n):
    sum = 0
    a = list(map(int,input().split()))
    for j in range(m):
        sum += a[j]*b[j]
    if sum + c > 0:
        cnt += 1
print(cnt)
a = list(map(int,input().split()))
N = a[0]
M = a[1]
dct = {}
for i in range(N):
    temp = list(map(int,input().split()))
    if temp[0] in dct:
        val = dct[temp[0]] + temp[1]
        dct[temp[0]] = val
    else:
        dct[temp[0]] = temp[1]

dct = sorted(dct.items())
ruiseki = 0
loop = 0

cost = []
nums = []
ans = 0
for i in range(N):
    cost.append(dct[i][0])
    nums.append(dct[i][1])
if nums[0] >= M:
    print(str(cost[0]*M))
else:
    ans += cost[0]*nums[0]
    for i in range(1, 100001):
        nums[i] += nums[i-1]
        if nums[i] >= M:
            print(str(ans + cost[i]*(M - nums[i-1])))
            break
        ans += cost[i]*(nums[i]-nums[i-1])


### FIXED CODE ###

a = list(map(int,input().split()))
N = a[0]
M = a[1]
dct = {}
for i in range(N):
    temp = list(map(int,input().split()))
    if temp[0] in dct:
        val = dct[temp[0]] + temp[1]
        dct[temp[0]] = val
    else:
        dct[temp[0]] = temp[1]

dct = sorted(dct.items())
ruiseki = 0
loop = 0

cost = []
nums = []
ans = 0
lendct = len(dct)
for i in range(lendct):
    cost.append(dct[i][0])
    nums.append(dct[i][1])
if nums[0] >= M:
    print(str(cost[0]*M))
else:
    ans += cost[0]*nums[0]
    for i in range(1, 100001):
        nums[i] += nums[i-1]
        if nums[i] >= M:
            print(str(ans + cost[i]*(M - nums[i-1])))
            break
        ans += cost[i]*(nums[i]-nums[i-1])
A,B,K = map(int,input().split())
tmp = list(range(A,B+1))
small = tmp[:K]
big = tmp[-K:]
tmp = sorted(list(set(small + big)))
for i in tmp:
    print(i)

### FIXED CODE ###

A,B,K = map(int,input().split())
if A == B:
    print(A)
else:
    if K > B - A:
        K = B - A
    tmp1 = list(range(A,A+K))
    tmp2 = list(range(B-K+1,B+1))
    ans = sorted(list(set(tmp1 + tmp2)))
    for i in ans:
        print(i)
import sys

X, N = (int(x) for x in input().split())
if N != 0:
  p = [int(x) for x in input().split()]
else:
  print(X)
  sys.exit()
i = 0
ans = X
flag = False
while True:
  if X + i in p: continue
  ans = X + i
  flag = True
  if X - i in p: continue
  ans = X - i
  flag = True
  if flag: break
  i += 1
pritn(ans)

### FIXED CODE ###

def main():
    x, n = (int(x) for x in input().split())
    p = [int(x) for x in input().split()]

    if x not in p:
        print(x)
    else:
        for i in range(1, 200):
            if x - i not in p:
                print(x - i)
                break
            if x + i not in p:
                print(x + i)
                break

if __name__ == '__main__':
    main()
N, K = map(int, input().split())
H = sorted([int(input()) for _ in range(N)])

ans = 10**9
for i in range(N-K+1):
    diff = H[i+2] - H[i]
    if diff < ans:
        ans = diff
print(ans)

### FIXED CODE ###

N, K = map(int, input().split())
h = [int(input()) for _ in range(N)]
h = sorted(h)

m = []
for i in range(N-K+1):
    m.append(h[i+K-1] - h[i])
print(min(m))
import time
s=time.time()
while time.time()-s<39.99:pass
i=input;a,b,c,d,e=map(int,[i(),i(),i(),i(),i()])
print(c*-a+d+b*e)if a<0 else print((b-a)*e)

### FIXED CODE ###

import time
s=time.time()
while time.time()-s<39.9:pass
i=input
a,b,c,d,e=map(int,[i(),i(),i(),i(),i()])
if a<0:print(c*-a+d+b*e)
else:print((b-a)*e)
from fractions import gcd
a, b, c = map(int, raw_input().split())
print ['NO', 'YES'][c % gcd(a, b) ^ 1]


### FIXED CODE ###

from fractions import gcd
a, b, c = map(int, raw_input().split())
print ['NO', 'YES'][c % gcd(a, b) is 0]
s_list = list(input())
s_list1 = s_list

if s_list[0] == "A":
    del s_list[:2], s_list[-1]
    Str = "".join(s_list)
    if Str.count("C") != 1:
        print("WA")
    else:
        Str = "".join(s_list1)
        Str = Str.replace("C", "")
        if Str1.islower():
            print("AC")
        else:
            print("WA")
else:
    print("WA")

### FIXED CODE ###

s_list = list(input())
s_list1 = s_list[1:]
count = 0

if s_list[0] == "A":
    del s_list[:2], s_list[-1]
    for i in range(len(s_list)):
        if s_list[i] == "C":
            count += 1
            isC = i + 1
    if count != 1:
        print("WA")
    else:
        del s_list1[isC]
        Str = "".join(s_list1)
        if Str.islower():
            print("AC")
        else:
            print("WA")
else:
    print("WA")
N, P = map(int, input().split())
b=0
a = int(pow(P, 1/N))
for i in range(1, a+1):
  if P % pow(a+1-i,N) == 0:
     b = a+1-i
     break
print(b)

### FIXED CODE ###

N = str(input())
count = 0

for i in N:
  if i=="2":
     count += 1

print(count)
X,Y,Z=map(int,input().split())
print(Y Z X)

### FIXED CODE ###

X,Y,Z=map(int,input().split())
print(Z ,X, Y)
N = int(input())
for i in range(1,1+int(N)):
    if N % i == 0:
        tmp = i
s = max(len(str(N // tmp)),len(str(tmp)))
ans = min(ans,s)

### FIXED CODE ###

N = int(input())
for i in range(1,1+int(N**(1/2))):
    if N % i == 0:
        tmp = i
print(max(len(str(N // tmp)),len(str(tmp))))
# B - Bounding

N, X = map(int, input().split())
L = [int(l) for l in input().split()]
D = 0
cnt = 0
for i in range(N + 1):
    if D <= X:
        cnt += 1
    D = D + L[i]

print(cnt)


### FIXED CODE ###

# B - Bounding

N, X = map(int, input().split())
L = [int(l) for l in input().split()]
D = 0
cnt = 1
for i in range(N):
    D = D + L[i]
    if D <= X:
        cnt += 1

print(cnt)
n,i=map(int,input().split())
print(n-p+1)

### FIXED CODE ###

n,i=map(int,input().split())
print(n-i+1)
n = int(input())
A = list(map(int, input().split()))
A.sort()
hst = [0] * (max(A) + 1)
for a in A:
    hst[a] += 1

rec = []
squ = []
A_ = list(set(A))
for a in A_:
    if hst[a] > 1:
        rec.append(a)
    if hst[a] >= 4:
        squ.append(a)

# print(rec)
# print(squ)

s = 0
if len(squ) != 0:
    s = squ[-1]**2

if len(rec) < 2:
    print(s)
else:
    print(max(s, rec[-1]*rec[-2]))

### FIXED CODE ###

from collections import Counter
n = int(input())
A = list(map(int, input().split()))

C = Counter(A)

rec = []
squ = []

for a in A:
    if 2 <= C[a]:
        rec.append(a)
    if 4 <= C[a]:
        squ.append(a)
rec = list(set(rec))
squ = list(set(squ))
# print(rec)
# print(squ)

s = 0
if len(squ) != 0:
    s = max(squ)**2

if len(rec) < 2:
    print(s)
else:
    rec.sort(reverse=True)
    print(max(s, rec[0]*rec[1]))
import math
a, b, c = map(int, raw_input().split())
c = c / 180.0 * math.pi

s = 0.5 * a * b * math.sin(c))
l = a + b + math.sqrt(a ** 2 + b ** 2 - 2 * a * b * math.sin(c))
h = b * math.sin(c)

print "%f" % s
print "%f" % l
print "%f" % h

### FIXED CODE ###

import math
a, b, c = map(float, raw_input().split())
c = (c * math.pi) / 180.0

print "%f" %(a * b * math.sin(c) / 2.0)
print "%f" %(a + b + math.sqrt(a ** 2 + b ** 2 - 2 * a * b * math.cos(c)))
print "%f" %((b * math.sin(c)))
class Dice():
	def __init__(self, label):
		self.d = label
	
	def roll(self, drt):
		if drt == 'N':
			self.d[1], self.d[2], self.d[6], self.d[5] = self.d[2], self.d[6], self.d[5], self.d[1]
		elif drt == 'E':
			self.d[1], self.d[3], self.d[6], self.d[4] = self.d[4], self.d[1], self.d[3], self.d[6]
		elif drt == 'S':
			self.d[2], self.d[6], self.d[5], self.d[1] = self.d[1], self.d[2], self.d[6], self.d[5]
		elif drt == 'W':
			self.d[4], self.d[1], self.d[3], self.d[6] = self.d[1], self.d[3], self.d[6], self.d[4]
	
	def printl(self, lct):
		print(self.d[lct])
	
	def rot(self, drc):
		self.roll('N')
		if drc == 'r':
			self.roll('E')
		elif drc == 'l':
			self.roll('W')
		self.roll('S')
		
label = [0]	
label.extend(list(map(int, input().split())))
dice1 = Dice(label)
q = int(input())

ST = 'NNNNEEE'
SF = 'rrr'

for i in range(q):
	s = list(map(int, input().split()))
	for j in range(7):
		if dice1.d[1] == s[0]:
			break
		dice1.roll(ST[j])
	for k in range(3):
		if dice1.d[2] == s[1]:
			break
		dice1.rot(SF[j])
	dice1.printl(3)

### FIXED CODE ###

class Dice():
	def __init__(self, label):
		self.d = label
	
	def roll(self, drt):
		if drt == 'N':
			self.d[1], self.d[2], self.d[6], self.d[5] = self.d[2], self.d[6], self.d[5], self.d[1]
		elif drt == 'E':
			self.d[1], self.d[3], self.d[6], self.d[4] = self.d[4], self.d[1], self.d[3], self.d[6]
		elif drt == 'S':
			self.d[2], self.d[6], self.d[5], self.d[1] = self.d[1], self.d[2], self.d[6], self.d[5]
		elif drt == 'W':
			self.d[4], self.d[1], self.d[3], self.d[6] = self.d[1], self.d[3], self.d[6], self.d[4]
	
	def printl(self, lct):
		print(self.d[lct])
	
	def rot(self, drc):
		self.roll('N')
		if drc == 'r':
			self.roll('E')
		elif drc == 'l':
			self.roll('W')
		self.roll('S')
		
label = [0]	
label.extend(list(map(int, input().split())))
dice1 = Dice(label)
q = int(input())

ST = 'NNNNEEE'
SF = 'rrr'

for i in range(q):
	s = list(map(int, input().split()))
	for j in range(7):
		if dice1.d[1] == s[0]:
			break
		dice1.roll(ST[j])
	for k in range(3):
		if dice1.d[2] == s[1]:
			break
		dice1.rot(SF[k])
	dice1.printl(3)
A = int(input())
B = int(input())

ans1 = A + B


if ans1 >= 24:
    ans2 = ans1 - 24
    print(ans2)
else:
    print(ans1)
    
    
    

### FIXED CODE ###

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

ans1 = A + B


if ans1 >= 24:
    ans2 = ans1 - 24
    print(ans2)
else:
    print(ans1)
N = input()
s = 0
 for i in range(0,2):
  if N[i] == "o":
    s = s + 1
print(700+100*s)    

### FIXED CODE ###

A = input()
B = A.count('o')
print(700+int(B)*100)
r=map(int,input())
a=3(rxr)


### FIXED CODE ###

r=int(input())
a=3*(r*r)
print(a)
input()
i=map(int,input().split())
print(f'{min(i)} {max(i)} {sum(i)}')

### FIXED CODE ###

input()
b=list(map(int,input().split()))
print(min(b),max(b),sum(b))
for i in range(1, 10):
    for j in range(1, 10):
        print str(i) + 'x' + str(j) + '=' + str(i * j)


### FIXED CODE ###

for i in range(1, 10):
    for j in range(1, 10):
        print str(i) + 'x' + str(j) + '=' + str(i * j)
N, K = map(int, input().split())
MOD = 10**9+7
cmb = [[1] if i == -1 else [1] + [0]*i + [1] for i in range(-1,N-1)]

for i in range(2, N):
    for j in range(1, i):
        cmb[i][j] = cmb[i-1][j-1] + cmb[i-1][j]

for i in range(1, K+1):
    print((cmb[N-K+1][i] * cmb[K-1][i-1]) % MOD)


### FIXED CODE ###

N, K = map(int, input().split())
MOD = 10**9+7
cmb = [[1] if i == -1 else [1] + [0]*i + [1] for i in range(-1,N)]

for i in range(2, N+1):
    for j in range(1, i):
        cmb[i][j] = cmb[i-1][j-1] + cmb[i-1][j]

for i in range(1, K+1):
    try:
        ans = cmb[N-K+1][i]
    except IndexError:
        ans = 0
    if ans:
        ans *= cmb[K-1][i-1]
    print(ans % MOD)
K = int(input())

if K <= 500:
    print(K)
    for i in range(K):
        print(*([i+1]*K))
elif K % 4 == 0:
    print(K // 2)
    for i in range(K // 2):
        print(*([i+1, i+1+K//2] * (K//4)))
else:
    print(1//0)
    


### FIXED CODE ###

K = int(input())
M = 1000

def a(i, j):
    tmp = (i - j) % (M//2) + 1
    if j % 2 == 0 or M + 1 - tmp > K:
        return tmp
    else:
        return M + 1 - tmp
    
if K <= M//2:
    print(K)
    for i in range(K):
        print(*([i+1]*K))
else:
    print(M//2)
    for j in range(M//2):
        print(*([a(i, j) for i in range(M//2)]))
H1,M1,H2,H2,K = map(int,input().split())
print((H2-H1)*60+(M2-M1)-K)

### FIXED CODE ###

H1,M1,H2,M2,K = map(int,input().split())
print((H2-H1)*60+(M2-M1)-K)
L,R,d = input(int(_) for _ in input().split())

for i in range(d):
  if(i%d == 0) cnt++;
  
print(cnt);

### FIXED CODE ###

L,R,d=map(int, input().split())
cnt=0
 
for i in range(L, R+1):
  if i%d == 0: cnt+=1
  
print(cnt)
S = ABC

if S == ABC:
 print('ARC')
else:
 print('ABC')

### FIXED CODE ###

s=input()
print("ABC" if s=="ARC" else "ARC")
# -*- coding: utf-8 -*-
while True:
    kazu = [int(x) for x in input()]
    if kazu == 0:
        break
    print('{}'.format(sum(kazu)))


### FIXED CODE ###

while True:
    kazu = [int(x) for x in input()]
    if kazu == [0]:
        break
    else:
        print('{}'.format(sum(kazu)))
s = input()
ww = ["Sunny", "Cloudy", "Rainy"]
for w in ww:
  if s == w[i]:
    if i == 2: j = 0
    else: j = i + 1
    print(w[j])
    break


### FIXED CODE ###

s = input()
w = ["Sunny", "Cloudy", "Rainy"]
for i in range(3):
  if s == w[i]:
    if i == 2: j = 0
    else: j = i + 1
    print(w[j])
    break
N = int(input())

graph = [[] for i in range(N)]

for i in range(N -1):
    a, b = map(int, input().split())
    graph[a-1].append((b, i))
    graph[b-1].append((a, i))

print(graph)
ans = [0] * (N -1)


def dfs(past, now, color):
    new_color = 1
    for future, edge in graph[now - 1]:
        if future == past:
            pass
        else:
            if new_color == color:
                new_color += 1
            ans[edge] = new_color
            dfs(now, future, new_color)
            new_color += 1

dfs(-1, 1, -1)

print(max(ans))
for i in ans:
    print(i)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**9)

N = int(input())

graph = [[] for i in range(N)]

for i in range(N - 1):
    a, b = map(int, input().split())
    graph[a - 1].append((b,i))
    graph[b - 1].append((a,i))

ans = [0] * (N - 1)


def dfs(past, now, color):
    new_color = 1
    for future, edge in graph[now - 1]:
        if future == past:
            pass
        else:
            if new_color == color:
                new_color += 1
            ans[edge] = new_color
            dfs(now, future, new_color)
            new_color += 1


dfs(-1, 1, -1)

print(max(ans))
for i in ans:
    print(i)
from numpy import*
n, m = map(int, input().split())
l = []
for i in range(m):
    *a,=map(int,input().split())
    l.append(a[1:])
*p,=map(int,input().split())
ans = 0
for t in range(2**n):
    for s in range(n):
        tmp = array([t >> s & 1])
    for i in l:
        if p == sum(tmp[array(i)-1])%2:
            ans += 1
print(ans)

### FIXED CODE ###

from numpy import*
n, m = map(int, input().split())
l = []
for i in range(m):
    *a,=map(int,input().split())
    l.append(a[1:])
*p,=map(int,input().split())
ans = 0
for t in range(2**n):
    tmp=array([t>>s&1 for s in range(n)])
    if p==[sum(tmp[array(i)-1])%2for i in l]:
        ans+=1
print(ans)
import heapq, math, sys

N, K = map(int, input().split())
A = sorted(list(map(int, input().split())), reverse=True)
maxA = A[0]
pre = -1
while len(A) != pre:
    if len(A) == 0:
        print(math.ceil(maxA))
        sys.exit()
    pre = len(A)
    meanA = math.ceil(sum(A)/(len(A)+K))
    for i, a in enumerate(A):
        if a <= meanA:
            A = A[:i]
            break


cuts = [0]*(i+1)
meanA = math.ceil(sum(A)/(len(A)+K))
for i, a in enumerate(A):
    cut_at_least = (a//meanA - 1)
    cuts[i] = cut_at_least
    K -= cut_at_least
hq = [(-a/(cut+1), i) for i, (a, cut) in enumerate(zip(A, cuts))]
heapq.heapify(hq)
lenhq = len(hq)
if K>N:
    raise ValueError
for k in range(K):
    l, i = heapq.heappop(hq)
    cuts[i] += 1
    heapq.heappush(hq, (-A[i]/(cuts[i]+1), i))
l, i = heapq.heappop(hq)
print(math.ceil(-l))


### FIXED CODE ###

import heapq, math, sys

N, K = map(int, input().split())
A = sorted(list(map(int, input().split())), reverse=True)
maxA = A[0]
pre = -1
while len(A) != pre:
    if len(A) == 0:
        print(math.ceil(maxA))
        sys.exit()
    pre = len(A)
    meanA = math.ceil(sum(A)/(len(A)+K))
    for i, a in enumerate(A):
        if a <= meanA:
            A = A[:i]
            break


cuts = [0]*(i+1)
meanA = (sum(A)/(len(A)+K))
for i, a in enumerate(A):
    cut_at_least = (math.floor(a/meanA) - 1)
    cuts[i] = cut_at_least
    K -= cut_at_least
hq = [(-a/(cut+1), i) for i, (a, cut) in enumerate(zip(A, cuts))]
heapq.heapify(hq)
lenhq = len(hq)
for k in range(K):
    l, i = heapq.heappop(hq)
    cuts[i] += 1
    if k <= N:
        heapq.heappush(hq, (-A[i]/(cuts[i]+1), i))
l, i = heapq.heappop(hq)
print(math.ceil(-l))
a,v = map(int,input().split())
b,w = map(int,input().split())
t = int(input())
first_distance = abs(b-a)
speed = v-w
t_position = first_distance - speed*t
if t_position <= 0:
  print("YES")
else:a
  print("NO")

### FIXED CODE ###

a,v = map(float,input().split())
b,w = map(float,input().split())
t = float(input())
first_distance = abs(b-a)
speed = v-w
t_position = first_distance - speed*t
if t_position <= 0:
  print("YES")
else:
  print("NO")
r = int(input())
a = 2 * pi * r
print(a)

### FIXED CODE ###

r = int(input())
a = 2 * 3.1415 * r
print(a)
while True:
  x, y = map(int, raw_input.split())
  if x == y == 0:
     break


  if x < y:
     print '%d %d' %(x, y)
  elif x > y :
     print '%d %d' %(y, x)
  elif x == y:
     print '%d %d' %(x, y)

 

### FIXED CODE ###




while 1:
  x, y = map(int, raw_input().split())
  if x == y == 0:
     break


  if x < y:
     print '%d %d' %(x, y)
  elif x > y :
     print '%d %d' %(y, x)
  elif x == y:
     print '%d %d' %(x, y)
import sys

N = float(input())
t = 3
prime_number = []
while t <= N / 15.0:
    l = []
    for i in range(t+1):
        if i != 0:
            if t % i == 0:
                l.append(i)
    if l == [1, t]:
        prime_number.append(t)
    t += 1
n = len(prime_number)
ans = 0
if n < 3:
    print(0)
    sys.exit()
else:
    for i in prime_number:
        for j in prime_number:
            if j != i:
                for k in prime_number:
                    if k != i and k != j:
                        if i * j * k <= N:
                            ans += 1
ans = ans / 6
if N >= 189:
    ans += 2
elif N >= 135:
    ans += 1
print(int(ans))

### FIXED CODE ###

a, b = [int(_) for _ in input().split()]
ans = (a - 1) * (b - 1)
print(ans)
N, K = map(int, input().split(' '))
x = list(map(int, input().split(' ')))

x_min = []
for i in range(N):
    if x[i] == 0:
        K -= 1
    if x[i] > 0:
        break

x_min = [0] + x[0:i][::-1]
x_plus = [0] + x[i:]
length_m = len(x_min)
length_p = len(x_plus)
# print(x_min, x_plus)
ans = 2*abs(x[0]) + abs(x[-1])

for i in range(length_m):
    if (length_p-1) + i < K:
        continue
    if (i+1) > K:
        break
    temp = 2 * abs(x_min[i]) + abs(x_plus[K-i])
#    print(temp)
    ans = min(ans, temp)

for i in range(length_p):
    if (length_m-1) + i < K:
        continue
    if (i+1) > K:
        break
    temp = 2 * abs(x_plus[i]) + abs(x_min[K-1])
#        print(temp)
    ans = min(ans, temp)

print(ans)


### FIXED CODE ###

N, K = map(int, input().split(' '))
x = list(map(int, input().split(' ')))
ans = abs(x[0]) + abs(x[0]-x[0+K-1])

for i in range(N-K+1):
    temp1 = abs(x[i]) + abs(x[i]-x[i+K-1])
    temp2 = abs(x[i+K-1]) + abs(x[i]-x[i+K-1])
    ans = min(ans, temp1, temp2)

print(ans)
# -*- coding: UTF-8 -*-
L, N = map(int, input().split())
a = list(input() for i in range(N))
a.sort()
b = "".join(a)
print(b)


### FIXED CODE ###

# -*- coding: UTF-8 -*-
N, L = map(int, input().split())
a = [input() for i in range(N)]
a.sort()
b = "".join(a)
print(b)
# import collections

print('input >>')
N, K, Q = map(int, (input().split()))
points = [K] * N
A = []
for _ in range(Q):
    A.append(int(input()))

Acount = collections.Counter(A)

for answerer, times in Acount.items():
    points = [p - times for p in points]
    points[answerer - 1] += times

# print('----------output----------')

for answerer in range(N):
    print('Yes') if points[answerer] > 0 else print('No')

### FIXED CODE ###

import collections

# print('input >>')
N, K, Q = map(int, (input().split()))
points = [K] * N
A = []
for _ in range(Q):
    A.append(int(input()))

Acount = collections.Counter(A)

for answerer, times in Acount.items():
    points[answerer - 1] += times

# print('----------output----------')

for answerer in range(N):
    print('Yes') if points[answerer] > Q else print('No')
a,b=map(int,input().split())
print("Even",if a*b%2=21 else "Odd" )

### FIXED CODE ###

a,b=map(int, input().split())
print("Even" if a*b%2==0 else "Odd")
N,M = map(int,input().split())
A = list(map(int,input().split()))
A.sort()
B = [0 for i in range(10**5+1)]
S = [0]
s = 0
for i in range(N):
    B[A[i]] += 1
    s += A[i]
    S.append(s)
for i in range(2,10**5+2):
    B[-i] += B[-i+1]
d = 0
u = 2*10**5
for i in range(30):
    x = (u+d)//2
    m = 0
    for i in range(N):
        a = A[i]
        y = max(x - a,0)
        if y <= 10**5:
            m += B[y]
    if m >= M:
        d = x
    else:
        u = x
ans = 0
for i in range(N):
    a = A[i]
    x = max(d - a,0)
    y = B[x]
    ans += (S[N] - S[N-y]) + a*y
ans -= (m-M)*d
print(ans)

### FIXED CODE ###

N,M = map(int,input().split())
A = list(map(int,input().split()))
A.sort()
B = [0 for i in range(10**5+1)]
S = [0]
s = 0
for i in range(N):
    B[A[i]] += 1
    s += A[i]
    S.append(s)
for i in range(2,10**5+2):
    B[-i] += B[-i+1]
d = 0
u = 2*10**5
for i in range(30):
    x = (u+d)//2
    if i == 28:
        x += 1
    m = 0
    for i in range(N):
        a = A[i]
        y = max(x - a,0)
        if y <= 10**5:
            m += B[y]
    if m >= M:
        d = x
    else:
        u = x
ans = 0
for i in range(N):
    a = A[i]
    x = max(d - a,0)
    if x <= 10**5:
        y = B[x]
    else:
        y = 0
    ans += (S[N] - S[N-y]) + a*y
ans -= (m-M)*d
print(ans)
n=int(input())
t, a=map(int, input().split())
h=list(int(i) for i input.split())
temp=[abs(a-(t-(k*0.006))) for k in h]
print(temp.index(min(temp))+1)



### FIXED CODE ###

n=int(input())
t, a=map(int, input().split())
h=list(int(i) for i in input().split())
temp=[abs(a-(t-k*0.006)) for k in h]
print(temp.index(min(temp))+1)
from collections import defaultdict
from fractions import Fraction
import sys
input = sys.stdin.readline
N=int(input())
mod=10**9+7
dic=defaultdict(int)
c=0
d=0
e=0
for i in range(N):
 A,B = map(int,input().split())
 if A==0 and B==0:
  e+=1
 elif A==0:
  c+=1
 elif B==0:
  d+=1
 else:
   x=Fraction(A,B)
   dic[x]+=1
ans=1
for k in dic:
 if k>0:
  ans*=(pow(2,dic[k],mod)+pow(2,dic[-1/k],mod) -1)
 else:
  if -1/k in dic:
   continue
  else:
   ans*=pow(2,dic[k],mod)
 ans%=mod
ans*=(pow(2,c,mod)+pow(2,d,mod)-1)
print((ans-1+e)%mod)

### FIXED CODE ###

from collections import defaultdict
from math import gcd
import sys
input = sys.stdin.readline
N=int(input())
mod=10**9+7
dic=defaultdict(lambda: [0,0])
c=0
d=0
e=0
for i in [0]*N:
 A,B = map(int,input().split())
 if A==0 and B==0:
  e+=1
 elif A==0:
  c+=1
 elif B==0:
  d+=1
 else:
  g=gcd(A,B)
  A//=g
  B//=g
  if A*B>0:
   dic[(abs(A),abs(B))][0]+=1
  else:
   dic[(abs(B),abs(A))][1]+=1
ans=1
for k in dic:
 ans=ans*(pow(2,dic[k][0],mod)+pow(2,dic[k][1],mod) -1)
ans=ans*(pow(2,c,mod)+pow(2,d,mod)-1)
print((ans-1+e)%mod)
H,W=map(int,input().split())
C=[]
A=[]
for i in range(10):
    C.append(list(map(int,input().split())))
for i in range(H):
    A.append(list(map(int,input().split())))
# WF
for i in range(10):
    for j in range(10):
        for k in range(10):
            C[i][j]=min(C[i][j], C[i][k]+C[k][j])
for i in range(10):
    cst[i]=djcstra(i,1,C)
print(sum(sum(C[i][1] for i in AA if i >= 0) for AA in A))

### FIXED CODE ###

H,W=map(int,input().split())
C=[]
A=[]
for i in range(10):
    C.append(list(map(int,input().split())))
for i in range(H):
    A.append(list(map(int,input().split())))
# WF
for i in range(10):
    for j in range(10):
        for k in range(10):
            C[j][k]=min(C[j][k], C[j][i]+C[i][k])
print(sum(sum(C[i][1] for i in AA if i >= 0) for AA in A))