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

# coding: utf8

if __name__ == '__main__':
    """
        (A, B)と(A+1, B+1)の結果は同じになる.
        (0, 0), (0, 1) ... (0, N-1)をチェックすれば良くなる.
    """
    N = int(input())
    rows = [input() for _ in range(N)]
    ans = 0
    for n in range(N):
        flag = False
        for i in range(N):
            for j in range(N):
                num = j - n if j - n >= 0 else N + (j - n)
                a = i - n if i - n >= 0 else N + (i - n)
                if rows[i][num] != rows[j][a]:
                    flag = True
                    break
            if flag == True:
                break
        if flag == False:
            ans += 1
    print(ans * N)



### FIXED CODE ###

# coding: utf8

if __name__ == '__main_sample__':
    """
        (A, B)と(A+1, B+1)の結果は同じになる.
        (0, 0), (0, 1) ... (0, N-1)をチェックすれば良くなる.
    """
    N = int(input())
    rows = [input() for _ in range(N)]
    ans = 0
    for n in range(N):
        flag = False
        for i in range(N):
            for j in range(N):
                num = j - n if j - n >= 0 else N + (j - n)
                a = i - n if i - n >= 0 else N + (i - n)
                if rows[i][num] != rows[j][a]:
                    flag = True
                    break
            if flag == True:
                break
        if flag == False:
            ans += 1
    print(ans * N)

if __name__ == '__main__':
    """
        高速化された開放
    """
    N = int(input())
    Sss = [input() for _ in range(N)]
    Sss_tr = list(map(''.join, zip(*Sss))) # 転置
    ans = 0
    for k in range(N):
        for i in range(N):
            if (Sss[i][-k:] + Sss[i][:-k]) != Sss_tr[i - k]:
                break
        else:
            ans += N
    
    print(ans)
### BUGGY CODE ###

N = int(input())
ans = 0
for i in range(N):
  ans += i
print(ans)

### FIXED CODE ###

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

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

    ans = 0
    from collections import Counter
    cnt = Counter(a)
    tmp = [0] * (max(a) + 1)
    # set_a = list(set(a))
    # set_a.sort()
    a.sort()
    for aa in a:
        if tmp[aa] == 0:
            for j in range(aa,max(a)+1,aa):
                tmp[j] = 1

            if cnt[aa] == 1:
                # print(aa, ans)
                ans += 1




    print(ans)

if __name__=='__main__':
    main()


### FIXED CODE ###

from collections import Counter
import bisect
N = int(input())
A = list(map(int,input().split()))
cnt = Counter(A)
A.sort()
ans = 0
MX = 10**6
P = [0] * (MX+1)
for a in A:
    if P[a]==0:
        for i in range(MX+1):
            x = a*i
            if x > MX:
                break
            P[x] = 1
        if cnt[a]==1:
            ans+=1
print (ans)
### BUGGY CODE ###

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

count = 0
for i in range(1, n + 1):
	for a in A:
		if i == a:
			count += 1
	print(count)
	count = 0


### FIXED CODE ###

from collections import Counter

n = int(input())
A = list(map(int, input().split()))
C = Counter(A)

for i in range(1, n + 1):
	print(C[i])
### BUGGY CODE ###


s = input()
t = input()

#dp[i][j] => s[i], t[j]までの最長部分文字列

dp = [[""] *(len(t) + 1) for j in range(len(s) + 1)]
for i in range(1,len(s)+1):
    for j in range(1,len(t)+1):
        if s[i - 1] == t[j - 1]:
            dp[i][j] = "".join(dp[i - 1][j] + s[i - 1])
        else:
            #上か左の長いほうを入れる
            if len(dp[i][j-1]) < len(dp[i-1][j]):
                dp[i][j] = dp[i - 1][j]
            else:
                dp[i][j] = dp[i][j - 1]
print(dp[-1][-1])


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**5)
s = input()
t = input()

#dp[i][j] => s[i], t[j]までの最長部分文字列

dp = [[0] * (len(t) + 1) for j in range(len(s) + 1)]
for i in range(1,len(s)+1):
    for j in range(1,len(t)+1):
        if s[i-1] == t[j-1]:
            x = 1
        else:
            x = 0
        dp[i][j] = max(dp[i-1][j-1] + x, dp[i-1][j], dp[i][j-1])


def make_ans(a, b):
    if a ==  0 or b == 0:
        return 
    if s[a-1] == t[b-1]:
        make_ans(a-1,b-1)
        ans.append(s[a-1])
    else:
        if a == 0:
            make_ans(a, b - 1)
        elif b == 0:
            make_ans(a - 1,b)
        else:
            if dp[a - 1][b] > dp[a][b - 1]:
                make_ans(a-1,b)
            else:
                make_ans(a,b-1)

ans = []
make_ans(len(s),len(t))
print("".join(ans))
### BUGGY CODE ###

import sys

input = sys.stdin.readline
n = int(input())
sl = list(input())[:-1]

q = int(input())
kl = list(map(int,input().split()))

for k in kl:
    # i文字目までのdとmとdmの数
    d = 0
    m = 0
    dm = 0
    ans = 0
    for i, s in enumerate(sl):
        if i - k >= 0:
            if sl[i-k] == "D":
                d -= 1
                dm -= m
            if sl[i-k] == "M":
                m -= 1
        if s == "D":
            d += 1
        if s == "M":
            m += 1
            dm += d
        if s == "C":
            ans += dm

    print(ans)









### FIXED CODE ###

import sys
input = sys.stdin.readline

def main():
    N = int(input())
    S = input()
    Q = int(input())
    x = tuple(map(int,input().split()))
    for k in x:
        d,m,dm,dmc = 0,0,0,0
        for i in range(N):
            if S[i] == "D":
                d += 1
            elif S[i] == "M":
                m += 1
                dm += d
            elif S[i] == "C":
                dmc += dm
            if i >= k-1:
                if S[i-k+1] == "D":
                    dm -= m
                    d -= 1
                elif S[i-k+1] == "M":
                    m -= 1
        print(dmc)
    
if __name__ == "__main__":
    main()
### BUGGY CODE ###

def main():
    n = int(input())
    s = list(input())
    count = {"G": 0, "R":0, "B":0}
    for i in s:
        count[i] += 1
    ans = count["G"]*count["R"]*count["B"]
    for j in range(n):
        for i in range(1, n//2+1):
            if j+2*i > n-1:
                continue
            if len(set([s[j], s[j+i], s[j+2*i]])) == 3:
                ans -= 1
    print(ans)
    
    

if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
    n = int(input())
    s = list(input())
    ss = list(sorted(list(set(s))))
    s_sorted = list(sorted(s))
    if len(ss) < 3:
        print(0)
        return
    m = n-1
    sn = [0]*3
    j = 0
    flag = False
    for i, si in enumerate(ss):
        while s_sorted[j] == si:
            sn[i] += 1
            if j == m:
                flag = True
                break
            j += 1
        if flag:
            break
    ans = sn[0]*sn[1]*sn[2]
    for d in range(1, n//2+1):
        i = 0
        d2 = 2*d
        ma = n-d2
        while i < ma:
            si, sj, sk = s[i], s[i+d], s[i+d2]
            if si != sj and sj != sk and si != sk:
                ans -= 1
            i += 1
    print(ans)
                

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

n = input()
array = []
x = 1
while x <= n:
    if x % 3 == 0:
        array.append(x)
    else:
        while x != 0:
            if x % 10 == 3:
                array.append(x)
                break
            x /= 10
    x += 1
print str(array).replace('[', ' ').replace(']', '').replace(',', '')

### FIXED CODE ###

n = input()
array = []
i = 1
while i <= n:
    x = i
    if x % 3 == 0:
        array.append(i)
    else:
        while x != 0:
            if x % 10 == 3:
                array.append(i)
                break
            x /= 10
    i += 1
print str(array).replace('[', ' ').replace(']', '').replace(',', '')
### BUGGY CODE ###

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

### FIXED CODE ###

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

N = int(input())
P = [int(i) for i in input().split(" ")]

ans = 0
for L in range(N-1):
    for R in range(L+1, N):
        if 2 <= len(P[L:R+1]) <= 3:
            seq = sorted(P[L:R+1], reverse=True)
        else:
            if seq[0] > P[R] > seq[1]:
                seq = [seq[0], P[R], seq[1]]
            elif P[R] > seq[0]:
                seq = [P[R], seq[0], seq[1]]
            elif seq[1] > P[R] > seq[2]:
                seq = [seq[0], seq[1], P[R]]
        ans += seq[1]
print(ans)

### FIXED CODE ###

N = int(input())
P = [int(i) for i in input().split(" ")]

# 各数字が何番目に入っているかを保存する
pos = [0] * (N + 1)
for i in range(N):
    pos[P[i]] = i + 1

l = [0]+[i for i in range(N + 1)]
r = [i + 1 for i in range(N + 1)] + [N + 1]

# 1から順番に見ていく
ans = 0
for i in range(1, N + 1):
    idx = pos[i]
    l1, r1 = l[idx], r[idx]
    l2, r2 = l[l1], r[r1]
    ans += i * ((l1 - l2) * (r1 - idx) + (idx - l1) * (r2 - r1))
    l[r1], r[l1] = l1, r1
print(ans)
### BUGGY CODE ###

# Good Sequence
n = int(input())
a = list(map(int, input().split()))
a_ = set(a)
p = 0
for i in a_:
    if a.count(i) < i:
        p += a.count(i)
    elif a.count(i) > i:
        p += a.count(i) - i
print(p)


### FIXED CODE ###

# Good Sequence
n = int(input())
a = list(map(int, input().split()))
count = {}
ans = 0
for i in a:
    if i not in count:
        count[i] = 1
    else:
        count[i] += 1
for i, c in count.items():
    if i > c:
        ans += c
    elif i < c:
        ans += c - i
print(ans)
### BUGGY CODE ###

def top(L, node):
    current = node
    while L[current] != current:
        current = L[current]
    return current


def main():
    n, m = map(int, input().rstrip("\n").split(" "))

    L = [0]
    counts = {}
    for i in range(1, n + 1):
        L.append(i)
        counts[i] = 1

    edges = []
    for j in range(m):
        a_b = map(int, input().rstrip("\n").split(" "))
        edges.append(a_b)

    total = n * (n - 1) // 2

    answers = [total]
    for a, b in reversed(edges):
        a_top = top(L, a)
        b_top = top(L, b)
        if a_top == b_top:
            answers.append(total)
        else:
            total -= counts[a_top] * counts[b_top]
            answers.append(total)
            L[b_top] = a_top
            counts[a_top] += counts[b_top]


    for answer in reversed(answers[:-1]):
        print(answer)

if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    n, m = map(int, input().rstrip("\n").split(" "))

    L = [0]
    counts = {}
    for i in range(1, n + 1):
        L.append(i)
        counts[i] = 1

    edges = []
    for j in range(m):
        a_b = map(int, input().rstrip("\n").split(" "))
        edges.append(a_b)

    total = n * (n - 1) // 2

    answers = [total]
    for a, b in reversed(edges):
        current = a
        while L[current] != current:
            current = L[current]
        a_top = current
        current = b
        while L[current] != current:
            current = L[current]
        b_top = current
        if a_top == b_top:
            answers.append(total)
        else:
            total -= counts[a_top] * counts[b_top]
            answers.append(total)
            L[b_top] = a_top
            L[b] = a_top
            L[a] = a_top
            counts[a_top] += counts[b_top]

    for answer in reversed(answers[:-1]):
        print(answer)

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

N, K, Q = map(int, input().split())
A = []
for i in range(Q):
  A.append(int(input()))

P = [K for i in range(N)]


for i in range(Q):
  for j in range(N):
    if j != A[i] - 1:
      P[j] = P[j] - 1
      

for i in range(N):
  if (P[i] < 1):
    print("No")
  else:
    print("Yes")

### FIXED CODE ###

N, K, Q = map(int, input().split())
A = []
for i in range(Q):
  A.append(int(input()))

P = [0 for i in range(N)]


for i in range(Q):
    P[A[i] - 1] = P[A[i] - 1] + 1
      

for i in range(N):
  if (Q - P[i] >= K ):
    print("No")
  else:
    print("Yes")
### BUGGY CODE ###

n, m = map(int,input().split())
a = list(map(int,input().split()))
list.sort(a,reverse=True)
ans = 0

kouho = [[0,0]]
for i in range(m):
    max = 0
    m0 = -1
    m1 = -1
    for j in kouho:
        if a[j[0]]+a[j[1]] > max:
            max = a[j[0]]+a[j[1]]
            m0 = j[0]
            m1 = j[1]
    ans += max
    kouho.remove([m0,m1])
    if m0 < n-1 and (not [m0+1,m1] in kouho):
        kouho.append([m0+1,m1])
    if m1 < n-1 and (not [m0,m1+1] in kouho):
        kouho.append([m0,m1+1])

print(ans)


### FIXED CODE ###

import math
#import numpy as np
import queue
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    n,m = map(int,ipt().split())
    a = [int(i) for i in ipt().split()]
    a.sort()
    maa = max(a)

    pn = [0]*(2*maa+1)
    pn[0] = n
    pa = 0
    for i in a:
        for j in range(pa+1,i+1):
            pn[j] = pn[pa]
        pn[i+1] = pn[pa]-1
        pa = i+1

    l = 0
    r = 2*maa
    while l < r:
        mid = l+(r-l+1)//2
        nm = 0
        for i in a:
            if mid <= i:
                nm += n
            else:
                nm += pn[mid-i]
        if nm >= m:
            l = mid
        else:
            r = mid-1

    pt = [0]*(2*maa+1)
    pp = maa+1
    for i in a[::-1]:
        for j in range(pp-1,i,-1):
            pt[j] = pt[pp]
        pt[i] = pt[pp]+i
        pp = i
    for j in range(pp-1,-1,-1):
        pt[j] = pt[pp]

    ans = 0
    sm = 0
    for i in a:
        sm += pn[max(0,l-i)]
        ans += pt[max(0,l-i)]+pn[max(0,l-i)]*i
    print(ans-l*(sm-m))
    return

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

#172D
#Sum of Divisors

n=int(input())
ans=0

for i in range(1,n+1):
    j=1
    while i*j<=n:
        ans+=i*j
        j+=1
print(ans)

### FIXED CODE ###

#172D
#Sum of Divisors

n=int(input())
ans=0

for i in range(1,n+1):
    j=n//i
    ans+=j*(j+1)*i/2
print(int(ans))
### BUGGY CODE ###

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

AK = A+K-1
BK = B-K+1
for i in range(A,B+1):
  if i >= A and i <= AK:
    print(i)
  elif i >= BK and i <= B:
    print(i)

### FIXED CODE ###

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

AK = A+K-1
BK = B-K+1
for i in range(A,A+K):
  if i <= B:
    if i >= A and i <= AK:
      print(i)
for i in range(BK,B+1): 
  if (i <= AK)!=1:
    if i >= BK and i <= B:
      print(i)
### BUGGY CODE ###

N = int(input())
A = [0] * (N+1)

for i in range(1, N+1):
    A[i] = int(input())

sorted_A = sorted(A)

cnt = 0
for i in range(1, N+1):
    ind = sorted_A.index(A[i])
    if ind % 2 != i % 2:
        cnt += 1

print(cnt // 2)


### FIXED CODE ###

N = int(input())
A = [0] * (N+1)

for i in range(1, N+1):
    A[i] = int(input())

sorted_A = sorted(A)
sorted_dict_A = { sorted_A[i]: i for i in range(1, N+1) }

cnt = 0
for i in range(1, N+1):
    ind = sorted_dict_A[A[i]]
    if ind % 2 != i % 2:
        cnt += 1

print(cnt // 2)
### BUGGY CODE ###

import sys

sys.setrecursionlimit(10**9)

def dfs(now, prev):
    ans[now]+=(h[now]+ans[prev])
    # 今いる頂点から行ける頂点を順に next に入れてループ
    for next in g[now]:
        if next != prev:
            if memo[next]==True:
                # 過去に訪れていれば終わらせる
                return False
            else:
                memo[next] = True
                dfs(next, now)


n, q = map(int, input().split())
g = [[] * n for i in range(n)]
for i in range(n-1):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    g[u].append(v)
    g[v].append(u)

h=[0]*n
for i in range(q):
    u, v = map(int, input().split())
    u -= 1
    h[u]+=v

ans=[0]*n
memo = [False for i in range(n)]
dfs(0,0)

print(' '.join(map(str, ans)))

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

def dfs(now, prev):
    ans[now]+=(h[now]+ans[prev])
    # 今いる頂点から行ける頂点を順に next に入れてループ
    for next in g[now]:
        if next != prev:
            if memo[next]==True:
                # 過去に訪れていれば終わらせる
                return False
            else:
                memo[next] = True
                dfs(next, now)
 
#木構造の取り込み 
n, q = map(int, input().split())
g = [[] * n for i in range(n)]
for i in range(n-1):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    g[u].append(v)
    g[v].append(u)
 
#操作の取り込み
h=[0]*n
for i in range(q):
    u, v = map(int, input().split())
    u -= 1
    h[u]+=v
 
#初期のカウンター
ans=[0]*n
memo = [False for i in range(n)]
 
#DFSでカウンターを動かす
dfs(0,0)
 
print(' '.join(map(str, ans)))
### BUGGY CODE ###

n = int(input())
a = input()
a2 = [int(a[i]) for i in range(n)]
n2 = bin(n)
b = [0] * n
c = [1] * (2 ** (len(n2) - 3))
for i in range(len(c)):
    b[i] += c[i]
temp = len(n2) - 4
count = len(c)
while temp>= 0:
    if n2[-1-temp] == "1":
        c = [b[i] for i in range(count)]
        for i in range(count):
            b[i + 2 ** temp] += c[i]
        count += 2 ** temp
    temp -= 1
e = [b[i] % 2 for i in range(len(b))]
d = 0
for i in range(n):
    if e[i] % 2 == 1:
        d += a2[i]
if d % 2 == 1:
    print(1)
else:
    a3 = [abs(a2[i] - a2[i + 1]) for i in range(n - 1)]
    if 1 in a3:
        print(0)
    else:
        n3 = bin(n - 1)
        b = [0] * (n - 1)
        c = [1] * (2 ** (len(n3) - 3))
        for i in range(len(c)):
            b[i] += c[i]
        temp = len(n3) - 4
        count = len(c)
        while temp>= 0:
            if n3[-1-temp] == "1":
                c = [b[i] for i in range(count)]
                for i in range(count):
                    b[i + 2 ** temp] += c[i]
                count += 2 ** temp
            temp -= 1
        e = [b[i] % 2 for i in range(len(b))]
        d = 0
        for i in range(n - 1):
            if e[i] % 2 == 1:
                d += a3[i]
        if d % 4 == 0:
            print(0)
        else:
            print(2)

### FIXED CODE ###

n = int(input())
a = input()
a2 = [int(a[i]) for i in range(n)]
n2 = bin(n)
b = [0] * n
c = [1] * (2 ** (len(n2) - 3))
for i in range(len(c)):
    b[i] += c[i]
temp = len(n2) - 4
count = len(c)
while temp>= 0:
    if n2[-1-temp] == "1":
        c = [b[i] for i in range(count)]
        for i in range(count):
            b[i + 2 ** temp] += c[i]
        count += 2 ** temp
    temp -= 1
e = [b[i] % 2 for i in range(len(b))]
d = 0
for i in range(n):
    if e[i] % 2 == 1:
        d += a2[i]
if d % 2 == 1:
    print(1)
else:
    a3 = [abs(a2[i] - a2[i + 1]) for i in range(n - 1)]
    if 1 in a3:
        print(0)
    else:
        n3 = bin(n - 1)
        b = [0] * (n - 1)
        c = [1] * (2 ** (len(n3) - 3))
        for i in range(len(c)):
            b[i] += c[i]
        temp = len(n3) - 4
        count = len(c)
        while temp>= 0:
            if n3[-1-temp] == "1":
                c = [b[i] for i in range(count)]
                for i in range(count):
                    b[i + 2 ** temp] += c[i]
                count += 2 ** temp
            temp -= 1
        e = [b[i] % 2 for i in range(len(b))]
        d = 0
        for i in range(n - 1):
            if e[i] % 2 == 1:
                d += a3[i]
        if d % 4 == 0:
            print(0)
        else:
            print(2)
### BUGGY CODE ###

n, m = map(int, input().split(' '))
s = [list(map(int, input().split(' '))) for _ in range(m)]

dic = [x for x in range(n)]
result = [int(n*(n-1)/2)]
for i in range(1,m):
    if dic[s[-1*i][0]-1] == dic[s[-1*i][1]-1]:
        result.append(result[-1])
    else:
#        p = [x for x in dic if x == dic[s[-1*i][0]-1]]
#        q = [x for x in dic if x == dic[s[-1*i][1]-1]]
        p = dic.count(dic[s[-1*i][0]-1])
        q = dic.count(dic[s[-1*i][1]-1])
        result.append(result[-1]-p*q)
        dic = [dic[s[-1*i][1]-1] if x == dic[s[-1*i][0]-1] else x for x in dic]
for i in range(1,m+1):
    print(result[-1*i])

### FIXED CODE ###

n, m = map(int, input().split(' '))
a = [0]*m
b = [0]*m
for i in range(m):
    a[i], b[i] = list(map(int, input().split(' ')))

c = [-1]*(m+2)

def find(num):
    if c[num] < 0:
        return num
    else:
        k = find(c[num])
        c[num] = k
        return k

result = [int(n*(n-1)/2)]
for i in range(m-1, 0,-1):
    x = find(a[i])
    y = find(b[i])

    if x != y:
        result.append(result[-1]-c[x]*c[y])
        x, y = sorted([x,y])
        c[x] += c[y]
        c[y] = x
    else:
        result.append(result[-1])

for i in result[::-1]:
    print(int(i))
### BUGGY CODE ###

import numpy as np
n,w = map(int,input().split())
w_i = [0]
v_i = [0]
for i in range(n):
  temp = list(map(int,input().split()))
  w_i.append(temp[0])
  v_i.append(temp[1])

dp = np.zeros(((n+1),(w+1)))

for i in range(1,n+1):
#  print(dp)
  for j in range(w+1):
    temp_1 = -float("inf")
    if j-w_i[i] >= 0:
      temp_1 = dp[i-1][j-w_i[i]] + v_i[i]
    
    temp_2 = dp[i-1][j]
    
    if temp_1 <= temp_2:
      dp[i][j] = temp_2
    elif temp_2 < temp_1:
      dp[i][j] = temp_1
      
print(int(dp[n][w]))

### FIXED CODE ###

n,w = map(int,input().split())
w_i = [0]
v_i = [0]
for i in range(n):
  temp = list(map(int,input().split()))
  w_i.append(temp[0])
  v_i.append(temp[1])

dp = []
for i in range(n+1):
  temp = []
  for j in range(w+1):
    temp.append(0)
  
  dp.append(temp)

for i in range(1,n+1):
#  print(dp)
  for j in range(w+1):
    temp_1 = -float("inf")
    if j-w_i[i] >= 0:
      temp_1 = dp[i-1][j-w_i[i]] + v_i[i]
    
    temp_2 = dp[i-1][j]
    
    if temp_1 <= temp_2:
      dp[i][j] = temp_2
    elif temp_2 < temp_1:
      dp[i][j] = temp_1
      
print(dp[n][w])
### BUGGY CODE ###

import numpy as np
from itertools import chain
 
n, m = map(int, input().split())
A = list(map(int, input().split()))
bc = [list(map(int, input().split())) for _ in range(m)]
 
A.sort()
bc.sort(reverse=True, key=lambda x: x[1])
C = list(chain(*[[c]*b for b, c in bc]))
threshold = np.count_nonzero((np.array(C[:len(A)]) - np.array(A[:len(C)])) > 0)
 
print(sum(C[:threshold]) + sum(A[threshold:]))

### FIXED CODE ###

n, m = map(int, input().split())
a = list(map(int, input().split()))
bc = [list(map(int, input().split())) for _ in range(m)]

a.sort()
bc.sort(reverse=True, key=lambda x: x[1])
j = 0
for i in range(m):
    while j < len(a) and bc[i][0] > 0:
        if a[j] < bc[i][1]:
            a[j] = bc[i][1]
            bc[i][0] -= 1
        j += 1
print(sum(a))
### BUGGY CODE ###

import sys

stdin = sys.stdin

read_int = lambda : list(map(int,stdin.readline().split()))

N,M = read_int()

price_howmany = {}
price_list = []
for i in range(N):
    tmp = read_int()
    if tmp[0] not in price_list:
        price_list.append(tmp[0])
    if tmp[0] in price_howmany:
        price_howmany[tmp[0]] += tmp[1]
    else:
        price_howmany[tmp[0]] = tmp[1]
price_list.sort()

def solve():
    price = 0
    global M
    for low_price in price_list:
        many = min(M,price_howmany.pop(low_price))
        price += many * low_price
        M -= many
        if M == 0: break
    print(price)

if __name__ == "__main__":
    solve()

### FIXED CODE ###

# from collections import defaultdict
# N,M = list(map(int,input().split()))
# price_howmany = defaultdict(int)
import sys

stdin = sys.stdin

read_int = lambda : list(map(int,stdin.readline().split()))

N,M = read_int()
price_howmany = {}
# price_list = []

price_set = set()
for _ in range(N):
    tmp = read_int()
    # if tmp[0] not in price_set:
        # price_list.append(tmp[0])
    price_set.add(tmp[0])
    if tmp[0] in price_howmany:
        price_howmany[tmp[0]] += tmp[1]
    else:
        price_howmany[tmp[0]] = tmp[1]
# price_list.sort(reverse=True)
price_list = sorted(list(price_set))

# price_howmany = dict(price_howmany)

def solve():
    price = 0
    global M
    # while M > 0:
        # low_price = min(price_howmany.keys())
        # low_price = price_list.pop()
        # many = min(M,price_howmany.pop(low_price))
        # price += many * low_price
        # M -= many
    for low_price in price_list:
        many = min(M,price_howmany.pop(low_price))
        price += many * low_price
        M -= many
        if M == 0: break
    print(price)

if __name__ == "__main__":
    solve()