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

import sys
input = sys.stdin.readline
class Unionfind:
    def __init__(self,n):
        self.per = [i for i in range(n)]

    def find(self, x):
        if self.per[x] == x:
            return x
        else:
            self.per[x] = self.find(self.per[x])
            return self.per[x]

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

    def union(self,x,y):
        x = self.find(x)
        y = self.find(y)
        self.per[x] = y
        
            
N = int(input())
cityx = []
cityy = []
for i in range(N):
    x,y = map(int,input().split())
    cityx.append([x,i])
    cityy.append([y,i])
cityx.sort()
cityy.sort()
side = []
for i in range(N-1):
    side.append([cityx[i+1][0]-cityx[i][0], cityx[i+1][1], cityx[i][1]])
    side.append([cityy[i+1][0]-cityy[i][0], cityy[i+1][1], cityy[i][1]])
side.sort()
ans = 0
uf = Unionfind(N)
for cost, x, y in side:
    if uf.same_check(x,y):
        continue
    ans += cost
    uf.union(x,y)

print(ans)



### FIXED CODE ###

import sys
input = sys.stdin.readline

N = int(input())
cityx = [[0,i]for i in range(N)]
cityy = [[0,i]for i in range(N)]
for i in range(N):
    x,y = map(int,input().split())
    cityx[i][0] = x
    cityy[i][0] = y

cityx.sort()
cityy.sort()
side = []
for i in range(N-1):
    side.append([cityx[i+1][0]-cityx[i][0], cityx[i+1][1], cityx[i][1]])
    side.append([cityy[i+1][0]-cityy[i][0], cityy[i+1][1], cityy[i][1]])
side.sort()
ans = 0
per = [i for i in range(N)]
rank = [0]*N
def find(x):
    if per[x] == x:
        return x
    else:
        per[x] = find(per[x])
        return per[x]

ans = 0

for cost,x,y in side:
    x = find(x)
    y = find(y)
    if x != y:
        ans += cost
        if rank[x] < rank[y]:
            per[x] = y
        else:
            per[y] = x
            if rank[x] == rank[y]:
                rank[x] += 1

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

import functools
n = int(input())
a_list = list(map(int,input().split()))

def gcd(m,n):
    x = max(m,n)
    y = min(m,n)
    if y in res:
        return y
    if x%y==0:
        return y
    else:
        while x%y!=0:
            x,y = y,x%y
        return y

res = []
tmp = []
for _ in range(n):
    e = a_list.pop(0)
    if e in tmp:
        continue
    res.append(functools.reduce(gcd, a_list))
    a_list.append(e)
    tmp.append(e)

print(max(res))

### FIXED CODE ###

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

def gcd(m,n):
    x = max(m,n)
    y = min(m,n)
    if y==0:
        return x
    else:
        while x%y!=0:
            x,y = y,x%y
        return y

res = []
l_gcd = [0]*(n+2)
r_gcd = [0]*(n+2)
for i in range(n+1):
    if i ==0:
        l_gcd[i] = 0
        r_gcd[n-i+1] = 0
        continue
    l_gcd[i] = gcd(l_gcd[i-1], a_list[i-1])
    r_gcd[n-i] = gcd(r_gcd[n-i+1], a_list[n-i])

for i in range(n+1):
    res.append(gcd(l_gcd[i],r_gcd[i+1]))

print(max(res))
### BUGGY CODE ###

def abc084_d():

  def primes_list(n):
    # n以下の素数列挙
    primes = set(range(2, n+1))
    for i in range(2, int(n**0.5+1)):
      primes.difference_update(range(i*2, n+1, i))
    return list(primes)

  # 素数リストを用意する
  primes = sorted(primes_list(10**5))

  # (n+1)//2 を素数判定するための準備
  is_prime = [False] * (10**5 + 10)
  for p in primes:
    is_prime[p] = True

  # 入力を受け取る
  q = int(input())
  query = [tuple(map(int, input().split())) for _ in range(q)]

  # クエリを処理する
  from bisect import bisect_left
  for l, r in query:
    # 2は素数だが奇数ではない、rは3以上でないと解が無い
    if r < 3:
      print(0)
      continue
    # 左側は3以下はカット
    l = max(l, 3)
    # 二分探索で範囲決める
    idx_start = bisect_left(primes, l)
    idx_stop = bisect_left(primes, r+1)
    ans = 0
    for i in range(idx_start, idx_stop):
      # (n+1)//2 が素数なら当たり
      if is_prime[(primes[i]+1) // 2]:
        ans += 1
    print(ans)

abc084_d()

### FIXED CODE ###

def abc084_d():

  def primes_list(n):
    # n以下の素数列挙
    primes = set(range(2, n+1))
    for i in range(2, int(n**0.5+1)):
      primes.difference_update(range(i*2, n+1, i))
    return list(primes)

  # 素数リストを用意する
  primes = sorted(primes_list(10**5))

  # (n+1)//2 を素数判定するための準備
  is_prime = [False] * (10**5 + 10)
  for p in primes:
    is_prime[p] = True

  # 2017に似た数の累積個数 (1-index)
  acc_like = [0]
  for p in primes:
    this_like = 1 if is_prime[(p+1) // 2] else 0
    acc_like.append(acc_like[-1] + this_like)

  # 入力を受け取る
  q = int(input())
  query = [tuple(map(int, input().split())) for _ in range(q)]

  # クエリを処理する
  from bisect import bisect_left
  for l, r in query:
    # 2は素数だが奇数ではない、rは3以上でないと解が無い
    if r < 3:
      print(0)
      continue
    # 左側は3以下はカット
    l = max(l, 3)
    # 二分探索で範囲決める
    idx_l = bisect_left(primes, l)
    idx_r = bisect_left(primes, r+1)
    # 累積和から個数求める
    ans = acc_like[idx_r] - acc_like[idx_l]
    print(ans)

abc084_d()
### BUGGY CODE ###

def main():
    n = int(input())
    s = input()
    # Positions for each character.
    r = set()
    g = set()
    b = set()
    r_add = r.add
    g_add = g.add
    b_add = b.add
    for ind, c in enumerate(s):
        if c == 'R':
            r_add(ind)
        elif c == 'G':
            g_add(ind)
        else:
            b_add(ind)
    ans = 0
    for i in r:
        for j in g:
            for k in b:
                o, p, q = sorted((i, j, k))
                if p - o != q - p:
                    ans += 1
    return ans


if __name__ == '__main__':
    print(main())


### FIXED CODE ###

def main():
    n = int(input())
    s = input()
    # Positions for each character.
    r = set()
    g = set()
    r_add = r.add
    g_add = g.add
    for ind, c in enumerate(s):
        if c == 'R':
            r_add(ind)
        elif c == 'G':
            g_add(ind)
    b = set(range(n)) - r - g

    ans = 0
    for i in r:
        for j in g:
            p, q = min(i, j), max(i, j)
            if (q - p) % 2 == 0 and (p + q) // 2 in b:
                ans -= 1
            if (q + (q - p)) in b:
                ans -= 1
            if (p - (q - p)) in b:
                ans -= 1
            ans += len(b)
    return ans


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

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

n = int(input())
ans_L = []
for val in range(1,int(n/2+1)):
    if n % val ==0:
        x = val
        y = n/val
        ans_L.append(int(x+y-2))

#print(ans_L)
print(min(ans_L))

### FIXED CODE ###

import math


n = int(input())
ans_L = []
d = []
for val in range(int(math.sqrt(n)+1),0,-1):
    if n % val ==0:
        x = val
        y = int(n/val)
        #st = str(x) + "*" +str(y)
        #d.append(st) 
        #ans_L.append(int(x+y-2))
        print(int(x+y-2))
        exit()
#print(d)
#print(ans_L)
#print(min(ans_L))
### BUGGY CODE ###

import re

s = input()
pattern = "(01)|(10)"
count = 0
f = True
while f:
    l = re.findall(pattern,s)
    count += len(l)*2
    s = re.sub(pattern, "", s)
    f = len(l)


print(count)

### FIXED CODE ###

import re

s = input()
zero = re.findall("0", s)
one = re.findall("1", s)
print(2 * min(len(zero), len(one)))
### BUGGY CODE ###

import numpy as np

n, m = map(int, input().split())
tail = []
head = []
cost = []
for _ in range(m):
  l, r, c = map(int, input().split())
  tail.append(l - 1)
  head.append(r - 1)
  cost.append(c)
tail += list(range(1, n))
head += list(range(n - 1))
cost += [0] * (n - 1)

tail = np.array(tail, dtype=np.int)
head = np.array(head, dtype=np.int)
cost = np.array(cost, dtype=np.int)

inf = cost.sum() + 1
dp = np.ones(n, dtype=np.int) * inf
dp[0] = 0
act = 0
unexplr = np.ones(n, dtype=np.bool)
unexplr[0] = False
while unexplr[-1]:
  edge = (tail == act)
  dp[head[edge]] = np.minimum(dp[head[edge]], dp[act] + cost[edge])
  tmp = np.ones(n, dtype=np.int) * inf
  tmp[unexplr] = dp[unexplr]
  act = tmp.argmin()
  unexplr[act] = False
if dp[-1] < inf:
  print(dp[-1])
else:
  print(-1)

### FIXED CODE ###

import heapq

n, m = map(int, input().split())
edge = [[]] + [[(0, i)] for i in range(n-1)]
for _ in range(m):
  l, r, c = map(int, input().split())
  edge[l-1].append((c, r-1))

inf = 1 << 60
dp = [0] + [inf] * (n - 1)
queue = [(0, 0)]
check = [False] * n
while queue and not check[-1]:
  dist, act = heapq.heappop(queue)
  check[act] = True
  for cost, vertex in edge[act]:
    if check[vertex]:
      continue
    d = dist + cost
    if dp[vertex] > d:
      heapq.heappush(queue, (d, vertex))
      dp[vertex] = d
if dp[-1] < inf:
  print(dp[-1])
else:
  print(-1)
### BUGGY CODE ###

n = int(input())
i = 1

while True:
    x = i
    if  x % 3 == 0:
        print(" %d" ,i)
        i+=1
        if i > n:
            print()
            break
    if x % 10 == 3:
        print(" %d" ,i)
        i+=1
        if i > n:
            print()
            break
    else:
        x /= 10
        if x != 0:
            if x % 10 == 3:
                print(" %d" ,i)
                i+=1
                if i > n:
                    print()
                    break


### FIXED CODE ###

#
# 5d
#

def main():
    n = int(input())
    s = ""
    for i in range(1, n+1):
        x = i
        if x % 3 == 0 or x % 10 == 3:
            s += " " + str(i)
        else:
            x //= 10
            while x:
                if x % 10 == 3:
                    s += " " + str(i)
                    break
                x //= 10
    print(s)


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

import sys
sys.setrecursionlimit(6009)
from collections import defaultdict
dp=defaultdict(lambda:0)

s=input()
n=len(s)
t=input()
m=len(t)
def lcs(x,y):
	
	if min(x,y)<=-1:
		return ""
	if dp[(x,y)]!=0:
		return dp[(x,y)]
	if s[x]==t[y]:
		dp[(x,y)]=lcs(x-1,y-1)+s[x]
		return dp[(x,y)]
	a=lcs(x-1,y)
	b=lcs(x,y-1)
	if len(a)>len(b):
		dp[(x,y)]=a
		return a
	else:
		dp[(x,y)]=b
		return b
print(lcs(n-1,m-1))

### FIXED CODE ###

s=input()
t=input()
n=len(s)
m=len(t)
dp=[[0 for j in range(m+1)] for i in range(n+1)]
for i in range(1,n+1):
	for j in range(1,m+1):
		if s[i-1]==t[j-1]:
			dp[i][j]=dp[i-1][j-1]+1
		else:
			dp[i][j]=max(dp[i-1][j],dp[i][j-1])
i=n
j=m
st=""
while dp[i][j]:
	while dp[i-1][j]==dp[i][j]:
		i-=1
	while dp[i][j-1]==dp[i][j]:
		j=j-1
	j-=1
	st+=s[i-1]
	i-=1
print(st[::-1])
### BUGGY CODE ###


from collections import deque
H, W = map(int, input().split())
k=[]
l=[]
for i in range(W):
    ta,tb = map(int, input().split())
    if ta == 1:
        k.append(tb)
    if tb == H:
        l.append(ta)
s = 0
for i in range(len(k)):
    for j in range(len(l)):
        if k[i] == l[j]:
            s = 1
if s ==1:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

### FIXED CODE ###

from collections import deque
H, W = map(int, input().split())
k=[0]*200000
for i in range(W):
    ta,tb = map(int, input().split())
    if ta == 1:
        k[tb-1]+=1
    if tb == H:
        k[ta-1]+=1
s = 0
for i in range(len(k)):
    if k[i]>=2:s=1
if s ==1:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")
### BUGGY CODE ###

import heapq

n, m = map(int, input().split())
prices = [int(p) for p in input().split()]
heapq._heapify_max(prices)
for _ in range(m):
    prices[0] //= 2
    heapq._heapify_max(prices)
print(sum(prices))

### FIXED CODE ###

import heapq

n, m = map(int, input().split())
prices = [-int(p) for p in input().split()]
heapq.heapify(prices)
for _ in range(m):
  p = heapq.heappop(prices)
  heapq.heappush(prices, p / 2)
print(-sum(int(p) for p in prices))
### BUGGY CODE ###

N = int(input())
a = input().split(' ')
ans = []
for i in range(1,N+1):
    ans.append(a.count(str(i)))
for j in ans:
    print(j)

### FIXED CODE ###

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

ans = [0]*N

for i in A:
    ans[i - 1] += 1
print('\n'.join(map(str,ans)))
### BUGGY CODE ###

import bisect

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

l.sort()
ans=0
for i in range(n):
    for j in range(i+1,n):
        ans+=bisect.bisect_left(l[j+1:], l[i]+l[j])

print(ans)


### FIXED CODE ###

from bisect import bisect_left
N = int(input())
L = sorted(list(map(int, input().split())))
 
ans = 0
for i in range(N):  # １番短い棒
    for j in range(i + 1, N):  # 真ん中の長さの棒
        ans += bisect_left(L, L[i] + L[j]) - (j + 1)
 
print(ans)
### BUGGY CODE ###

N, K= (map(int, input().split()))
number_list = [N]
while True:
    a = abs(N-K)
    if a in number_list:
        break
    else:    
        number_list.append(a)
        N = a
print(min(number_list))

### FIXED CODE ###

N, K= (map(int, input().split()))
a = N % K
b = abs(a-K)
if a > b:
    print(b)
else:
    print(a)
### BUGGY CODE ###

s = list(input())

k = len(s)
i = 0
j = 0

for t in range(1000000000000):
    if i+1 >= k-j or len(s)==1:
        break
    elif s[i] + s[i+1] =='01' or s[i] + s[i+1] =='10':
        del s[i]
        del s[i]
        i = 0
        j = j + 2
    else:
        i = i+1


print(j)

### FIXED CODE ###

s = list(input())


if s.count('0') >= s.count('1'):
    print(s.count('1')*2)
else:
    print(s.count('0')*2)
### BUGGY CODE ###

def main():
    from fractions import gcd
    import sys
    input = sys.stdin.readline

    # def GCD(a: int, b: int) -> int:
    #     return a if b == 0 else GCD(b, a % b)

    class SegTree():
        def __init__(self, n_, ele_id, operation_func):
            self.n = 1
            while self.n < n_:
                self.n *= 2
            self.data = [ele_id] * (2 * self.n - 1)
            self.ele_id = ele_id
            self.operation_func = operation_func

        def __getitem__(self, idx):
            return self.data[idx + self.n - 1]

        def init(self, data_init):
            for i in range(len(data_init)):
                self.data[i + self.n - 1] = data_init[i]
            for i in range(self.n - 2, -1, -1):
                self.data[i] = self.operation_func(self.data[2 * i + 1],
                                                   self.data[2 * i + 2])

        def update(self, idx, x):
            # idx番目の要素をxに更新する
            idx += self.n - 1
            self.data[idx] = x
            while idx > 0:
                idx = (idx - 1) // 2
                self.data[idx] = self.operation_func(self.data[2 * idx + 1],
                                                     self.data[2 * idx + 2])

        def query(self, a, b):
            return self.query_(a, b, 0, 0, self.n)

        def query_(self, a, b, k, l, r):
            # [a, b)の最小値を求める
            if r <= a or b <= l:
                # [a, b)が[l, r)と交差しない
                return self.ele_id

            if a <= l and r <= b:
                # [a, b)が[l, r)を完全に含む
                return self.data[k]
            else:
                # [a, b)と[l, r)は一部被る
                child_l = self.query_(a, b, 2 * k + 1, l, (l + r) // 2)
                child_r = self.query_(a, b, 2 * k + 2, (l + r) // 2, r)
                return self.operation_func(child_l, child_r)

    n = int(input())
    a = tuple(map(int, input().split()))
    seg_gcd = SegTree(n, 0, gcd)
    seg_gcd.init(a)

    ans = seg_gcd.data[0]
    for i in range(n):
        seg_gcd.update(i, 0)
        ans = max(ans, seg_gcd.data[0])
        seg_gcd.update(i, a[i])

    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

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

def GCD(a: int, b: int) -> int:
    return a if b == 0 else GCD(b, a % b)

l = [0]
r = [0]
for i in range(n):
    l.append(GCD(l[i], a[i]))
    r.append(GCD(r[i], a[n-1 - i]))
r = r[::-1]

ans = 1
for i in range(n):
    ans = max(ans, GCD(l[i], r[i+1]))

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

def main():
    import sys
    input = sys.stdin.readline
    from collections import deque

    N = int(input())
    # 1-indexed
    A = [deque() for _ in range(N+1)]
    # O(N^2)
    for i in range(1,N+1):
        for j in input().split():
            A[i].append(int(j))

    # O(N)
    def is_not_empty():
        for x in A:
            if x:
                return True
        return False

    answer = 0
    while is_not_empty():
        if answer == N*(N-1)//2:
            print(-1)
            exit()
        played = set()
        for i in range(1,N+1):
            if i in played:
                continue
            if not A[i]:
                continue
            enemy = A[i].popleft()
            ME = A[enemy].popleft()
            if ME == i and not(enemy in played):
                played.add(ME)
                played.add(enemy)
            else:
                A[i].appendleft(enemy)
                A[enemy].appendleft(ME)
        if not played:
            print(-1)
            exit()
        answer += 1

    print(answer)

if __name__ == '__main__':
    main()

### FIXED CODE ###

# O(N)
def is_not_empty(A):
    for x in A:
        if x:
            return True
    return False

def main():
    import sys
    input = sys.stdin.readline
    from collections import deque

    N = int(input())
    # 1-indexed
    A = [deque() for _ in range(N+1)]
    # O(N^2)
    for i in range(1,N+1):
        for j in input().split():
            A[i].append(int(j))

    # 当日の参加者
    today = set()
    # 初日
    for i in range(1,N+1):
        # 既に参加した人はダメ
        if i in today:
            continue
        enemy = A[i].popleft()
        ME = A[enemy].popleft()
        if ME == i and not(enemy in today):
            today.add(ME)
            today.add(enemy)
        else:
            A[i].appendleft(enemy)
            A[enemy].appendleft(ME)
    # 初日に誰も試合できなかったとき
    if not today:
        print(-1)
        exit()

    # 前日の参加者
    yesterday = today
    # 日数
    answer = 1
    while is_not_empty(A):
        today = set()
        # 前日に試合した人は必ず次の日に試合する
        for i in yesterday:
            if not A[i]:
                continue
            if i in today:
                continue
            enemy = A[i].popleft()
            ME = A[enemy].popleft()
            if ME == i and not(enemy in today):
                today.add(ME)
                today.add(enemy)
            else:
                A[i].appendleft(enemy)
                A[enemy].appendleft(ME)
        if not today:
            print(-1)
            exit()
        answer += 1
        yesterday = today

    print(answer)

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

import numpy as np
N, M = map(int, input().split())
A = np.array(sorted(list(map(int, input().split()))))
BC = []
for _ in range(M):
  bc = list(map(int, input().split()))
  A[:bc[0]][A[:bc[0]]<bc[1]] = bc[1]
  A = np.sort(A)
print(sum(A))

### FIXED CODE ###

N, M = map(int, input().split())
A = list(map(int, input().split()))
BC = []
for _ in range(M):
  BC.append(list(map(int, input().split())))
BC = sorted(BC, key=lambda x:x[1],reverse=True)  
for b, c in BC:
  A.extend([c] * b)
  if len(A)>=2*N:
    break
A = sorted(A, reverse=True)
print(sum(A[:N]))
### BUGGY CODE ###

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

for i in range(N):
    if K-Q+A.count(i)>0:
        print("Yes")
    else:
        print("No")

### FIXED CODE ###

N,K,Q=map(int, input().split())
S=[0]*N
for _ in range(Q):
    S[int(input())-1]+=1

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

N, K = map(int, input().split())
h = list(map(int, input().split()))
DP = [0]*N
DP[1] = abs(h[1]-h[0])

for i in range(2, N):
    DP[i] = min(abs(h[i]-h[j]) + DP[j] for j in range(max(0, i-K), i))
print(DP[-1])

### FIXED CODE ###

def main():

    N, K = map(int, input().split())
    h = list(map(int, input().split()))
    DP = [0]*N
    DP[1] = abs(h[1]-h[0])

    for i in range(2, N):
        DP[i] = min(abs(h[i]-h[j]) + DP[j] for j in range(max(0, i-K), i))
    print(DP[-1])
    
main()
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
x = []
x = [0 for i in range(n)]
for j in range(n):
    x.pop(a[j] - 1)
    x.insert(a[j] - 1, j + 1)
print(" ".join(map(str, x)))


### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
x = []
for i in range(n):
    x.append((a[i], i + 1))
x.sort()
y = []
for i in range(n):
    y.append(x[i][1])
print(" ".join(map(str, y)))
### BUGGY CODE ###

N, M = map(int, input().split())
shop = [list(map(int, input().split())) for _ in range(N)]
drink = 0
money = 0

shop.sort(key=lambda x: x[0])

for i in range(N):
    if drink + shop[i][1] <= M:
        drink += shop[i][1]
        money += shop[i][0] * shop[i][1]
        if drink == M:
            print(money)
            break
    else:
        for j in range(shop[i][1]):
            drink += 1
            money += shop[i][0]
            if drink == M:
                print(money)
                break



### FIXED CODE ###

from bisect import bisect_left
from itertools import accumulate

N, M = map(int, input().split())
shop = [list(map(int, input().split())) for _ in range(N)]
shop.sort(key=lambda x: x[0])

cnt = 0
ans = 0

for i in range(N):
    cnt += shop[i][1]
    if M <= cnt:
        dif = cnt - M
        ans += shop[i][0] * shop[i][1] - dif * shop[i][0]
        break
    else:
        ans += shop[i][0] * shop[i][1]

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

#-*-coding:utf-8-*-

def count(s, c):
    cnt = 0
    for i in s:
        if i == c:
            cnt += 1
    return cnt

def main():
    #入力
    N = int(input())
    S = input()

    min_cnt = 300000
    ew = ['E', 'W']

    for i in range(N):
        first_str = S[:i]
        last_str = S[i+1:]

        cnt = 0
        cnt_too_much_flag = 0

        for j in first_str:
            if j == 'W':
                cnt += 1
            elif cnt_too_much_flag == 1:
                break
            elif cnt > min_cnt:
                cnt_too_much_flag = 1
        for j in last_str:
            if j == 'E':
                cnt += 1
            elif cnt_too_much_flag == 1:
                break
            elif cnt > min_cnt:
                cnt_too_much_flag = 1

        if cnt < min_cnt:
            min_cnt = cnt
        #print(first_str, last_str, cnt)
    
    
    print(min_cnt)
            

        


if __name__ == '__main__':
    main()

### FIXED CODE ###

#-*-coding:utf-8-*-

#累積和を求める
def get_cum_sum(s, c):
	cum_sum =[]
	cnt = 0
	
	for i in s:
		if i == c:
			cnt += 1
			cum_sum.append(cnt)
		else:
			cum_sum.append(cnt)
			
	return cum_sum
    
	

def main():
    #入力
    N = int(input())
    S = input()
		
    cum_sum_w = get_cum_sum(S, 'W')
    cum_sum_e = get_cum_sum(S, 'E')
    min_cnt = 300000
    
    for i in range(N):
    	if S[i] == 'W':
    		first_total_w = cum_sum_w[i] - 1
    	else:
    		first_total_w = cum_sum_w[i]
    		
    	last_total_e = cum_sum_e[-1] - cum_sum_e[i]
    	
    	#print(S[:i], S[i+1:], first_total_w, last_total_e)
    	
    	if min_cnt > first_total_w + last_total_e:
    		min_cnt = first_total_w + last_total_e
    
    print(min_cnt)
    	
    	
        


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

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

bc.sort()
for i in range(m):
    a.sort()
    if sum(a[0:bc[i][0]]) < bc[i][0]*bc[i][1]:
        for j in range(bc[i][0]):
            a[j] = bc[i][1]

print(sum(a))


### FIXED CODE ###

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

a.sort()
bc.sort(reverse=True,key=lambda x:x[1])
t = 0
for i in range(m):
    for j in range(bc[i][0]):
        if t != n:
            if a[t] < bc[i][1]:
                a[t] = bc[i][1]
                t+=1
            else:
                break
        else:
            break
    else:
        continue
    break

print(sum(a))