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

from collections import deque


def get_arounds(point, grid, max_x, max_y):
    x = point[0]
    y = point[1]
    arounds = [(x, y-1), (x+1, y), (x, y+1), (x-1, y)]
    return list(filter(lambda a: a[0] >= 0 and a[0] < max_x and
                                 a[1] >= 0 and a[1] < max_y and
                                 grid[a[0]][a[1]], arounds))


H, W = tuple(map(int, input().split()))

grid = []
for i in range(0, H):
    grid.append(list(map(lambda x: True if x == '.' else False, list(input()))))

black = sum(map(lambda l: l.count(False), grid))

p_grid = {(0, 0): 0, (H - 1, W - 1): -1}
queue = deque([(0, 0)])
while not len(queue) == 0:
    here = queue.popleft()
    if here == (H - 1, W - 1):
        break;
    grid[here[0]][here[1]] = False
    arounds = get_arounds(here, grid, H, W)
    for a in arounds:
        p_grid[a] = p_grid[here] + 1
    queue.extend(arounds)

if p_grid[H-1, W-1] == -1:
    print('-1')
else:
    print(H * W - (p_grid[H-1, W-1] + 1) - black)


### FIXED CODE ###

from collections import deque


def get_arounds(point, grid, max_x, max_y):
    x = point[0]
    y = point[1]
    arounds = [(x + dx, y + dy) for dx, dy in ((0, -1), (1, 0), (0, 1), (-1, 0))]
    return list(filter(lambda a: 0 <= a[0] < max_x and
                                 0 <= a[1] < max_y and
                                 grid[a[0]][a[1]], arounds))


H, W = tuple(map(int, input().split()))

grid = []
for i in range(0, H):
    grid.append(list(map(lambda x: True if x == '.' else False, list(input()))))

black = sum(map(lambda l: l.count(False), grid))

grid[0][0] = False
p_grid = {(0, 0): 0}
queue = deque([(0, 0)])
while not len(queue) == 0:
    here = queue.popleft()
    if here == (H - 1, W - 1):
        break;
    arounds = get_arounds(here, grid, H, W)
    for a in arounds:
        grid[a[0]][a[1]] = False
        p_grid[a] = p_grid[here] + 1
    if not arounds:
        continue
    queue.extend(arounds)

if (H-1, W-1) in p_grid:
    print(H * W - (p_grid[H-1, W-1] + 1) - black)
else:
    print(-1)
### BUGGY CODE ###

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

dp = [[0 for _ in range(d+1)] for _ in range(c+1)]
for i in range(a, c+1):
    for j in range(b, d+1):
        if i == a and j == b:
            dp[i][j] = 1
            continue
        dp[i][j] += dp[i-1][j] * j
        dp[i][j] += dp[i][j-1] * i
        dp[i][j] -= dp[i-1][j-1] * (i-1) * (j-1)
        dp[i][j] %= mod


print(dp[c][d])

### FIXED CODE ###

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

dp = [[0 for _ in range(d+1)] for _ in range(c+1)]
for i in range(a, c+1):
    for j in range(b, d+1):
        if i == a and j == b:
            dp[i][j] = 1
            continue
        dp[i][j] += dp[i-1][j] * j
        dp[i][j] += dp[i][j-1] * i
        dp[i][j] -= dp[i-1][j-1] * (i-1) * (j-1)
        dp[i][j] %= mod


print(dp[c][d])
### BUGGY CODE ###

def f(array):
    temp = 'abcdefghijklmnopqrstuvwxyz'
    ret = [0] * len(temp)
    cnt = 0
    for x in array:
        ret[temp.index(x)] += 1
        cnt += 1
        if cnt == 10:
            break
    return ret


N = int(input())
s = [f(input()) for i in range(N)]
check = [False] * N
cnt = 0
for i in range(N - 1):
    part = 0
    if check[i]:
        continue
    for j in range(i + 1, N):
        if check[j]:
            continue
        if s[i] == s[j]:
            part += 1
            check[j] = True
    cnt += (part + 1) * part // 2

print(cnt)


### FIXED CODE ###

def f(array):
    temp = 'abcdefghijklmnopqrstuvwxyz'
    ret = [0] * len(temp)
    cnt = 0
    for x in array:
        ret[temp.index(x)] += 1
        cnt += 1
        if cnt == 10:
            break
    return ret

N = int(input())
s = [''.join(sorted(input())) for i in range(N)]

dic = {}
for i in range(N):
    if s[i] in dic:
        dic[s[i]] += 1
    else:
        dic[s[i]] = 1

cnt = 0
for v in dic.values():
    cnt += v * (v - 1) // 2

print(cnt)
### BUGGY CODE ###

n=int(input())
a=[list(map(int,input().split())) for _ in range(n)]
ans=0
for i in range(n-1):
  for j in range(i+1,n):
    flg=True
    for k in range(n):
      if k in (i,j):continue
      if a[i][j]>a[i][k]+a[k][j]:
        print(-1)
        exit()
      elif a[i][j]==a[i][k]+a[k][j]:
        flg=False
    if flg:
      ans+=a[i][j]
      #print(i,j)

print(ans)


### FIXED CODE ###

n=int(input())
a=[list(map(int,input().split())) for _ in range(n)]
ans=0
for i in range(n-1):
  for j in range(i+1,n):
    flg=True
    for k in range(n):
      if k in (i,j):continue
      if a[i][j]>a[i][k]+a[k][j]:
        print(-1)
        exit()
      elif a[i][j]==a[i][k]+a[k][j]:
        flg=False
    if flg:
      ans+=a[i][j]
      #print(i,j)

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

# 入力 : 自然数     ex) 12
# 出力 : 約数リスト ex) [2, 2, 3]
def factorization(n):
    R = int(n)
    s = 0
    L = []
    div = 2
    while s == 0:
        for i in range(div, R + 1):
            if n % i == 0:
                n = n / i
                div = i
                if n == 1:
                    s = 1
                L.append(i)
                break
    return L


n = int(input())
if n == 1:
    print(1)
    exit()
divs = factorization(n)
N = [i for i in divs]  # N = bit探索する桁数
maxDigit = n
# Nの要素の全組み合わせが出力
for i in range(1, 1 << len(N)):
    output = []
    nonout = []
    outNum = 1
    nonOutNum = 1
    for j in range(len(N)):
        if ((i >> j) & 1) == 1:
            output.append(N[j])  # このjが今回探索するindexの1つ
            outNum *= N[j]
        else:
            nonout.append(N[j])
            nonOutNum *= N[j]
    # print("{} vs {}".format(outNum, nonOutNum))
    digitOut = 0
    digitNonOut = 0
    while outNum > 0:
        digitOut += 1
        outNum = int(outNum / 10)
    while nonOutNum > 0:
        digitNonOut += 1
        nonOutNum = int(nonOutNum / 10)
    if max(digitOut, digitNonOut) < maxDigit:
        maxDigit = max(digitOut, digitNonOut)
print(maxDigit)


### FIXED CODE ###

# 入力 : 自然数     ex) 12
# 出力 : 約数リスト ex) [(2,2),(3,1)]
def factorize(n):
    fct = []  # prime factor
    b, e = 2, 0  # base, exponent
    while b * b <= n:
        while n % b == 0:
            n = n // b
            e = e + 1
        if e > 0:
            fct.append((b, e))
        b, e = b + 1, 0
    if n > 1:
        fct.append((n, 1))
    return fct


def divisorize(fct):
    b, e = fct.pop()  # base, exponent
    pre_div = divisorize(fct) if fct else [[]]
    suf_div = [[(b, k)] for k in range(e + 1)]
    return [pre + suf for pre in pre_div for suf in suf_div]


def num(fct):
    a = 1
    for base, exponent in fct:
        a = a * base ** exponent
    return a

n = int(input())
if n == 1:
    print(1)
    exit()
fct = factorize(n)
maxDigit = n
for div in divisorize(fct):
    outNum = num(div)
    nonOutNum = int(n/outNum)
    digitOut = 0
    digitNonOut = 0
    while outNum > 0:
        digitOut += 1
        outNum = int(outNum / 10)
    while nonOutNum > 0:
        digitNonOut += 1
        nonOutNum = int(nonOutNum / 10)
    if max(digitOut, digitNonOut) < maxDigit:
        maxDigit = max(digitOut, digitNonOut)
print(maxDigit)
### BUGGY CODE ###

n, q = map(int, input().split())
s = input()
s = s.replace("AC", "12")
idx = [i+1 for i, x in enumerate(s) if x in "1"]

for j in range(q):
    l, r = map(int, input().split())
    n = [i for i in idx if ((i >= l) & (i < r))]
    print(len(n))

### FIXED CODE ###

n, q = map(int, input().split())
s = input()
m = [0]
c = 0
for i in range(1, n):
    if (s[i-1] == "A") & (s[i] == "C"):
        c += 1
    m.append(c)

for j in range(q):
    l, r = map(int, input().split())
    print(m[r-1] - m[l-1])
### BUGGY CODE ###

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

max_count = 0
max_i = 0

for i, h in enumerate(H):
  arr = H[i+1:]
  now = h
  count = 0
  for ar in arr:
    migi = ar
    if now >= ar:
      count += 1
    else:
      break
    
    if count > max_count:
      max_i = i
      max_count = count
    now = ar

print(max_count)
    

### FIXED CODE ###

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

max_count = 0
max_i = 0

t_max_count = 0
t_max_i = 0

for i, h in enumerate(H):
  if i == (len(H) - 1):
    break
  
  migi = H[i+1]
  
  if h >= migi:
    t_max_count += 1
    t_max_i = i
  else:
    if max_count < t_max_count:
      max_count = t_max_count
      max_i = t_max_i
    t_max_count = 0
    t_max_i = 0
      
if max_count < t_max_count:
  max_count = t_max_count
  max_i = t_max_i
print(max_count)
### BUGGY CODE ###

A, B, K = list(map(int, input().strip().split(' ')))
newlist=[]
for j in range(A,B+1):
    if not(j >= A+K and j <= B-K):
        newlist.append(j)

for k in newlist:
    print(k)


### FIXED CODE ###

A, B, K = list(map(int, input().strip().split(' ')))
for j in range(A,min(A+K,B+1)):
    if not(j >= A+K and j <= B-K):
        print(j)
for i in range(max(B-K,j+1),B+1):
    if not(i >= A+K and i <= B-K):
        print(i)
### BUGGY CODE ###

N = int(input())
A = [list(map(int, input().split())) for i in range(N)]
MOD = 10 ** 9 + 7
dp = [0] * (1<<N)
dp[0] = 1
for i in range(1, 1<<N):
    for j in range(N):
        if i>>j&1 == 0: continue
        cnt = bin(i).count("1")
        dp[i] += dp[i - (1<<j)] * A[cnt-1][j]
        dp[i] %= MOD
print(dp[-1])


### FIXED CODE ###

N = int(input())
A = [list(map(int, input().split())) for i in range(N)]
MOD = 10 ** 9 + 7
dp = [0] * (1<<N)
dp[0] = 1
for i in range(1, 1<<N):
    cnt = bin(i).count("1")
    for j in range(N):
        if (i>>j)&1 == 0: continue
        dp[i] += dp[i - (1<<j)] * A[cnt-1][j]
        dp[i] %= MOD
print(dp[-1])
### BUGGY CODE ###

Mod = 10**9+7
S = input()
N = len(S)
O = 1
A = [0]*N
AB = [0]*N
ABC = [0]*N

for i in range(N):
    A[i] = A[i-1]
    AB[i] = AB[i-1]
    ABC[i] = ABC[i-1]
    if S[i] == 'A':
        A[i] += O
    if S[i] == 'B':
        AB[i] += A[i-1]
    if S[i] == 'C':
        ABC[i] += AB[i-1]
    if S[i] == '?':
        A[i] *= 3
        A[i] += O
        AB[i] *= 3
        AB[i] += A[i-1]
        ABC[i] *= 3
        ABC[i] += AB[i-1]
        O *= 3
    A[i] %= Mod
    AB[i] %= Mod
    ABC[i] %= Mod

print(ABC[-1])

### FIXED CODE ###

Mod = 10**9+7
S = input()
N = len(S)
O = 1
A = [0]*N
AB = [0]*N
ABC = [0]*N

for i in range(N):
    A[i] = A[i-1]
    AB[i] = AB[i-1]
    ABC[i] = ABC[i-1]
    if S[i] == 'A':
        A[i] += O
    if S[i] == 'B':
        AB[i] += A[i-1]
    if S[i] == 'C':
        ABC[i] += AB[i-1]
    if S[i] == '?':
        A[i] *= 3
        A[i] += O
        AB[i] *= 3
        AB[i] += A[i-1]
        ABC[i] *= 3
        ABC[i] += AB[i-1]
        O *= 3
    A[i] %= Mod
    AB[i] %= Mod
    ABC[i] %= Mod
    O %= Mod
print(ABC[-1])
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
x = 1
for i, v in enumerate(A):
  if i >= N:
    break
  x *= A[i]

if x>10**18:
  print('-1')
  exit()
print(x)

### FIXED CODE ###

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

if 0 in A:
  print('0')
  exit()

for i, v in enumerate(A):
  if i >= N:
    break
  x *= A[i]
  if x>10**18:
    print('-1')
    exit()

print(x)
### BUGGY CODE ###

i = int(input())

while True:
    i = i-1000
    if 0 < i < 1000:
        print(1000 - i)
        break
    elif i == 0:
        print(0)
        break

### FIXED CODE ###

import math
i = int(input())

s, f = math.modf(i/1000)
if s != 0.0:
    f += 1
v = int((f) * 1000) - i
if v >= 1000:
    print(2000 - v)
else:
    print(v)
### BUGGY CODE ###

N,M = map(int,input().split())
ABC = [list(map(int,input().split())) for _ in [0]*M]

E = [{} for _ in [0]*N]
for a,b,c in ABC:
    E[a-1][b-1] = -c


INFTY = 10**18
d = [INFTY]*N
d[0] = 0

def update():
    done = [False]*N
    done[0] = True
    q = [0]
    qp = q.pop
    qa = q.append
    while q:
        i = qp()
        di = d[i]
        for j,c in E[i].items():
            d[j] = min(d[j],d[i]+c)
            if not done[j]:
                qa(j)
                done[j] = True

for _ in range(N-1):update()
dc = d[:]
for _ in range(N):update()
if dc[-1]!=d[-1]:
    print("inf")
else:
    print(-d[-1])

### FIXED CODE ###

N,M = map(int,input().split())
ABC = [list(map(int,input().split())) for _ in [0]*M]

E = [{} for _ in [0]*N]
for a,b,c in ABC:
    E[a-1][b-1] = -c


INFTY = 10**18
d = [INFTY]*N
d[0] = 0

def update():
    done = [False]*N
    done[0] = True
    q = [0]
    qp = q.pop
    qa = q.append
    while q:
        i = qp()
        di = d[i]
        for j,c in E[i].items():
            d[j] = min(d[j],d[i]+c)
            if not done[j]:
                qa(j)
                done[j] = True

for _ in range(N-1):update()
dc = d[:]
for _ in range(N):update()
if dc[-1]!=d[-1]:
    print("inf")
else:
    print(-d[-1])
### BUGGY CODE ###

N = int(input())
lst = [i for i in range(2, N + 1)] + [1]

val = 0
for i in range(N):
    val += (i + 1) % lst[i]

print(val)

### FIXED CODE ###

N = int(input())
print(N * (N - 1) // 2)
### BUGGY CODE ###

S = input()
N = len(S)

dp = [[0]*2019 for _ in [0]*(N+1)]
for i,s in enumerate(S,1):
    s = int(s)
    dpi = dp[i]
    dpi1 = dp[i-1]
    dpi[s] += 1
    for j in range(2019):
        dpi[(j*10+s)%2019] += dpi1[j]

ans = sum(dp[i][0] for i in range(N+1))
print(ans)

### FIXED CODE ###

S = input()
N = len(S)

dp = [[0]*2019 for _ in [0]*2]
ans = 0
for i,s in enumerate(S,1):
    s = int(s)
    i %= 2
    dpi = [0]*2019
    dpi1 = dp[1-i]
    dpi[s] += 1
    for j in range(2019):
        dpi[(j*10+s)%2019] += dpi1[j]
    dp[i] = dpi
    ans += dpi[0]

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

# -*- coding:utf-8 -*-
n, k = list(map(int, input().split()))
nums = list(map(int, input().split()))
one_index = nums.index(1)
min = n
for i in range(k):
    left = one_index - i
    right = len(nums[one_index+1:]) + i
    if left + right > n-1:
        continue
    else:
        min_tmp = (-(-left//(k-1)))+(-(-right//(k-1)))
        if min > min_tmp:
            min = min_tmp
print(min)


### FIXED CODE ###

# -*- coding:utf-8 -*-
import math
n, k = list(map(int, input().split()))
nums = list(map(int, input().split()))
one_index = nums.index(1)
if k == len(nums):
    print(1)
else:
    print(math.ceil((n-1)/(k-1)))
### BUGGY CODE ###

n = int(input())

alp = ["a","b","c","d","e",
"f","g","h","i","j",
"k","l","m","n","o",
"p","q","r","s","t",
"u","v","w","x","y","z"]

ans = 0
list1 = []
for i in range(n):
    s = input()
    list2=[]
    for alp1 in alp:
        list2.append(s.count(alp1))

    if i >0:
        ans = ans + sum(map(lambda x: x==list2,list1))
            
    list1.append(list2)

print(ans)

### FIXED CODE ###

n = int(input())

ans = 0
ans_dict = {}

for i in range(n):
    s = input()
    s = ''.join(sorted(s))
    if(s in ans_dict):
        ans += ans_dict[s]
        ans_dict[s] += 1
    else:
        ans_dict[s] = 1
        
print(int(ans))
### BUGGY CODE ###

n = int(input())
dec = list(map(int, input().split()))
diff = []
for i in range(1, n):
    diff.append(abs(sum(dec[:i])-sum(dec[i:])))
print(min(diff))

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))

snk = a[0]
ari = sum(a)-snk
ans = abs(snk-ari)
for i in range(n-2):
    snk += a[i+1]
    ari -= a[i+1]
    ans = min(ans, abs(snk-ari))
print(ans)
### BUGGY CODE ###

n = int(input())
s = input()
cnt = 0
for i in range(n-2):
    for j in range(i+1, n-1):
        for k in range(j+1, n):
            if k - j != j - i:
                if s[i] != s[j] and s[j] != s[k] and s[k] != s[i]:
                    cnt += 1
print(cnt)

### FIXED CODE ###

n = int(input())
s = input()
r = 0
g = 0
b = 0
for letter in s:
    if letter == "R":
        r +=1
    elif letter == "G":
        g +=1
    elif letter == "B":
        b +=1
total = r * g * b
subs = 0
for i in range(n):
    for j in range(i + 1, n):
        k = 2 * j - i
        if k <= n - 1:
            if s[i] == s[j]:
                continue
            elif s[j] == s[k]:
                continue
            elif s[k] == s[i]:
                continue
            else:
                subs += 1
        else:
            break
ans = total - subs
print(ans)
### BUGGY CODE ###

N = int(input())
result = 0

def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]

for num in range(1, N+1):
	result += len(make_divisors(num)) * num
print(result)

### FIXED CODE ###

N = int(input())
divisors = [1 for _ in range(N+1)]
result = 0

for n in range(2, N+1):
  for m in range(n, N+1, n):
    divisors[m] += 1
for i, d in enumerate(divisors):
  result += i * d
print(result)
### BUGGY CODE ###

import fractions
from functools import reduce

def gcd_list(numbers):
    return reduce(fractions.gcd, numbers)

n = int(input())
a = list(map(int, input().split()))

ans = 0

if n <= 10**3:
    for i in range(n):
        ans = max(gcd_list(a[:i]+a[i+1:]), ans)

    print(ans)
    exit()
else:
    n1 = n//10**3
    n2 = n%10**3

    g = []

    for i in range(n1):
        g.append(gcd_list(a[i*(10**3):(i+1)*(10**3)]))

    if n2 >0:
        g.append(gcd_list(a[n1*(10**3):]))

    for i in range(n):
        memo = g[i//(10**3)]
        g[i//(10**3)] = gcd_list(a[(i//10**3)*(10**3):i] + a[i+1:(i//10**3+1)*(10**3)])
        ans = max(gcd_list(g), ans)
        g[i // (10 ** 3)] = memo
    print(ans)
    

### FIXED CODE ###

import fractions

n = int(input())
a = list(map(int, input().split()))

ans = 0

l = [0]
r = [0]

for i in range(n):
    l.append(fractions.gcd(l[i],a[i]))
    r.append(fractions.gcd(r[i],a[n-i-1]))

ans = 0

for i in range(n):
    ans = max(ans, fractions.gcd(l[i],r[n-i-1]))

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

N = int(input())
A = list(map(int, input().split()))
x = 1
for i in A:
    x *= i
if x > 10**18:
    print(-1)
else:
    print(x)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
x = 1
if 0 in A:
    print(0)
else:
    for i in A:
        x *= i
        if x > 10**18:
            break
    if x > 10**18:
        print(-1)
    else:
        print(x)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10000000)
N, M, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

AA = list(reversed(A))
BB = list(reversed(B))

rest = K
ans = 0

def dfs(cost, aindex, bindex, score):

    if K == cost:
        # print("1:", score, cost)
        return score
    elif K < cost:
        # print("2:", score, cost)
        return score - 1
        # return -1
    
    if aindex == N and bindex == M:
        # print("3:", score, cost)
        return score

    if aindex >= N:
        return dfs(cost + B[bindex], aindex, bindex+1, score + 1)
    
    elif bindex >= M:
        return dfs(cost + A[aindex], aindex+1, bindex, score + 1)

    else:
        return max(dfs(cost + A[aindex], aindex+1, bindex, score + 1), dfs(cost + B[bindex], aindex, bindex + 1, score + 1))

print(max(dfs(A[0], 1, 0, 1), dfs(B[0], 0, 1, 1)))

### FIXED CODE ###

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

a, b = [0], [0]
for ai in A:
    a.append(a[-1] + ai)

for bi in B:
    b.append(b[-1] + bi)

# print(a, b)
ans = 0
bs = M
for i in range(N+1):
    if a[i] > K:
        break
    for j in reversed(range(bs+1)):
        if a[i] + b[j] <= K:
            ans = max(ans, i + j)
            bs = j
            break

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

def getLunum(n):
    if(n==0):
        return 2
    elif(n==1):
        return 1
    else:
        return getLunum(n-1)+getLunum(n-2)
a=int(input())
print(getLunum(a))

### FIXED CODE ###

b=[]
a=int(input())
b.append(2)
b.append(1)
for i in range(2,87):
    b.append(b[i-1]+b[i-2])
print(b[a])
### BUGGY CODE ###

from collections import Counter

def main():
    N = int(input())
    A = list(map(int, input().split()))
    count = Counter(A)
    sum_ = sum([i*(i-1)/2 for i in count.values()])

    for i in range(len(A)):
        remain = A[:i] + A[i+1:]
        took = A[i]
        took_count = count[took]
        sub = took_count - 1
        print(int(sum_ - sub))

if __name__ == '__main__':
    main()

### FIXED CODE ###

from collections import Counter

def main():
    N = int(input())
    A = list(map(int, input().split()))
    count = Counter(A)
    sum_ = sum([v*(v-1)/2 for v in count.values()])

    for i in range(len(A)):
        took_count = count[A[i]]
        sub = took_count - 1
        print(int(sum_ - sub))

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

# -*- using:utf-8 -*-
from itertools import combinations

class main:
  def v(array):
    sum = 0
    mod = 1000000007
    for i in range(len(array)):
      sum += array[i][0] * array[i][1]
    ans = sum % mod
    print(ans)

if __name__ == "__main__":
  n = int(input())
  li = list(map(int, input().split()))
  array = list(combinations(li, 2))
  main.v(array)

### FIXED CODE ###

# -*- using:utf-8 -*-

class main:
  def function(n, a):
    mod = 10 **9 +7
    S = [0] * (n + 1)
    for i in range(n):
      S[i + 1] = S[i] + a[i]
    SN = S[-1]
    ans = 0
    for i in range(n - 1):
      cnt = a[i] * (SN - S[i + 1])
      ans += cnt
    print(ans % mod)



if __name__ == "__main__":
  n = int(input())
  a = list(map(int, input().split()))
  main.function(n,a)
### BUGGY CODE ###

import math 
 
n = int(input())
m = int(round(math.sqrt(n)))
while True:
    p, q = divmod(n, m)
    if q == 0:
        print(m + p - 2)
        break
    else:
        m += 1


### FIXED CODE ###

import math 
 
n = int(input())
m = int(round(math.sqrt(n)))
while m >= 1:
    p, q = divmod(n, m)
    if q == 0:
        print(m + p - 2)
        break
    else:
        m -= 1
### BUGGY CODE ###

def main():
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    for _ in range(M):
        B, C = map(int, input().split())
        A = [C] * B + A

    sort_A = sorted(A,reverse=True)

    print(sum(sort_A[:N]))



main()

### FIXED CODE ###

from collections import defaultdict

def main():
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    d = defaultdict(int)
    for a in A:
        d[a] += 1
    for _ in range(M):
        B, C = map(int, input().split())
        d[C] += B

    sort_d = sorted(d.items(),reverse = True)

    cnt = 0
    ans = 0
    for i,j in sort_d:
        if cnt + j < N:
            ans += i * j
            cnt += j
        elif cnt + j >= N:
            if cnt == N:
                break
            ans += i * (N - cnt)
            break 

    print(ans)



main()
### BUGGY CODE ###

N=int(input())
X_raw=list(map(int,input().split()))

for i in range(N):
    X=X_raw[:]
#    X.pop(i)
    del X[i]
    X.sort()
    print(X[int(N/2-1)])




### FIXED CODE ###

N=int(input())
X=list(map(int,input().split()))
sX=sorted(X)
for i in X:
    if i<=sX[int(N/2-1)]:
        print(sX[int(N/2)])
    else:
        print(sX[int(N/2-1)])
### BUGGY CODE ###

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

st = 1 #k楽器
for i in range(k):
    st *= a[i]

for i in range(n-k):
    if st < st//a[i]*a[i+k]:
        print('Yes')
    else:
        print('No')
    st = st//a[i]*a[i+k]


### FIXED CODE ###

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

for i in range(n-k):
    if a[i] < a[i+k]:
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

N,M = map(int,input().split())
X = list(map(int,input().split()))
if N > M :
    print(0)
else:
    flag = []
    X.sort()
    x_next = X[0]
    for _ in X:
        flag.append(_ - x_next)
        x_next = _
    for lp in range(N-1):
        ff = flag.index(max(flag))
        flag.pop(ff)
    print(sum(flag))

### FIXED CODE ###

N,M = map(int,input().split())
X = list(map(int,input().split()))
if N > M :
    print(0)
else:
    X.sort()
    x_next = X[0]
    flag = [X[_] - X[_-1] for _ in range(1,M)]
    flag.sort()
    flag = flag[:M-N:]
    print(sum(flag))