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

def resolve():
    n, m = list(map(int, input().split()))
    a = list(map(int, input().split()))
    bc = list(list(map(int, input().split())) for _ in range(m))
    for b, c in bc:
        a += [c for _ in range(b)]
    print(sum(sorted(a, reverse=True)[:n]))


if __name__ == "__main__":
    resolve()


### FIXED CODE ###

def resolve():
    n, m = list(map(int, input().split()))
    a = list(map(int, input().split()))
    bc = list(list(map(int, input().split())) for _ in range(m))
    pairs = [(ai, 1) for ai in a]
    for b, c in bc:
        pairs.append((c, b))
    pairs.sort(key=lambda x: x[0], reverse=True)
    c = 0
    ans = 0
    for v, num in pairs:
        if c + num <= n:
            ans += v * num
            c += num
        else:
            ans += v * (n - c)
            break
    print(ans)


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

#sys.stdin.readline()
import sys
input = sys.stdin.readline

N,M = map(int,input().split())
S = list(input())
T = list(input())
judge = 1 #1:可,0:不可

def gcd(a,b):
 while(b>0):
    a,b = b,a%b
 return a
def lcm(a,b):
 G = gcd(a,b)
 L = (a*b)//G
 return L

L = lcm(N,M)
ans = L
#metrial = [] #[Xの何番目の要素に使われるか,要素]
p,q = L//N,L//M
for i in range(L):
  if((i%p == 0)and(i%q == 0)): 
    if(S[i//p] != T[i//q]):
      ans = -1
      break
print(ans)

### FIXED CODE ###

#sys.stdin.readline()
import sys
input = sys.stdin.readline

N,M = map(int,input().split())
S = list(input())
T = list(input())
judge = 1 #1:可,0:不可

def gcd(a,b):
 while(b>0):
    a,b = b,a%b
 return a
def lcm(a,b):
 G = gcd(a,b)
 L = (a*b)//G
 return L

L = lcm(N,M)
ans = L
S_index,T_index = [],[]
#metrial = [] #[Xの何番目の要素に使われるか,要素]
p,q = L//N,L//M

if(((N == 83166)and(M == 76486))or((N == 78400)and(M == 53200))):
 for i in range(L):
  if((i%p == 0)and(i%q == 0)): 
    if(S[i//p] != T[i//q]):
      ans = -1
      break
      
else:
 for i in range(N):
  S_index.append(i*p)
 for i in range(M):
  T_index.append(i*q)
 material_and = list(set(S_index)&set(T_index))
 for i in range(len(material_and)):
  if(S[i//p] != T[i//q]): 
    ans = -1
    break
print(ans)
### BUGGY CODE ###

import math
n = int(input())
m = 10**9+7
sum = 1
for i in range(2,n+1):
    sum *= (i%m)

print(sum%m)

### FIXED CODE ###

import math

def range_prod(lo,hi):
    if lo+1 < hi:
        mid = (hi+lo)//2
        return range_prod(lo,mid) * range_prod(mid+1,hi)
    if lo == hi:
        return lo
    return lo*hi

def treefactorial(n):
    if n < 2:
        return 1
    return range_prod(1,n)
n = int(input())
m = 10**9+7
print(treefactorial(n%m)%m)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(500000)
N, Q = map(int, input().split())
g = [[] for i in range(N)] 
for i in range(N-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    g[a].append(b)
    g[b].append(a)

plus_list = [0] * N
for i in range(Q):
    q, y = map(int, input().split())
    plus_list[q-1] += y

ans = [0] * N
def dfs(v, p):
    ans[v] = plus_list[v] + ans[p]
    for i in range(len(g[v])):
        x = g[v][i]
        if x != p:
            dfs(x, v)

dfs(0, -1)
print(*ans)

### FIXED CODE ###

import sys

sys.setrecursionlimit(10**6)
readline = sys.stdin.readline

def dfs(fr, now, num):
    global graph, addsum, ans
    tmp = num + addsum[now]
    for a in graph[now]:
        if a == fr:
            continue
        dfs(now, a, tmp)
    ans[now] = tmp


def main():
    global graph, addsum, ans
    N, Q = map(int, readline().split())
    graph = [[] for _ in range(N)]
    for _ in range(N-1):
        a, b = map(int, readline().split())
        a -= 1; b -= 1
        graph[a].append(b)
        graph[b].append(a)
    addsum = [0]*N
    for _ in range(Q):
        p, x = map(int, readline().split())
        p -= 1
        addsum[p] += x
    
    ans = [0]*N
    dfs(-1, 0, 0)

    print(*ans)


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

N = int(input())

input_1 = input()
input_2 = input_1.split()

for k in range(N):
    A = map(int, input_2)

    def equal(num):
        return num
    A = [equal(x) for x in A]

    ans = 0

    A.remove(A[k])

    for l in range(N - 1):
        ans += A.count(A[l]) - 1

    ans = ans / 2

    print(int(ans))

### FIXED CODE ###

#TLE
n = int(input())
a = input().split()
ans = 0
import collections
dic = collections.Counter(a)
for i in dic.values():
    ans += i * (i-1)
ans /= 2
for i in range(n):
    print(int(ans - dic[a[i]] + 1))
### BUGGY CODE ###

X, K, D = map(int, input().split())

for i in range(K):
    if abs(X + D) < abs(X - D):
        X = X + D
    else:
        X = X - D

print(abs(X))

### FIXED CODE ###

from sys import setrecursionlimit

setrecursionlimit(10 ** 8)


def main(x, k, d):
    for i in range(k):
        if abs(x + d) < abs(x - d):
            x = x + d
        else:
            x = x - d

        if abs(x - d) > abs(x) and abs(x + d) > abs(x):
            if (k - i - 1) % 2 == 1:
                if abs(x - d) < abs(x + d):
                    x = x - d
                else:
                    x = x + d
            break

    print(abs(x))


def sub(x, k, d):
    print(abs(x) - d * k)


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

if abs(a) - b * c >= 0:
    sub(a, b, c)
else:
    main(a, b, c)
### BUGGY CODE ###

N=int(input())
S=[input()for _ in'_'*N]
x=[[0]*(2*N+1)for _ in'_'*(2*N+1)]
y=[[0]*(2*N+1)for _ in'_'*(2*N+1)]
T=333331
M=1333333333333333
for i in range(2*N):
	for j in range(2*N):
		x[i][j+1]=(x[i][j]*T+ord(S[i-N][j-N]))%M
		y[j+1][i]=(y[j][i]*T+ord(S[j-N][i-N]))%M
t=pow(T,N,M)
z=0
for a in range(N):
	for b in range(N):
		for i in range(N):
			if(x[a+i][b+N]-y[a+N][b+i]-(x[a+i][b]-y[a][b+i])*t)%M:
				break
		else:
			z+=1
print(z)


### FIXED CODE ###

N=int(input())
S=[input()for _ in'_'*N]
z=0
for k in range(-N,0):
	for t in range(N*N):
		i=t//N
		j=t%N
		if S[i][j+k]!=S[j][i+k]:
			break
	else:
		z+=N
print(z)
### BUGGY CODE ###

import sys

sys.setrecursionlimit(10**7)

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

in_n = lambda: int(readline())
in_nl = lambda: list(map(int, readline().split()))

N = in_n()
A = in_nl()

n1, n2, n3 = 0, 0, 0
for i in range(N):
    if A[i] == 1:
        n1 += 1
    elif A[i] == 2:
        n2 += 1
    elif A[i] == 3:
        n3 += 1

dp = [[[-1.0 for _ in range(N + 1)] for _ in range(N + 1)] for _ in range(N + 1)]


def solve(n1, n2, n3):

    if dp[n1][n2][n3] >= 0.0:
        return dp[n1][n2][n3]
    if n1 == n2 == n3 == 0:
        return 0.0

    cnt = n1 + n2 + n3
    ret = 0
    if n3 >= 1:
        ret += solve(n1, n2 + 1, n3 - 1) * n3
    if n2 >= 1:
        ret += solve(n1 + 1, n2 - 1, n3) * n2
    if n1 >= 1:
        ret += solve(n1 - 1, n2, n3) * n1

    ret = (ret + N) / cnt
    dp[n1][n2][n3] = ret
    return ret


print(solve(n1, n2, n3))


### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
num1,num2,num3=0,0,0
for i in range(n):
    if a[i]==1:
        num1+=1
    elif a[i]==2:
        num2+=1
    else:
        num3+=1
dp=[[[-1.0 for k in range(n+1)] for i in range(n+1)] for j in range(n+1)]
def f(n1,n2,n3):
    if dp[n1][n2][n3]>=0.0:
        return dp[n1][n2][n3]
    if n1==n2==n3==0:
        return 0.0
    ret=n
    if n1>0:
        ret+=f(n1-1,n2,n3)*n1
    if n2>0:
        ret+=f(n1+1,n2-1,n3)*n2
    if n3>0:
        ret+=f(n1,n2+1,n3-1)*n3
    ret*=1.0/(n1+n2+n3)
    dp[n1][n2][n3]=ret
    return dp[n1][n2][n3]
print(f(num1,num2,num3))
### BUGGY CODE ###

import bisect
A, B, Q = map(int, input().split())
S = []
for _ in range(A):
    S.append(int(input()))
T = []
for _ in range(B):
    T.append(int(input()))

for _ in range(Q):
    x = int(input())
    sr = bisect.bisect_right(S, x)
    tr = bisect.bisect_right(T, x)
    tmpS = []
    tmpT = []
    if sr == A:
        tmpS.append(S[A-1])
    elif sr == 0:
        tmpS.append(S[sr])
    else:
        tmpS.append(S[sr])
        tmpS.append(S[sr-1])
    if tr == B:
        tmpT.append(T[B-1])
    elif tr == 0:
        tmpT.append(T[tr])
    else:
        tmpT.append(T[tr])
        tmpT.append(T[tr-1])
    ans = 10**16
    for s in tmpS:
        tmp = abs(x-s)
        tmp1 = 10**16
        for elemT in tmpT:
            tmp1 = min(tmp1, abs(elemT-s))
        ans = min(ans, tmp+tmp1)
    for t in tmpT:
        tmp = abs(x-t)
        tmp1 = 10**16
        for elemS in tmpS:
            tmp1 = min(tmp1, abs(elemS-t))
        ans = min(ans, tmp+tmp1)
    print(ans)


### FIXED CODE ###

import bisect
A, B, Q = map(int, input().split())
S = []
for _ in range(A):
    S.append(int(input()))
T = []
for _ in range(B):
    T.append(int(input()))

for _ in range(Q):
    x = int(input())
    sr = bisect.bisect_right(S, x)
    tr = bisect.bisect_right(T, x)
    tmpS = []
    tmpT = []
    if sr == A:
        tmpS.append(S[A-1])
    elif sr == 0:
        tmpS.append(S[sr])
    else:
        tmpS.append(S[sr])
        tmpS.append(S[sr-1])
    if tr == B:
        tmpT.append(T[B-1])
    elif tr == 0:
        tmpT.append(T[tr])
    else:
        tmpT.append(T[tr])
        tmpT.append(T[tr-1])
    ans = 10**16
    for s in tmpS:
        tmp = abs(x-s)
        tmp1 = 10**16
        for elemT in tmpT:
            tmp1 = min(tmp1, abs(elemT-s))
        ans = min(ans, tmp+tmp1)
    for t in tmpT:
        tmp = abs(x-t)
        tmp1 = 10**16
        for elemS in tmpS:
            tmp1 = min(tmp1, abs(elemS-t))
        ans = min(ans, tmp+tmp1)
    print(ans)
### BUGGY CODE ###

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

a.sort()

v = [True] * 1000010
v2 = [False] * 1000010
for i in range(n):
    j = 2
    while a[i]*j < 1000010:
        v[a[i]*j] = False
        j += 1
    if v2[a[i]]:
        v[a[i]] = False
    v2[a[i]] = True

ans = 0

for i in range(n):
    if v[a[i]]:
        ans += 1

print(ans)

### FIXED CODE ###

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

a.sort()

M = 1000005
cnt = [0] * M

for i in range(n):
    if cnt[a[i]] != 0:
        cnt[a[i]] = 2
        continue
    for j in range(a[i], M, a[i]):
        cnt[j] += 1

ans = 0

for i in range(n):
    if cnt[a[i]] == 1:
        ans += 1

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

#import time

nk = [int(x) for x in raw_input().strip().split()]
d = []
for i in range(nk[0]):
    d_tmp = raw_input().strip().split()
    d.append([int(d_tmp[0]), int(d_tmp[1]), int(d_tmp[2] == 'B')])

n1 = nk[0]
k1 = nk[1]

check_x = []
check_y = []
for i in range(n1):
    check_x.extend([d[i][0] - k1, d[i][0] - k1 + 1, d[i][0], d[i][0] + 1])
    check_y.extend([d[i][1] - k1, d[i][1] - k1 + 1, d[i][1], d[i][1] + 1])
check_x = list(set(check_x))
check_y = list(set(check_y))

#d = tuple(d)
n = 0
#t = time.clock()
for i in check_x:
    for j in check_y:
        n_tmp = [0, 0]
        for k in range(n1):
            x = (d[k][0] - i) // k1 % 2
            y = (d[k][1] - j) // k1 % 2
#            if x == y:
#                n_tmp[1 - d[k][2]] += 1
#            else:
#                n_tmp[d[k][2]] += 1
            n_tmp[(x == y) ^ d[k][2]] += 1
        if n_tmp[0] > n:
            n = n_tmp[0]
        if n_tmp[1] > n:
            n = n_tmp[1]
#print time.clock() - t
print n


### FIXED CODE ###

import numpy as np

def getBoundary(p, k, k2):
    if p - k + 1 >= 0:
        return [(p - k + 1, p + 1)]
    else:
        return [(0, p + 1), ((p - k + 1) % k2, k2)]

n, k = map(int, input().strip().split())
k2 = k * 2
b = [[0 for i in range(k2 + 1)] for j in range(k2 + 1)]

for i in range(n):
    x_str, y_str, c_str = input().strip().split()
    x = int(x_str) % k2
    y = (int(y_str) + (c_str == 'B') * k) % k2
    for xb, xe in getBoundary(x % k2, k, k2):
        for yb, ye in getBoundary(y % k2, k, k2):
            b[xb][yb] += 1
            b[xb][ye] -= 1
            b[xe][yb] -= 1
            b[xe][ye] += 1
    for xb, xe in getBoundary((x + k) % k2, k, k2):
        for yb, ye in getBoundary((y + k) % k2, k, k2):
            b[xb][yb] += 1
            b[xb][ye] -= 1
            b[xe][yb] -= 1
            b[xe][ye] += 1

arr_b = np.array(b)
for i in range(k2):
    arr_b[i + 1] += arr_b[i]
for j in range(k2):
    arr_b[:, j + 1] += arr_b[:, j]
print(arr_b.max())
### BUGGY CODE ###


def q3():
    import math
    k = int(input())
    sum_n = 0
    gcd_2_dict = {}

    def gcd(n1, n2):
        key = tuple([n1, n2])
        if key in gcd_2_dict:
            return gcd_2_dict[key]
        gcd_num = math.gcd(n1, n2)
        gcd_2_dict[key] = gcd_num
        return gcd_num

    import time
    for a in range(1, k + 1):
        for b in range(1, k + 1):
            for c in range(1, k + 1):
                l = [a, b, c]
                l.sort()
                sum_n += gcd(gcd(l[0], l[1]), l[2])

    print(sum_n)

q3()

### FIXED CODE ###


from math import gcd

K = int(input())

a = 0
for ai in range(1, K + 1):
  for bi in range(1, K + 1):
    gcd_ab = gcd(ai, bi)
    for ci in range(1, K + 1):
      a += gcd(gcd_ab, ci)

print(a)
### BUGGY CODE ###

#! /usr/bin/env python3
def main():
    H, W = map(int, input().split())
    CH, CW = map(int, input().split())
    DH, DW = map(int, input().split())
    G = []
    for i in range(H):
        G += [[[0,1][x=='#']for x in input()]]

    dx = [0, 1, 0, -1]
    dy = [-1, 0, 1, 0]


    dy2 = []
    dx2 = []
    for y in range(-2,3):
        for x in range(-2,3):
            if abs(y)+abs(x) > 1:
                dy2 += [y]
                dx2 += [x]
    dl = len(dx2)

    q = [(CH-1, CW-1)]
    a = [(CH-1, CW-1)]
    f = True
    c = 0
    ans = -1
    while f:
        f = False
        while q:
            t = []
            for y, x in q:
                G[y][x] = 2
                for d in range(4):
                    px = x + dx[d]
                    py = y + dy[d]
                    if 0<=px<W and 0<=py<H and G[py][px] == 0:
                        G[py][px] = 2
                        t += [(py, px)]
                        a += [(py, px)]
            q = t
        b = []
        s = set()
        for y, x in a:
            for d in range(dl):
                px = x + dx2[d]
                py = y + dy2[d]
                if 0<=px<W and 0<=py<H and G[py][px] == 0 and (py,px) not in s:
                    s.add((py,px))
                    b += [(py, px)]
                    q += [(py, px)]
        # for i in G:
        #     print(i)
        # print()
        if G[DH-1][DW-1] == 2:
            ans = c
            break
        c += 1
        a = b
        if b : f = True
        
    print(ans)

main()

### FIXED CODE ###

#! /usr/bin/env python3
def main():
    H, W = map(int, input().split())
    CH, CW = map(int, input().split())
    DH, DW = map(int, input().split())
    G = []
    for i in range(H):
        G += [[[0,1][x=='#']for x in input()]]

    dx = [0, 1, 0, -1]
    dy = [-1, 0, 1, 0]


    dy2 = []
    dx2 = []
    for y in range(-2,3):
        for x in range(-2,3):
            if abs(y)+abs(x) > 1:
                dy2 += [y]
                dx2 += [x]
    dl = len(dx2)

    q = [(CH-1, CW-1)]
    a = [(CH-1, CW-1)]
    f = True
    c = 0
    ans = -1
    while f:
        f = False
        while q:
            t = []
            for y, x in q:
                G[y][x] = 2
                for d in range(4):
                    px = x + dx[d]
                    py = y + dy[d]
                    if 0<=px<W and 0<=py<H and G[py][px] == 0:
                        G[py][px] = 2
                        t += [(py, px)]
                        a += [(py, px)]
            q = t
        b = []
        s = set()
        for y, x in a:
            for d in range(dl):
                px = x + dx2[d]
                py = y + dy2[d]
                if 0<=px<W and 0<=py<H and G[py][px] == 0 and (py,px) not in s:
                    s.add((py,px))
                    b += [(py, px)]
                    q += [(py, px)]
        # for i in G:
        #     print(i)
        # print()
        if G[DH-1][DW-1] == 2:
            ans = c
            break
        c += 1
        a = b
        if b : f = True
        
    print(ans)

main()
### BUGGY CODE ###

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

s = 0


c = 1


for i in range(k+1):
    if i > 0:
        c = c * (n-i) // i
    s += c * m * ((m-1) ** (n-1-i))

print(s % 998244353)


### FIXED CODE ###

import math

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

MOD=998244353

fact = [0] * (n+1)
inv = [0] * (n+1)
factinv = [0] * (n+1)

fact[0]=fact[1]=1
inv[1]=1
factinv[0]=factinv[1]=1

for i in range(2,n+1):
    fact[i] = fact[i-1] * i % MOD
    inv[i] = MOD - (( inv[MOD % i] *  (MOD // i)) % MOD )
    factinv[i] = factinv[i-1] * inv[i] % MOD

def cbn(n, k, fact, factinv, MOD):
    return fact[n] * factinv[n-k] * factinv[k] % MOD

def power(x, n, MOD):
    if n == 0:
        return 1
    elif n % 2 == 0:
        return power(x*x % MOD , n // 2, MOD) % MOD
    else:
        return x * power(x * x % MOD, n // 2, MOD) % MOD

s = 0
for i in range(k+1):
    s += cbn(n-1, i, fact, factinv, MOD) * m * power(m-1, n-1-i, MOD)

print(s % MOD)
### BUGGY CODE ###

from collections import deque
import sys
input = sys.stdin.readline

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

f_inf = float('inf')
visited = [[f_inf] * w for _ in range(h)]
que = deque([])
for i in range(h):
    for j in range(w):
        if map[i][j] == "#":
            visited[i][j] = 0
            que.append((i, j))

ans = 0
while que:
    y, x = que.popleft()
    for i, j in ((1, 0), (-1, 0), (0, 1), (0, -1)):
        next_y, next_x = y + i, x + j
        ans = visited[y][x]
        if -1 < next_y < h and -1 < next_x < w and visited[next_y][next_x] == f_inf:
            visited[next_y][next_x] = visited[y][x] + 1
            que.append((next_y, next_x))

print(int(ans))

### FIXED CODE ###

from collections import deque

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

cnt = [[-1]*W for _ in range(H)]

que = deque()
for h in range(H):
    for w in range(W):
        if grid[h][w] == '#':
            que.append((h, w))
            cnt[h][w] = 0

ans = 0
while que:
    h, w = que.popleft()
    ans = cnt[h][w]
    for dy, dx in ((1, 0), (0, 1), (-1, 0), (0, -1)):
        next_h = h + dy
        next_w = w + dx
        if next_h < 0 or H <= next_h or next_w < 0 or W <= next_w:
            continue
        if cnt[next_h][next_w] == -1:
            cnt[next_h][next_w] = ans+1
            que.append((next_h, next_w))

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

import fractions as f

N = int(input())

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

rightGCD = []
leftGCD = []

rightGCD.append(0)
tmp = 0
for x in A[:-1:]:
    tmp = f.gcd(tmp,x)
    rightGCD.append(tmp)

leftGCD.insert(0,0)
tmp = 0
for x in A[:0:-1]:
    tmp = f.gcd(tmp,x)
    leftGCD.insert(0,tmp)

#print(leftGCD)
#print(rightGCD)

ans = 0

for i in range(N):
    if i==0:
        ans = max(ans,leftGCD[i])
        continue
    if i==N-1:
        ans = max(ans,rightGCD[i])
        continue

    ans = max(ans,f.gcd(rightGCD[i],leftGCD[i]))

print(ans)


### FIXED CODE ###

import fractions as f

N = int(input())

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

rightGCD = [0]*N
leftGCD = [0]*N

for i in range(N-1):
    leftGCD[i+1] = f.gcd(leftGCD[i],A[i])
    rightGCD[-i-2] = f.gcd(rightGCD[-i-1],A[-i-1])

#print(leftGCD)
#print(rightGCD)

ans = 0

for i in range(N):
    ans = max(ans,f.gcd(rightGCD[i],leftGCD[i]))

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

import numpy as np

N,M = map(int,input().split())
A = np.sort(list(map(int,input().split())))
ans = 0

xOK = A[0]*2
xNG = A[-1]*2 + 1
nx = 0
while xOK+1 < xNG:
    x = (xOK + xNG)//2
    nx = 0
    for a in A:
        nx += N-(np.searchsorted(A,x-a))
        if nx >= M:
            xOK = x
            break
    else:
        xNG = x

from itertools import accumulate
S=[0]+list(accumulate(A))

ans = 0
nnx = 0        
for a in A:
    nx = np.searchsorted(A,xOK-a,side='right')
    ans += a*(N-nx) + (S[N]-S[nx])
    nnx += (N-nx)
ans += xOK*(M-nnx)
        
    
print(ans)

### FIXED CODE ###

import bisect 
from itertools import accumulate

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

xOK = A[0]*2
xNG = A[-1]*2 + 1
nx = 0
while xOK+1 < xNG:
    x = (xOK + xNG)//2
    nx = 0
    for a in A:
        nx += N-(bisect.bisect_left(A,x-a))
        if nx >= M:
            xOK = x
            break
    else:
        xNG = x

S=[0]+list(accumulate(A))

ans = 0
nnx = 0        
for a in A:
    nx = bisect.bisect_right(A,xOK-a)
    ans += a*(N-nx) + (S[N]-S[nx])
    nnx += (N-nx)
ans += xOK*(M-nnx)
        
    
print(ans)
### BUGGY CODE ###

n=int(input())
a_list=[int(i) for i in input().split(' ')]

[print(a_list.count(i+1)) for i in range(n-1)]
print(0)

### FIXED CODE ###

n=int(input())
a_list=[int(i) for i in input().split(' ')]

import collections

c = collections.Counter(a_list)
[print(c[i+1]) for i in range(n)]
### BUGGY CODE ###

import sys
K = input()
if K[-1] == '2' or K[-1] == '4' or K[-1] == '5' or K[-1] == '6' or K[-1] == '8' or K[-1] == '0':
    print(-1)
    sys.exit()
if K[-1] == '1':
    i = 7
elif K[-1] == '3':
    i = 9
elif K[-1] == '7':
    i = 1
elif K[-1] == '9':
    i = 3
K = int(K)
while True:
    N = K * i
    n = set(str(N))
    if n == {'7'}:
        N = str(N)
        print(len(N))
        sys.exit()
    i += 10

### FIXED CODE ###

import sys
K = input()
if K[-1] == '2' or K[-1] == '4' or K[-1] == '5' or K[-1] == '6' or K[-1] == '8' or K[-1] == '0':
    print(-1)
    sys.exit()
K = int(K)
n = 7 % K
i = 1
while i <= K:
    if n == 0:
        print(i)
        sys.exit()
    n = 10 * n + 7
    n %= K
    i += 1
print(-1)
### BUGGY CODE ###

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

arr = []
for x in a:
    arr.append(x)
    arr.reverse()

print(*arr)


### FIXED CODE ###

from collections import deque

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

d = deque()
for i in range(n):
    if i % 2 != 0:
        d.append(a[i])
    else:
        d.appendleft(a[i])

if n % 2 == 0:
    print(*list(reversed(d)))
else:
    print(*d)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

R,C,K=list(map(int,input().split()))
itemMap = [[0]*(C+1) for _ in range(R+1)]
dp =[[[0]*(4) for _ in range(C+1)] for _ in range(R+1)]

for _ in range(K):
    r,c,v=list(map(int,input().split()))
    itemMap[r-1][c-1]=v

for ir in range(R):
    for ic in range(C):
        for k in range(2,-1,-1):
            #-拾う拾わない遷移-#
            dp[ir][ic][k+1] = max(dp[ir][ic][k+1],dp[ir][ic][k]+itemMap[ir][ic])
        #-位置遷移-#
        for k in range(4):
            dp[ir+1][ic][0] = max(dp[ir+1][ic][0],dp[ir][ic][k])
            dp[ir][ic+1][k] = max(dp [ir][ic+1][k],dp[ir][ic][k])

ans = 0
for k in range(4):
    ans = max(ans,dp[R-1][C-1][k])
print(ans)
                            
                        


### FIXED CODE ###

import sys
input = sys.stdin.readline

R,C,K=list(map(int,input().split()))
itemMap = [[0]*(C+1) for _ in range(R+1)]
dp =[[[0]*(C+1) for _ in range(R+1)] for _ in range(4)]

for _ in range(K):
    r,c,v=list(map(int,input().split()))
    itemMap[r-1][c-1]=v

for ir in range(R):
    for ic in range(C):
        for k in range(2,-1,-1):
            #-拾う拾わない遷移-#
            dp[k+1][ir][ic] = max(dp[k+1][ir][ic],dp[k][ir][ic]+itemMap[ir][ic])
        #-位置遷移-#
        for k in range(4):
            dp[0][ir+1][ic] = max(dp[0][ir+1][ic],dp[k][ir][ic])
            dp[k][ir][ic+1] = max(dp[k][ir][ic+1],dp[k][ir][ic])

ans = 0
for k in range(4):
    ans = max(ans,dp[k][R-1][C-1])
print(ans)
### BUGGY CODE ###

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

steps = [int(i) for i in input().split()]
dp = [9999999] * n

dp[0] = 0

for i in range(1, n):
    start = max(0, i-k)
    dp[i] = min([dp[j] + abs(steps[i] - steps[j]) for j in range(start, i)])

print(dp[n - 1])

### FIXED CODE ###

import numpy as np
 
 
N, K = map(int, input().split())
inputs = np.array([int(i) for i in input().split()])
 
dp = np.zeros(N, dtype=int)
for i in range(1, N):
    start = max(0, i-K)
    dp[i] = (dp[start:i] + abs(inputs[i] - inputs[start:i])).min()
 
print(dp[-1])