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

#!/usr/bin/env python
# -*- coding: utf-8 -*-

import sys


def input():
    return sys.stdin.readline()


def resolve():
    n = int(input())
    s = input()

    all_count = 0
    count = 0
    for i in range(n):
        for j in range(i+1, n):
            if s[i] == s[j]:
                continue

            if s[i] == "R" and s[j] == "G":
                target_str = "B"
            elif s[i] == "R" and s[j] == "B":
                target_str = "G"
            elif s[i] == "G" and s[j] == "R":
                target_str = "B"
            elif s[i] == "G" and s[j] == "B":
                target_str = "R"
            elif s[i] == "B" and s[j] == "R":
                target_str = "G"
            elif s[i] == "B" and s[j] == "G":
                target_str = "R"

            count += s.count(target_str, j+1, n)

            if 2*j-i < n:
                if target_str == s[2*j-i]:
                    count -= 1
            """
            for k in range(j+1, n):
                if j - i == k -j:
                    continue
                
                if s[i] == s[k] or s[j] == s[k]:
                    continue

                count += 1
            """

    print(count)


if __name__ == "__main__":
    resolve()



### FIXED CODE ###

#!/usr/bin/env python
# -*- coding: utf-8 -*-

import sys


def input():
    return sys.stdin.readline()


def resolve():
    n = int(input())
    s = input()

    count_dic = {}

    for i in range(n):
        count_dic[str(i)+"R"] = s.count("R", i, n)
        count_dic[str(i)+"G"] = s.count("G", i, n)
        count_dic[str(i)+"B"] = s.count("B", i, n)

    all_count = n* (n-1) * (n-2)
    count = 0
    for i in range(n):
        for j in range(i+1, n):
            if s[i] == s[j]:
                continue

            if s[i] == "R" and s[j] == "G":
                target_str = "B"
            elif s[i] == "R" and s[j] == "B":
                target_str = "G"
            elif s[i] == "G" and s[j] == "R":
                target_str = "B"
            elif s[i] == "G" and s[j] == "B":
                target_str = "R"
            elif s[i] == "B" and s[j] == "R":
                target_str = "G"
            elif s[i] == "B" and s[j] == "G":
                target_str = "R"

            count += count_dic[str(j)+target_str]

            if 2*j-i < n:
                if target_str == s[2*j-i]:
                    count -= 1
            """
            for k in range(j+1, n):
                if j - i == k -j:
                    continue
                
                if s[i] == s[k] or s[j] == s[k]:
                    continue

                count += 1
            """

    print(count)


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

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

def get_prime(n):
    prime = Counter()
    
    while not n % 2:
        prime[2] += 1
        n //= 2
        
    i = 3
    
    while i <= n**0.5:
        while not n % i:
            prime[i] += 1
            n //= i
        i += 2
        
    if n > 1: prime[n] += 1
        
    return prime
    
def main():
    MOD = 10**9+7
        
    N = int(input())
    A = list(map(int, input().split()))
    
    prime = Counter()
    
    for a in A:
        p = get_prime(a)
        for x, n in p.items():
            prime[x] = max(prime[x], n)
            
    X = 1
    for x, n in prime.items():
        X = X * pow(x, n, MOD)
        
    ans = 0
    
    for a in A:
        ans += X // a
        ans %= MOD
        
    print(ans)
    
if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
input = sys.stdin.readline

MOD = 10**9+7
def pow(a, b):
    res = 1
    while b:
        if b & 1: res = res * a % MOD
        a = a**2 % MOD
        b >>= 1
    return res

def main():
    N = int(input())
    A = list(map(int, input().split()))
    B = set(A)
    
    m = max(B)+1    
    prime = {i:i for i in range(m)}
    is_prime = [False] * m
    
    for i in range(2, int(m**0.5)+1):
        if is_prime[i]: continue
        is_prime[i] = True
        
        for j in range(2*i, m, i):
            if not is_prime[j]: prime[j] = i
            is_prime[j] = True
            
    from collections import Counter
    
    count = Counter()
            
    for a in A:
        c = Counter()
        while a > 1:
            n = prime[a]
            c[n] += 1
            a //= n
        for k, v in c.items(): count[k] = max(count[k], v)
            
    x = 1
    for k, v in count.items(): x = x * k**v % MOD
    
    ans = 0
    for a in A: ans += x * pow(a, MOD-2) % MOD
    
    print(ans%MOD)

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

s=input()
t=input()


result=''
dp=[[0]*len(t) for _ in range(len(s))]

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

i=len(s)-1
j=len(t)-1

L=dp[i][j]

while L>=1:
    if i==0 and dp[i][j]==1:
        result+=s[i]
        L-=1
    elif j==0 and dp[i][j]==1:
        result+=t[i]
        L-=1
    elif dp[i][j]>dp[i-1][j]:
        result+=s[i]
        i-=1
        L-=1
    elif dp[i][j]>dp[i][j-1]:
        result+=t[j]
        j-=1
        L-=1
    elif dp[i][j]>dp[i-1][j-1]:
        result+=t[j]
        L-=1
        i-=1
        j-=1
    else:
        i-=1
        j-=1


print(result[::-1])
    

### FIXED CODE ###

s=input()
t=input()


result=''
dp=[[0]*len(t) for _ in range(len(s))]

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

i=len(s)-1
j=len(t)-1

L=dp[i][j]

while L>=1:
    if i==0 and dp[i][j]==1:
        result+=s[i]
        L-=1
    elif j==0 and dp[i][j]==1:
        result+=t[j]
        L-=1
    elif dp[i][j]==dp[i-1][j]:
        i-=1
    elif dp[i][j]==dp[i][j-1]:
        j-=1
    else:
        result+=t[j]
        L-=1
        i-=1
        j-=1


print(result[::-1])
### BUGGY CODE ###

r,g,b,n = map(int,input().split())
count = 0
for i in range(int(n/r)+1):
    for j in range(int(n/g)+1):
        if r*i+g*j>n:
            break
        elif (n-r*i-g*j)%b==0:
            count += 1
print(count)

### FIXED CODE ###

import numpy as np

r,g,b,n=map(int,input().split())

x = np.arange(3001)
rr=x*r
f=0
for i in range(3002):
    p = ((n-rr)%b==0)
    q = n-rr>=0
    f+=np.sum(np.logical_and(p,q))
    rr+=g
print(f)
### BUGGY CODE ###

import sys
def input():
    return sys.stdin.readline()[:-1]
n=int(input())
ta=[list(map(int,input().split())) for i in range(n)]
t,a=ta[0][0],ta[0][1]
for i in range(n-1):
    wa=sum(ta[i+1])
    j=1
    while wa*j<t+a or t>j*ta[i+1][0] or a>j*ta[i+1][1]:
        j+=1
    t,a=j*ta[i+1][0],j*ta[i+1][1]
    # print([t,a])
print(t+a)

### FIXED CODE ###

import sys
def input():
    return sys.stdin.readline()[:-1]
n=int(input())
ta=[list(map(int,input().split())) for i in range(n)]
t,a=ta[0][0],ta[0][1]
for i in range(n-1):
    wa=sum(ta[i+1])
    j=max((t+a+wa-1)//wa,(t+ta[i+1][0]-1)//ta[i+1][0],(a+ta[i+1][1]-1)//ta[i+1][1])
    # while wa*j<t+a or j*ta[i+1][0]<t or j*ta[i+1][1]<a:
    #     j+=1
    t,a=j*ta[i+1][0],j*ta[i+1][1]
    # print([t,a])
print(t+a)
### BUGGY CODE ###

n, m = map(int, input().split())
a = []
for i in range(m):
    a.append(int(input()))

dp = [0] * (n + 1)

for i in range(n + 1):
    if i in a:
        dp[i] = 0
    else:
        if i == 0:
            dp[i] = 1
        elif i == 1:
            dp[i] = 1
        else:
            dp[i] = (dp[i - 1] + dp[i - 2]) % 1000000007

print(int(dp[n]))

"""
100 5
1
23
45
67
89
"""


### FIXED CODE ###

n, m = map(int, input().split())
A = set()
for i in range(m):
    a = int(input())
    A.add(a)
dp = [0] * (n + 1)
for i in range(n + 1):
    if i in A:
        dp[i] = 0
    else:
        if i == 0:
            dp[i] = 1
        elif i == 1:
            dp[i] = 1
        else:
            dp[i] = (dp[i - 1] + dp[i - 2]) % 1000000007
print(dp[n])

"""
100 5
1
23
45
67
89
"""
### BUGGY CODE ###

import math
def gcd(a,b,c):
    a = math.gcd(a, b)
    a = math.gcd(a, c)
    return a

ans=0
K=int(input())
for i in range(1,K+1): 
    for j in range(1,K+1):
        for k in range(1, K+1):
            ans+=gcd(i,j,k)

print(ans)

### FIXED CODE ###

import math
def gcd(a,b,c):
    a = math.gcd(a, b)
    a = math.gcd(a, c)
    return a

ans=0
K=int(input())
for i in range(1,K+1): 
    for j in range(1,K+1):
        for k in range(1, K+1):
            ans+=gcd(i,j,k)

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

import sys
sys.setrecursionlimit(10**8)
def knapsack(N,W,weight,value):
  #初期化
  inf=float("inf")
  dp=[[-inf for i in range(W+1)] for j in range(N+1)]
  for i in range(W+1): dp[0][i]=0

  #DP
  for i in range(N):
    for w in range(W+1):
      if weight[i]<=w: #dp[i][w-weight[i]の状態にi番目の荷物が入る可能性がある
        dp[i+1][w]=max(dp[i][w-weight[i]]+value[i], dp[i][w])
      else: #入る可能性はない
        dp[i+1][w]=dp[i][w]
  return dp[N][W]
n1,w1=map(int,input().split())
lw=[]
lv=[]
for i in range(n1):
  w,v=map(int,input().split())
  lw.append(w)
  lv.append(v)
print(knapsack(n1,w1,lw,lv))

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**8)
def knapsack(N,W,weight,value):
  #初期化
  inf=float("inf")
  dp=[[-inf for i in range(W+1)] for j in range(N+1)]
  for i in range(W+1): dp[0][i]=0

  #DP
  for i in range(N):
    for w in range(W+1):
      if weight[i]<=w: #dp[i][w-weight[i]の状態にi番目の荷物が入る可能性がある
        dp[i+1][w]=max(dp[i][w-weight[i]]+value[i], dp[i][w])
      else: #入る可能性はない
        dp[i+1][w]=dp[i][w]
  return dp[N][W]
n1,w1=map(int,input().split())
lw=[]
lv=[]
for i in range(n1):
  w,v=map(int,input().split())
  lw.append(w)
  lv.append(v)
print(knapsack(n1,w1,lw,lv))
### BUGGY CODE ###

from collections import deque
H,W=map(int,input().split())

L=[]
l=["*" for i in range(W+2)]
L.append(l)
for i in range(H):
    s=input()
    s="*"+s+"*"
    s=list(s)
    L.append(s)
L.append(l)

#print(L)
Li=[]
for i in range(1,H+1):
    for j in range(1,W+1):
        if L[i][j]=="#":
            Li.append([i,j])
#print(Li)
x=[1,-1,0,0]
y=[0,0,1,-1]
ans=0
for i in range(len(Li)):
    A=[[0 for i in range(W+2)]for j in range(H+2)]
    Arr=deque()
    Arr.append([Li[i][0],Li[i][1],0])
    #print(Arr)
    A[Arr[0][0]][Arr[0][1]]=1
    for j in range(W*H*2):
        if len(Arr)==0:
            break
        else:
            #print(Arr,ans)
            
            if (Arr[0][2])%2==0:
                for k in range(4):
                    if L[Arr[0][0]+x[k]][Arr[0][1]+y[k]]=="." and A[Arr[0][0]+x[k]][Arr[0][1]+y[k]]==0:
                        Arr.append([Arr[0][0]+x[k],Arr[0][1]+y[k],Arr[0][2]+1])
                        A[Arr[0][0]+x[k]][Arr[0][1]+y[k]]=1
                        ans+=1
                del Arr[0]
            else:
                for k in range(4):
                    if L[Arr[0][0]+x[k]][Arr[0][1]+y[k]]=="#" and A[Arr[0][0]+x[k]][Arr[0][1]+y[k]]==0:
                        Arr.append([Arr[0][0]+x[k],Arr[0][1]+y[k],Arr[0][2]+1])
                        A[Arr[0][0]+x[k]][Arr[0][1]+y[k]]=1
                del Arr[0]
print(ans)

### FIXED CODE ###

H,W=map(int,input().split())
L=[list(input())for i in range(H)]
#print(L)

P=[i for i in range(H*W)]
size=[[0,0]for i in range(H*W)]

for i in range(H):
    for j in range(W):
        if L[i][j]==".":
            size[i*W+j][0]+=1
        else:
            size[i*W+j][1]+=1
#print(size)

def find(z):
    if  z==P[z]:
        return z
    else:
        return find(P[z])
def union(x,y):
    X=find(x)
    Y=find(y)
    if sum(size[X])>=sum(size[Y]):
        P[Y]=P[X]
        size[X][0]+=size[Y][0]
        size[X][0]+=size[Y][1]
    else:
        P[X]=P[Y]
        size[Y][0]+=size[X][0]
        size[Y][0]+=size[X][1]
        
for i in range(H):
    for j in range(W):
        if j+1<=W-1:
            
            if L[i][j]!=L[i][j+1]:
                
                if find(i*W+j)!=find(i*W+j+1):
                    #print(i,j)
                    union(i*W+j,i*W+j+1)
        if i+1<=H-1:
            if L[i][j]!=L[i+1][j]:
                if find((i)*W+j)!=find((i+1)*W+j):
                    union(i*W+j,(i+1)*W+j)
BW=[[0,0]for i in range(H*W)]
for i in range(H):
    for j in range(W):
        if L[i][j]==".":
            BW[find(i*W+j)][0]+=1
        else:
            BW[find(i*W+j)][1]+=1

ans=0
for i in range(H):
    for j in range(W):
        if P[i*W+j]==i*W+j:
            ans+=BW[i*W+j][0]*BW[i*W+j][1]
#print(P)
#print(BW)
print(ans)
### BUGGY CODE ###

S = input()
Q = int(input())
for i in range(Q):
    a = input()
    if a == '1':
        S = S[::-1]
    else:
        a = [x for x in a]
        if a[2] == '1':
            S = a[4] + S
        else:
            S = S + a[4]

print(S)

### FIXED CODE ###

s = input()
q = int(input())
qs = [input().split() for i in range(q)]
n = False
left= right = ""
for operation in qs:
    if operation[0] == '1':
        n = not n
    if operation[0] == '2':
        t , f, c = operation
        f = int(f)
        if n:
            f = 1 if f != 1 else 2
        if f == 1:
            left=c+left
        elif f == 2:
            right+=c
s = left+s+right
print(s[::-1] if n else s)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import sys 
import numpy as np
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
N = int(readline())
A = list(map(int,readline().split()))

S = np.cumsum(A)
ans1 = 0
ans2 = 0
# 偶数項-,奇数項を+にする
for i in range(N):
    if i & 1: 
        if S[i] >= 0:
            ans1 += S[i]+1
            S -= S[i]+1
    else: 
        if S[i] <= 0:
            ans1 += 1-S[i]
            S += 1-S[i]

S = np.cumsum(A)

for i in range(N):
    if i & 1: 
        if S[i] <= 0:
            ans2 += 1-S[i]
            S += 1-S[i]
    else: 
        if S[i] >= 0:
            ans2 += S[i]+1
            S -= S[i]+1
            
print(min(ans1,ans2))   

### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
N = int(readline())
A = list(map(int,readline().split()))

ans1 = 0
ans2 = 0
S1 = 0
S2 = 0
# 偶数項-,奇数項を+にする
for i in range(N):
    S1 += A[i]
    S2 += A[i]
    if i & 1: 
        if S1 >= 0:
            ans1 += S1+1
            S1 = -1
        if S2 <= 0:
            ans2 += 1-S2
            S2 = 1
    else: 
        if S1 <= 0:
            ans1 += 1-S1
            S1 = 1
        if S2 >= 0:
            ans2 += S2+1
            S2 = -1
print(min(ans1,ans2))
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
res = A[0]*A[1]
for i in range(2,N): 
	res *= A[i]
if res <= 10**18:
	print(res)
else:
	print("-1")


### FIXED CODE ###

a=int(input())
b=input().split(" ")
sum1=1
 
if "0" in b:
    print("0")
else:
    for i in range(a):
        sum1=sum1*int(b[i])
        if sum1>10**18:
            sum1=-1
            break
    print(sum1)
### BUGGY CODE ###

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

max_ = 0
for i in range(n-k+1):
  max_ = max(max_, sum(a[i:i+k]))
    
print((max_+k)/2)

### FIXED CODE ###

n , k = map(int, input().split())
a = list(int(i) for i in input().split())
 
temp = sum(a[0:k])
max_  = temp
for i in range(n-k):
  f = a[i]
  s = a[i+k]
  temp -= f
  temp += s
  max_ = max(max_, temp)
    
print((max_+k)/2)
### BUGGY CODE ###

import itertools
import numpy as np
from math import factorial
n = list(map(int, input().split()))
x = np.array(list(map(int, input().split())))

x = x - n[1]
b = len(x) - np.count_nonzero(x)
x = [i for i in x if i != 0]
x = np.sort(x)

c = 0
for i in range(1, b + 1):
    c += factorial(b) / factorial(i) / factorial(b - i)

cnt = c
for i in range(2, n[0] + 1):
    for j in itertools.combinations(x, i):
        if j[0] > 0:
            break
        if sum(j) == 0:
            cnt += c + 1
            
print(int(cnt))

### FIXED CODE ###

import sys
import numpy as np
def sinput(): return sys.stdin.readline()
def iinput(): return int(sinput())
def imap(): return map(int, sinput().split())
def fmap(): return map(float, sinput().split())
def iarr(): return list(imap())
def farr(): return list(fmap())
def sarr(): return sinput().split()

n, a = imap()
x = np.array(iarr()) - a
MAX = 50*50+1

dp = np.zeros((n+1, 2*MAX+1)).astype(int)
dp[0][MAX] = 1
for i in range(n):
    for j in range(2*MAX):
        if j-x[i] < 0 or j-x[i] > 2*MAX:
            dp[i+1][j] = dp[i][j]
        else:
            dp[i+1][j] = dp[i][j] + dp[i][j-x[i]]
print(dp[n][MAX]-1)
### BUGGY CODE ###

N,K=map(int,input().split())
nodes=[]
for i in range(N):
  x,y=map(int,input().split())
  nodes.append((x,y))
import math
ans=math.inf
count=0
for i in range(N):
  for j in range(N):
    for k in range(N):
      for l in range(N):
        count=0
        for m in range(N):
          if nodes[i][0]<=nodes[m][0]<=nodes[j][0] and nodes[k][1]<=nodes[m][1]<=nodes[l][1]:
            count+=1
        if count>=K:
          ans=min(ans,(nodes[j][0]-nodes[i][0])*(nodes[l][1]-nodes[k][1]))
print(ans)

### FIXED CODE ###

N,K=map(int,input().split())
nodes=[]
for i in range(N):
  x,y=map(int,input().split())
  nodes.append((x,y))
nodes.sort()
import math
ans=math.inf
count=0
for i in range(N):
  for j in range(i+1,N):
    for k in range(N):
      for l in range(i+1,N):
        count=0
        for m in range(N):
          small=min(nodes[k][1],nodes[l][1])
          big=max(nodes[k][1],nodes[l][1])
          if nodes[i][0]<=nodes[m][0]<=nodes[j][0] and small<=nodes[m][1]<=big:
            count+=1
        if count>=K:
          ans=min(ans,(nodes[j][0]-nodes[i][0])*(big-small))
print(ans)
### BUGGY CODE ###

abck = input().split()
abck= [int(x) for x in abck]
a = abck[0]
b = abck[1]
c = abck[2]
k = abck[3]


result = 0
for i in range(k):
    # print(result,a,b,c)2
    if a ==0:
        if b== 0:
            if c == 0:
             break
            result -= 1
            continue
        result += 0
        b -= 1
        continue
    result +=1 
    a -= 1

print(result)

### FIXED CODE ###

abck = input().split()
abck= [int(x) for x in abck]
a = abck[0]
b = abck[1]
c = abck[2]
k = abck[3]

    


def check(a,b,c,k):
    resutlt = 0
    if a > k:
        result = k
        return result
    else:
        k -=a
        result = a
        if b>k:
            return result 
        else:
            k -= b
            result  -= k
            return result 

print(check(a,b,c,k))
### BUGGY CODE ###

from copy import deepcopy
from sys import stdin
def S(): return stdin.readline().rstrip()
def I(): return int(stdin.readline().rstrip())

n = I()
s = list(S())

s0 = {'R','G','B'}
s1 = deepcopy(s0)
ans = 0
for i in range(len(s)-2):
    s1.remove(s[i])
    for j in range(i+1,len(s)-1):
        s2 = deepcopy(s1)
        if s[j] in s2:
            s2.remove(s[j])
            for k in range(j+1,len(s)):
                if s[k] in s2:
                    if k-j != j-i:
                        ans += 1
    s1 = deepcopy(s0)

print(ans)

### FIXED CODE ###

from sys import stdin
def S(): return stdin.readline().rstrip()
def I(): return int(stdin.readline().rstrip())
 
n = I()
s = list(S())

r = s.count('R')
g = s.count('G')
b = s.count('B')
 
ans = r*g*b
for i in range(n-1):
    for j in range(1,n):
        if i-j<0 or n<=i+j:
            break
        else:
            if s[i-j]!=s[i] and s[i]!=s[i+j] and s[i-j]!=s[i+j]:
                ans-=1
 
print(ans)
### BUGGY CODE ###

N = int(input())
HPs = list(map(int,input().split()))
while(True):
    min_hp = min(HPs)
    max_hp = max(HPs)
    HPs[HPs.index(max_hp)] = max_hp % min_hp
    try:
        HPs.remove(0)
    except:
        continue
    if len(HPs) == 1:
        break
print(HPs[0])


### FIXED CODE ###

from fractions import gcd
N = int(input())
HPs = list(map(int,input().split()))
ans = HPs[0]
for i in HPs:
    ans = gcd(ans,i)
print(ans)
### BUGGY CODE ###

import bisect
n,m = list(map(int, input().split()))
a = list(map(int, input().split()))
a.sort()

data = [None] * m
for i in range(m):
    data[i] = list(map(int, input().split()))
data.sort(key = lambda x : x[1])
data.reverse()


ans = 0
count = 0
#data[][1] = value, data[][0] = card_num
for i in range(m):
    insert_index = bisect.bisect_left(a, data[i][1])
    if insert_index == 0:
        break
    count = min(data[i][0], insert_index)
    ans += count * data[i][1]
    a = a[count:]
print(ans + sum(a))


### FIXED CODE ###

import bisect
n,m = list(map(int, input().split()))
a = list(map(int, input().split()))
a.sort()

data = [None] * m
for i in range(m):
    data[i] = list(map(int, input().split()))
data.sort(key = lambda x : x[1])
data.reverse()


ans = 0
count = 0
pre_index = 0
#print(data)
#print(a)
#data[][1] = value, data[][0] = card_num
for i in range(m):
    insert_index = bisect.bisect_left(a, data[i][1])
    count = min(data[i][0], insert_index - pre_index)
    for j in range(pre_index, pre_index + count):
        if j >= n:
            break
        a[j] = 0
    ans += count * data[i][1]
    pre_index = pre_index + count
print(ans + sum(a))
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
mod = 10**9+7

#2^iをmodで割った余りを出しておく
twos = [1]
for i in range(1,60):
    twos.append((twos[i-1]*2)%mod)

#各baのbitごとに0の個数と1の個数を求める
c0 = [0]*60
for i in range(n):
    for j in range(60):
        if a[i]%2 == 0:
            c0[j] += 1
        a[i] //= 2

#答えは各bitごとの(0の数)*(1の数)より求まる
ans = 0
for i in range(60):
    ans += (((c0[i]*(n-c0[i]))%mod)*twos[i])%mod

ans %= mod
print(ans)


### FIXED CODE ###

import numpy as np
n = int(input())
a = np.array(input().split(),dtype=int)
mod = 10**9+7

twos = 1
ans = 0
for i in range(0,60):
    cou1 = np.count_nonzero((a >> i) & 1)
    ans += (cou1*(n-cou1)*twos)%mod
    twos = (twos*2)%mod

ans %= mod
print(ans)
### BUGGY CODE ###

N, Q = map(int, input().split())
S = input()
for q in range(Q):
  l, r = map(int, input().split())
  si = S[l-1:r]
  print(si.count("AC"))

### FIXED CODE ###

n, q = map(int, input().split())
s = input()
c = [0]
for i in range(len(s)-1):
  if s[i] == "A" and s[i+1] == "C":
    c.append(c[-1]+1)
  else:
    c.append(c[-1])
    
for i in range(q):
  l, r = map(int, input().split())
  print(c[r-1] - c[l-1])
### BUGGY CODE ###

N = int(input())
s = [sorted(input()) for i in range(N)]
ans = 0

for i in range(N):
    for j in range(i+1, N):
        if s[i] == s[j]:
            ans += 1
print(ans)

### FIXED CODE ###

import math

N = int(input())
s = {}
ans = 0

for i in range(N):
    tmp = ''.join(sorted(input()))
    if tmp in s:
        s[tmp] += 1
    else:
        s[tmp] = 1

x = math.factorial(2)
for n in s.values():
  	if n > 1:
	    ans += math.factorial(n) // (math.factorial(n-2) * x)
print(ans)