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

# 整数を一つ入力
N = int(input())

# 文字列を一つ入力
S = input()

res = 0

for i in range(N-2):
    for j in range(i+1,N-1):
        for k in range(j+1,N):
            if j-i == k-j:
                continue
            if S[i] == S[j] or S[i] == S[k] or S[j] == S[k]:
                continue
            res += 1

print(res)


### FIXED CODE ###

# 整数を一つ入力
N = int(input())

# 文字列を一つ入力
S = input()

res = 0

R = []
G = []
B = []

for i in range(N):
    if S[i] == "R":
        R.append(i)
        continue
    if S[i] == "G":
        G.append(i)
        continue
    B.append(i)

BN = len(B)

for i in R:
    for j in G:
        res += BN
        ii,jj = i,j
        if ii > jj:
            ii,jj = jj,ii
        if ii - (jj-ii) >= 0:
            if S[ii-(jj-ii)] == "B":
                res -= 1
        if (abs(jj-ii)) % 2 == 0:
            if S[(jj+ii) // 2] == "B":
                res -= 1
        if jj + (jj-ii) <= N-1:
            if S[jj+(jj-ii)] == "B":
                res -= 1
print(res)
### BUGGY CODE ###

n = int(input())
a = []
for _ in range(n):
    a.append(int(input()))
b = []

for i in range(n):
    b = []
    b = a.copy()
    del b[i]
    print(max(b))


### FIXED CODE ###


n = int(input())
a = [int(input()) for _ in range(n)]
b = a.copy()
b.sort()

for i in range(n):
    if a[i] == b[-1]:
        print(b[-2])
    else:
        print(b[-1])
### BUGGY CODE ###

import sys
input = sys.stdin.readline
import numpy as np

S = input().rstrip()
n = len(S)
mod = 10**9+7
dp = np.zeros((n+1, 13), dtype=np.int64)
dp[0][0] = 1
j = np.arange(13)*10%13
for i, s in enumerate(S):
  if s != "?":
    t = int(s)
    dp[i+1][j] += np.roll(dp[i], t)
    dp[i+1] %= mod
  else:
    for t in range(10):
      dp[i+1][j] += np.roll(dp[i], t)
      dp[i+1] %= mod
print(dp[n][11])

### FIXED CODE ###

s = input()
n = len(s)
mod = 10**9+7
dp = [[0]*13 for _ in range(n+1)]
dp[0][0] = 1
d = {(j, k):(10*j+k)%13 for k in range(10) for j in range(13)}
for i in range(n):
  if s[i] != "?":
    t = int(s[i])
    for j in range(13):
      dp[i+1][d[(j, t)]] += dp[i][j]
      dp[i+1][d[(j, t)]] %= mod
  else:
    for k in range(10):
      for j in range(13):
        dp[i+1][d[(j, k)]] += dp[i][j]
        dp[i+1][d[(j, k)]] %= mod
print(dp[n][5]%mod)
### BUGGY CODE ###

N, M = list(map(int, input().split()))
sigma = list(map(int, input().split()))
gokans = []

for i in range(M):
    pair = tuple(map(int, input().split()))
    gokans.append(pair)

def connected(i, j, paths):
    if [pair for pair in paths if i in pair] and [pair for pair in paths if j in pair]:
        new_chain_i = [pair for pair in paths if i in pair]
        new_chain_j = [pair for pair in paths if j in pair]
        for pair in set(new_chain_i + new_chain_j):
            paths.remove(pair)
        narabi_i = set([couple[0] for couple in new_chain_i] + [couple[1] for couple in new_chain_i])
        narabi_j = set([couple[0] for couple in new_chain_j] + [couple[1] for couple in new_chain_j])
        if narabi_i & narabi_j != set():
            return True

        while new_chain_i and new_chain_j:
            new_chain_i_kari = []
            new_chain_j_kari = []

            for pair in new_chain_i:
                new_chain_i_kari += [couple for couple in paths if set(couple) & set(pair) != set()]
            for pair in new_chain_j:
                new_chain_j_kari += [couple for couple in paths if set(couple) & set(pair) != set()]
            new_chain_i = new_chain_i_kari
            new_chain_j = new_chain_j_kari

            for pair in set(new_chain_i + new_chain_j):
                paths.remove(pair)
            narabi_i = set([couple[0] for couple in new_chain_i] + [couple[1] for couple in new_chain_i])
            narabi_j = set([couple[0] for couple in new_chain_j] + [couple[1] for couple in new_chain_j])
            if narabi_i & narabi_j != set():
                return True
        return False
    else:
        return False

count = 0
for i in range(1, N+1):
    if i != sigma[i-1]:
        gokans1 = gokans.copy()
        if connected(i, sigma[i-1], gokans1):
            count += 1
    else:
        count += 1
print(count)

### FIXED CODE ###

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

par = [i for i in range(n)]
#rootの計算量は、parが最初の状態に近いほど値は小さくて、高々O(n)
def root(x):
	tmp = par[x]
	if tmp == x:
		return x
	else:
		a = root(tmp)
		par[x] = a
		return a

def merge(x, y):
	x = root(x)
	y = root(y)
	if x != y:
		par[x] = y
		return

for i in range(m):
	x, y = map(int, input().split())
	merge(x-1, y-1)
	#print(par)

ans = 0

for i in range(n):
	if p[i]-1 == i:
		ans += 1
	elif root(p[i]-1) == root(i):
		ans += 1
print(ans)
### BUGGY CODE ###

S = input()
Q = int(input())
for _ in range(Q):
    T = input()
  
    if len(T)==1:
        S = S[::-1]
    else:
        if T[2]=="1":
            S = T[4]+S
        else:
              S = S+T[4]
print(S)

### FIXED CODE ###

from collections import deque

S = input()
Q = int(input())

t = deque(S)
reverse = False
for _ in range(Q):
    query = input()
    if query[0] == '1':
        reverse = not reverse
    elif query[0] == '2':
        _, F, C = query.split()
        if F == '1':
            if reverse:
                t.append(C)
            else:
                t.appendleft(C)
        elif F == '2':
            if reverse:
                t.appendleft(C)
            else:
                t.append(C)
result = ''.join(t)
if reverse:
    result = result[::-1]
print(result)
### BUGGY CODE ###

N = int(input())
a = 0
ans = 10000000000000000
s = 0
if N%2==0:
    for x in range(1,(N//2)+1):
        s=N//x
        if N%x==0:
            a = (s-1)+(x-1)
            if ans>a:
                ans = a
else:
    for x in range(1,((N+1)//2)):
        s =N//x
        if N%x==0:
            a = (s-1)+(x-1)
            if ans>a:
                ans = a
print(ans)


### FIXED CODE ###

N = int(input())
a = 0
ans = N-1
s = 0
for x in range(1,1000001):
    s=N//x
    if N%x==0:
        a = (s-1)+(x-1)
        if ans>a:
             ans = a
print(ans)
### BUGGY CODE ###

N,K = map(int,input().split())
h = [int(i) for i in input().split()]
dp = [10**10 for _ in range(N)]
dp[0] = 0
for i in range(1,N):
    for k in range(min(K,i)+1):
        dp[i] = min(dp[i], dp[i-k] + abs(h[i-k]-h[i]))
        
print(dp[-1])

### FIXED CODE ###

import numpy as np
N,K = map(int,input().split())
h = np.array([int(i) for i in input().split()])
dp = np.full(N,10**10,dtype=int)
dp[0] = 0
for i in range(1,N):
    dp[i:i+K] = np.fmin(dp[i:i+K], dp[i-1] + np.abs(h[i:i+K] - h[i-1]))
        
print(dp[-1])
### BUGGY CODE ###

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())
  
N, M = map(int,input().split()) 
uf = UnionFind(N)
for _ in range(M):
  a, b = map(int,input().split())
  uf.union(a-1,b-1)

ans = 0
for i in list(uf.all_group_members().values()):
  ans = max(len(i),ans)
print(ans)

### FIXED CODE ###

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())
  
N, M = map(int,input().split()) 
uf = UnionFind(N)
for _ in range(M):
  a, b = map(int,input().split())
  uf.union(a-1,b-1)

ans = 0
for i in range(N):
  ans=max(ans, uf.size(i))
print(ans)
### BUGGY CODE ###

n=int(input())
dp=input().split()
m=int(input())
tp=input().split()
d=dict()

ans="YES"

for di in dp:
    if di in d:
        d[di]+=1
    else:
        d[di]=1

for ti in tp:
    if ti not in dp or d[ti]==0:
        ans="NO"
        break
    else:
        d[ti]-=1
print(ans)

### FIXED CODE ###

import collections
n=int(input())
dp=collections.Counter(int(x) for x in input().split())
m=int(input())
tp=collections.Counter(int(x) for x in input().split())
ans="YES"
for k,v in tp.items():
    if dp[k]<v:
        ans="NO"
        break
print(ans)
### BUGGY CODE ###

# d
I = lambda: map(int, input().split())
n, k = I()
a = []
for _ in range(n):
    t, d = I()
    a += [d, t, 0],
a.sort(reverse = True)
b = 0
c = [0]*(n+1)
e = 0
for i in a[:k]:
    b += i[0]
    if c[i[1]] == 0: e += 1
    c[i[1]] += 1
    i[2] = 1
f = [b+e**2]
for i in range(k, n):
    g = a[i]
    if c[g[1]] > 0: continue
    for j in a[:i][::-1]:
        if j[2] > 0 and c[j[1]] > 1:
            b += g[0]-j[0]
            g[2] = 1
            j[2] = 0
            c[g[1]] += 1
            c[j[1]] -= 1
            e += 1
            f += b+e**2,
            break
print(max(f))

### FIXED CODE ###

mi = lambda: map(int, input().split())
n, k = mi()
sushis = [list(mi()) for _ in range(n)]
types = set()
sushis.sort(key = lambda x: x[1], reverse = True)
bp = tp = sp = 0
exts = []
for t, d in sushis[:k]:
    bp += d
    if t in types:
        exts += d,
    else:
        types.add(t)
        tp += 1
sp = bp+tp**2
for t, d in sushis[k:]:
    if not exts: break
    if t not in types:
        types.add(t)
        bp += d-exts.pop()
        tp += 1
        sp = max(sp, bp+tp**2)
print(sp)
### BUGGY CODE ###

n,m = (int(i) for i in input().split())
ab = [[int(i)-1 for i in input().split()] for i in range(m)]

ab0 = list(filter(lambda x:x[0]==0,ab))
abn = list(filter(lambda x:x[1]==n-1,ab))

ab0 = list(map(lambda x:x[1], ab0))
abn = list(map(lambda x:x[0], abn))


res="IMPOSSIBLE"
for x in ab0:
    if x in abn:
        res= "POSSIBLE"
        break
 
print(res)

### FIXED CODE ###

import sys
input = sys.stdin.readline
n,m = (int(i) for i in input().split())
ab = [[int(i)-1 for i in input().split()] for i in range(m)]

ab = list(filter(lambda x:x[0]==0 or x[1]==n-1, ab))
ab0 = list(filter(lambda x:x[0]==0,ab))
abn = list(filter(lambda x:x[1]==n-1,ab))

ab0_bin = ["0"]*n
abn_bin = ["0"]*n
for x in ab0:
    ab0_bin[x[1]] = "1"
for x in abn:
    abn_bin[x[0]] = "1"

ab0_bin = "".join(ab0_bin)
abn_bin = "".join(abn_bin)

if bin(int(ab0_bin,2) & int(abn_bin, 2))[2:].count("1") > 0:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")
### BUGGY CODE ###

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

a=sorted(A)
print(sum(a[D:]))

### FIXED CODE ###

N, M = map(int, input().split())
A = list(map(int, input().split()))
BC = [list(map(int, input().split())) for _ in range(M)]
BC.sort(key=lambda x: x[1], reverse=True)
D = []
sum_B=0
for B, C in BC:
    D += [C] * B
    sum_B += B
    if sum_B>N:
        break

A+=D
A.sort(reverse = True)
print(sum(A[:N]))
### BUGGY CODE ###

import sys
from functools import lru_cache
sys.setrecursionlimit(10 ** 7)

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

sushi = [0] * 4
for a in A:
    sushi[a] += 1
B, C, D = sushi[1:]


@lru_cache(maxsize=10 ** 6)
def rec(a, b, c, d):
    if (b, c, d) == (0, 0, 0):
        return 0
    if b < 0 or c < 0 or d < 0:
        return 0

    x1 = rec(a + 1, b - 1, c, d) * b / (N - a)
    x2 = rec(a, b + 1, c - 1, d) * c / (N - a)
    x3 = rec(a, b, c + 1, d - 1) * d / (N - a)
    return x1 + x2 + x3 + N / (N - a)


print(rec(0, B, C, D))

### FIXED CODE ###

from collections import Counter, defaultdict
N = int(input())
A = list(map(int, input().split()))
C = Counter(A)

U = N + 1
inf = 1e18

dp = [[[inf] * U for _ in range(U)] for _ in range(U)]
dp[0][0][0] = 0.0

for c in range(N + 1):
    for b in range(N + 1):
        if c + b > N:
            break
        for a in range(N + 1):
            if a + b + c == 0:
                continue
            if a + b + c > N:
                break
            prob = 0
            E = N
            if a > 0:
                E += a * dp[a - 1][b][c]
                prob += a
            if b > 0 and a < N:
                E += b * dp[a + 1][b - 1][c]
                prob += b
            if c > 0 and b < N:
                E += c * dp[a][b + 1][c - 1]
                prob += c
            dp[a][b][c] = E / prob

x = C[1]
y = C[2]
z = C[3]
print(dp[x][y][z])
### BUGGY CODE ###

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

d = [a[i] - a[i-1] for i in range(1, n)]
d.insert(0, a[0])
d.append(k - a[-1])
sum_d = sum(d)

most_min_path = 10000

for i in range(n):
    if i == 0:
        normal_ck = sum_d - d[i] - d[-1]
        reverse_ck = sum_d - d[i+1]
    elif i == n - 1:
        normal_ck = sum(d) - d[i]
        reverse_ck = sum(d) - d[i+1] - d[0]
    elif 0 < i < n - 1:
        normal_ck =  sum(d) - d[i]
        reverse_ck = sum(d) - d[i+1]

    min_ck = normal_ck if normal_ck < reverse_ck else reverse_ck
    if most_min_path > min_ck:
        most_min_path = min_ck

print(most_min_path)

### FIXED CODE ###

k, n = map(int, input().split())
a = list(map(int, input().split()))
a.append(a[0] + k)

d = [a[i+1] - a[i] for i in range(n)]
l = 0
for i in range(n):
    l = max(l, a[i+1] - a[i])
print(k - l)
### BUGGY CODE ###

n=int(input())
s=input()
ans=0
a=[0]*3
f=0

for a[0] in range(10):
    for a[1] in range(10):
        for a[2] in range(10):
            #print("pass=",a[0],a[1],a[2])
            f=0
            for ss in s:
                #print(ss,a[f],f)
                if int(ss) == a[f]:
                    f+=1
                    if f==3:
                        ans+=1
                        break
print(ans)


### FIXED CODE ###

n=int(input())
s=input()
ans=0

for ii in range(1000):
    v = str(ii).zfill(3)
    start=0
    f=0
    
    for j in range(3):
        idx=s.find(v[j],start)
        if idx > -1:
            start = idx + 1
            f+=1
        else:
            break

    if f == 3:
        ans += 1

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

#!/usr/bin/python
import sys

s = sys.stdin.readline().replace('\n','')
q = sys.stdin.readline().replace('\n','')
q = int(q)

for i in range(0,q):
	str = sys.stdin.readline().replace('\n','')
        if( str[0] == '1'):
		s = s[::-1]
        if( str[0] == '2'):
          if( str[2] == '1'):
	    s = str[4] + s
          if( str[2] == '2'):
	    s = s + str[4]

print s
sys.stdout.flush()


### FIXED CODE ###

import sys

s = sys.stdin.readline().replace('\n','')
q = sys.stdin.readline().replace('\n','')
q = int(q)

flag = 0
prev=""
end=""
for i in range(0,q):
	str = sys.stdin.readline().replace('\n','')
        if( str[0] == '1'):
          flag += 1
        if( str[0] == '2'):
          if( str[2] == '1'):
	    if( flag % 2 == 0):
	      prev = str[4] + prev
	    else:
	      end = end + str[4]
          if( str[2] == '2'):
	    if( flag % 2 == 0):
	      end = end + str[4]
	    else:
	      prev = str[4] + prev

ss = prev + s + end
if( flag % 2 == 1):
  ss = ss[::-1]

print ss
sys.stdout.flush()
### BUGGY CODE ###

import collections

def calc(x,y):
  cnt1=(x+k-1)//k
  cnt2=(w-1-x+k-1)//k
  cnt3=(y+k-1)//k
  cnt4=(h-1-y+k-1)//k
  return min(cnt1,cnt2,cnt3,cnt4)

h,w,k=map(int,input().split())
boards=[list(input()) for _ in range(h)]
for i in range(h):
  for j in range(w):
    if boards[i][j]=='S':
      sx=j
      sy=i
      break
q=collections.deque()
checked=[[0]*w for _ in range(h)]
checked[sy][sx]=1
q.append((sx,sy,0))
ans=1+calc(sx,sy)
while 1:
  if len(q)==0:
    break
  tx,ty,cnt=q.popleft()
  if cnt==k+1:
    break
  ans=min(ans,1+calc(tx,ty))
  if tx!=0 and boards[ty][tx-1]!='#' and checked[ty][tx-1]==0:
    checked[ty][tx-1]=1
    q.append((tx-1,ty,cnt+1))
  if tx!=w-1 and boards[ty][tx+1]!='#' and checked[ty][tx+1]==0:
    checked[ty][tx+1]=1
    q.append((tx+1,ty,cnt+1))
  if ty!=0 and boards[ty-1][tx]!='#' and checked[ty-1][tx]==0:
    checked[ty-1][tx]=1
    q.append((tx,ty-1,cnt+1))
  if ty!=h-1 and boards[ty+1][tx]!='#' and checked[ty+1][tx]==0:
    checked[ty+1][tx]=1
    q.append((tx,ty+1,cnt+1))
print(ans)

### FIXED CODE ###

import collections

def solve():
  def calc(x,y):
    cnt1=(x+k-1)//k
    cnt2=(w-1-x+k-1)//k
    cnt3=(y+k-1)//k
    cnt4=(h-1-y+k-1)//k
    return min(cnt1,cnt2,cnt3,cnt4)

  h,w,k=map(int,input().split())
  boards=[tuple(input()) for _ in range(h)]
  for i in range(h):
    for j in range(w):
      if boards[i][j]=='S':
        sx=j
        sy=i
        break
  q=collections.deque()
  checked=[[0]*w for _ in range(h)]
  checked[sy][sx]=1
  q.append((sx,sy,0))
  ans=1+calc(sx,sy)
  while 1:
    if len(q)==0:
      break
    tx,ty,cnt=q.popleft()
    if cnt==k+1:
      break
    ans=min(ans,1+calc(tx,ty))
    if tx!=0 and boards[ty][tx-1]!='#' and checked[ty][tx-1]==0:
      checked[ty][tx-1]=1
      q.append((tx-1,ty,cnt+1))
    if tx!=w-1 and boards[ty][tx+1]!='#' and checked[ty][tx+1]==0:
      checked[ty][tx+1]=1
      q.append((tx+1,ty,cnt+1))
    if ty!=0 and boards[ty-1][tx]!='#' and checked[ty-1][tx]==0:
      checked[ty-1][tx]=1
      q.append((tx,ty-1,cnt+1))
    if ty!=h-1 and boards[ty+1][tx]!='#' and checked[ty+1][tx]==0:
      checked[ty+1][tx]=1
      q.append((tx,ty+1,cnt+1))
  print(ans)
solve()
### BUGGY CODE ###

import collections
N = int(input())
a = list(map(int, input().split()))
cand = collections.Counter(a)
cand_list = cand.most_common(len(set(a)))
ans = 0
for i in range(len(set(a))):
  num = cand_list[i][0]
  count = cand[num]
  if num + 1 in a:
    count += cand[num + 1]
  if num - 1 in a:
    count += cand[num - 1]
  if ans < count:
    ans = count

print(ans)

### FIXED CODE ###

import collections
N = int(input())
a = list(map(int, input().split()))
cand = collections.Counter(a)
cand_list = cand.most_common(len(set(a)))
ans = 0
for i in range(len(set(a))):
  num = cand_list[i][0]
  count = cand[num] + cand[num + 1] + cand[num - 1]
  ans = max(ans,count)

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

n,k = map(int,input().split())
a = list(map(int,input().split()))
b = []
x = 0
y = 1
while x != k and b.count(y) != 2:
    x += 1
    y = a[y-1]
    b.append(y)
if x != k:
    x -= 1
    k -= x
    y = b.index(b[-1])
    k %= (x - y)
    c = b[y:x]
    print(c[k-1])
else:
    print(b[-1])

### FIXED CODE ###

n,k = map(int,input().split())
a = list(map(int,input().split()))
b = [0] * n
c = ['Y'] * n
c[0] = 'N'
x = 0
y = 1
while x != k:
    c[y-1] = 'N'
    x += 1
    y = a[y-1]
    b[x-1] = y
    if c[y-1] == 'N':
        break
if x != k:
    y = b.index(a[y-1])
    k -= x
    k %= (x-y)
    c = b[y:x]
    print(c[k-1])
else:
    print(y)
### BUGGY CODE ###

def main():
    import heapq
    n, m, *abc = map(int, open(0).read().split())
    a = sorted(abc[:n])
    *bc, = zip(*[iter(abc[n:])] * 2)
    bc = sorted(bc, key=lambda x: x[1], reverse=True)
    b = []
    for i, j in bc:
        b += [j] * i

    c = heapq.merge(a, b)

    print(sum(heapq.nlargest(n, c)))


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    from collections import Counter
    n, m, *abc = map(int, open(0).read().split())
    a = Counter(abc[:n])
    bc = abc[n:]
    for i, j in zip(*[iter(bc)] * 2):
        a[j] += i

    cnt = n
    ans = 0
    keys = list(a.keys())
    keys.sort(reverse=True)

    for k in keys:
        m = a[k]
        if m <= cnt:
            ans += k * m
            cnt -= m
        else:
            ans += k * cnt
            break

    print(ans)


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

s = input()
q = int(input())
qs = [input().split() for i in range(q)]

for operation in qs:
    if operation[0] == '1':
        s = s[::-1]
    elif operation[0] == '2':
        t , f, c = operation
        if f == '1':
            s = c+s
        else:
            s = s + c
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 ###

import numpy as np
n=int(input())

ans=0
for a in range(1,n+1):
  for b in range(1,n+1):
    d=np.gcd(a,b)
    if d==1:
      ans+=n
      continue
    for c in range(1,n+1):
      ans += np.gcd(c,d)

print(ans)

### FIXED CODE ###

import numpy as np
n=int(input())

ans=0
for a in range(1,n+1):
  for b in range(1,n+1):
    d=np.gcd(a,b)
    if d==1:
      ans+=n
      continue
    if d==2:
      ans+=n//2*3+n%2
      continue
    if d==3:
      ans+=n//3*5+n%3
      continue
    if d==5:
      ans+=n//5*9+n%5
      continue
    for c in range(1,n+1):
      ans += np.gcd(c,d)

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

n=int(input())
p=[]
for i in range(n):
  s=input()
  if not s in p:
    p.append(s)
print(len(p))

### FIXED CODE ###

n=int(input())
p=[]
for i in range(n):
  s=input()
  p.append(s)
print(len(set(p)))
### BUGGY CODE ###

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

a = [0]
b = [0]
for i in range(N):
    a.append(a[i]+A[i])
for i in range(M):
    b.append(b[i] +B[i])
ans = 0
best = M
for i in range(N+1):
    if a[i] > K:
        break
    for j in range(best, -1, -1):
        if a[i] + b[j] <= K:
            ans = max(ans, i+j)
            break
print(ans)


### FIXED CODE ###

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

a = [0]
b = [0]
for i in range(N):
    a.append(a[i]+A[i])
for i in range(M):
    b.append(b[i] +B[i])
ans = 0
j = M
for i in range(N+1):
    if a[i] > K:
        break
    while b[j] > K -a[i]:
        j -= 1
    ans = max(ans, i+j)
print(ans)
### BUGGY CODE ###

import sys

N, M = map(int, sys.stdin.readline().split())
A = list(map(int, sys.stdin.readline().split()))
BC0 = [0]*M
for m in range(M):
    BC0[m] = list(map(int, sys.stdin.readline().split()))
A.sort()
BC0.sort(key=lambda x:x[1])
BC = []
for bc0 in BC0:
    BC = BC + [bc0[1]]*bc0[0]

S = [0] * (N+1)
S[0] = sum(A)
for n in range(min(N,len(BC))):
    S[n+1] = S[n] - A[n] + BC[-n-1]
print(max(S))

### FIXED CODE ###

N, M = map(int, input().split())
A0 = list(map(int, input().split()))
BC = [list(map(int, input().split())) for _ in range(M)]

A = [[1,a] for a in A0] 
ABC = A + BC
ABC.sort(key=lambda x:x[1], reverse=True)

summation = 0
p = 0
n = 0

while n<N:
    summation += ABC[p][1] * (min(ABC[p][0], N-n))
    n += min(ABC[p][0], N-n)
    p += 1

print(summation)