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

# import numpy as np
from collections import deque

H,W=map(int,input().split())
CH,CW=map(int,input().split())
DH,DW=map(int,input().split())

S=[list(input()) for _ in range(H)]
MAX_COST = 10 ** 9
Cost=[ [ MAX_COST for _ in range(W)] for _ in range(H)]
# Cost = np.full((H,W),MAX_COST)

# print(S)

ans = -1

deq = deque()

deq.append((CH-1,CW-1,0))
Cost[CH-1][CW-1] = 0;

# used = set()
five_five = [ (i,j) for i in range(-2,3,1) for j in range(-2,3,1) ]
ffCosts = {}
for i,j in five_five:
	# print(i,j)
	if (j == 0 and (i==1 or i==-1)) or (i==0 and (j==1 or j==-1)):
		ffCosts[(i,j)] = 0
	else:
		ffCosts[(i,j)] = 1
# print(five_five)

while 0 < len(deq):
	h,w,c=deq.popleft()
	# print(h,w,c)
	for i,j in five_five:
		# print(i,j)
		if 0 <= h+i and h+i < H and 0 <= w+j and w+j < W:
			if S[h+i][w+j] == '.':
				cAdd = ffCosts[(i,j)]
				if c + cAdd < Cost[h+i][w+j]:
					Cost[h+i][w+j] = c + cAdd
					if (h+i,w+j,Cost[h+i][w+j]) not in deq:
						if cAdd == 0:
							deq.appendleft((h+i,w+j,Cost[h+i][w+j]))
						else:
							deq.append((h+i,w+j,Cost[h+i][w+j]))


if Cost[DH-1][DW-1] == MAX_COST:
	print(-1)
else:
	print(Cost[DH-1][DW-1])

### FIXED CODE ###

from collections import deque

H,W=map(int,input().split())
CH,CW=map(int,input().split())
DH,DW=map(int,input().split())

S=[list(input()) for _ in range(H)]
MAX_COST = 10 ** 9
Cost=[ [ MAX_COST for _ in range(W)] for _ in range(H)]

# print(S)

ans = -1

deq = deque()

deq.append((CH-1,CW-1,0))
Cost[CH-1][CW-1] = 0;

walk=[(1,0),(0,1),(-1,0),(0,-1)]

# used = set()

while 0 < len(deq):
	h,w,c=deq.popleft()
	# print(h,w,c)
	for i,j in walk:
		if 0 <= h+i and h+i < H and 0 <= w+j and w+j < W:
			if S[h+i][w+j] == '.' and c < Cost[h+i][w+j]:
				Cost[h+i][w+j] = c
				# print("updl ", i,j,h+i,w+j,c)
				deq.appendleft((h+i,w+j,Cost[h+i][w+j]))
	for i in range(-2,3,1):
		for j in range(-2,3,1):
			# print(i,j)
			if 0 <= h+i and h+i < H and 0 <= w+j and w+j < W:
				if S[h+i][w+j] == '.':
					if c + 1 < Cost[h+i][w+j]:
						Cost[h+i][w+j] = c + 1
						deq.append((h+i,w+j,Cost[h+i][w+j]))
						# print("updr ", h+i,w+j,Cost[h+i][w+j])

if Cost[DH-1][DW-1] == MAX_COST:
	print(-1)
else:
	print(Cost[DH-1][DW-1])
### BUGGY CODE ###

import sys

N = int(input())
A = [[int(i) for i in input().split()] for i in range(N)]

ans=0
empty = [[] for n in range(N)]

for i in range(N*(N-1)//2):
    change=0
    stamina=[1]*N
    for g in range(N):
        if A[g]!=[] and stamina[g]==1 and stamina[A[g][0]-1]==1:
            if g+1 == A[A[g][0]-1][0]:
                _pop = A[g].pop(0)
                A[_pop-1].pop(0)
                stamina[g]=0
                stamina[_pop-1]=0
                change+=1
    ans+=1
    if change==0:
        break
    if A==empty:
        print(ans)
        sys.exit()

print(-1)

### FIXED CODE ###

import sys
from collections import deque

N = int(input())
A = [deque([int(i) for i in input().split()]) for i in range(N)]

ans=0
empty = [deque() for i in range(N)]
pre_fight = set([i for i in range(N)])
record = set()

while True:
    for g in pre_fight:
        if A[g]!=deque():
            if g+1 == A[A[g][0]-1][0]:
                record.add(g)
                record.add(A[g][0]-1)
    if record==set():
        break
    else:
        for i in record:
            A[i].popleft()
    ans+=1
    pre_fight = record
    record = set()
    if A==empty:
        print(ans)
        sys.exit()

print(-1)
### BUGGY CODE ###

n = int(input())
suuretu = list(map(int,input().split()))
nn = frg = 0

for nn in range(0,n-1):
    for mm in range(nn+1,n):
        if suuretu[nn] == suuretu[mm]:
            frg = 1
            break
    else:
        if frg == 1:
            break
if frg == 1:
    print('NO')
else:
    print('YES')

### FIXED CODE ###

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

if len(li) == len(set(li)):
    print('YES')
else:
    print('NO')
### BUGGY CODE ###


def main():
  s = input()
  n = len(s)

  mod = 2019

  counts = {}
  counts[0] = 1

  prev = int(s[-1])
  counts[prev % mod] = 1
  for i in range(2, n + 1):
    t = (prev + int(s[-i]) * 10 ** (i - 1)) % mod
    if t in counts:
      counts[t] += 1
    else:
      counts[t] = 1

    prev = t

  ans = 0
  for count in counts.values():
    if count > 1:
      ans += count * (count - 1) // 2

  print(ans)

main()


### FIXED CODE ###


def main():
  s = map(int, input()[::-1])

  mod = 2019

  counts = [0] * mod
  counts[0] = 1
  t = 0
  x = 1
  for num in s:
    t = (t + num * x) % mod
    counts[t] += 1
    x = (x * 10) % mod

  ans = 0
  for count in counts:
    if count > 1:
      ans += count * (count - 1) // 2

  print(ans)

main()
### BUGGY CODE ###

n = int(input())
s = [input() for _ in range(n)]

ans = [[0]*26 for _ in range(n)]
for i in range(n):
    for j in range(97,123):
        ans[i][j-97] = s[i].count(chr(j))


cnt = 0
for i in range(n-1):
    for j in range(i+1,n):
        if ans[i] == ans[j]:
            cnt += 1

print(cnt)

### FIXED CODE ###

import collections as c

N = int(input())
S = sorted(["".join(sorted(input())) for _ in range(N)])

D = c.Counter(S)

D_value = []

for a in D.values():
	D_value.append(a)

ans = 0

for i in D_value:
	if i == 0:
		continue
	ans += (i * (i-1)) // 2

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

from scipy.sparse.csgraph import floyd_warshall as wf
n=int(input())
s=[list(map(float,input().split()))for i in range(n)]
a=wf(s,directed=False).tolist()
if s!=a:
    print(-1)
else:
    c=0
    for i in range(n):
        s[i][i]=float("inf")
    for i in range(n):
        for j in range(i):
            d=min(map(sum,zip(s[i],s[j])))
            if s[i][j]<d:
                c+=int(s[i][j])
    else:
        print(c)

### FIXED CODE ###

import numpy as np
from scipy.sparse.csgraph import floyd_warshall as wf
n=int(input())
s=np.array([list(map(int,input().split()))for i in range(n)])
if np.any(s!=wf(s,directed=False)):
    print(-1)
else:
    c=0
    for i in range(n):
        s[i][i]=10**10
    for i in range(n):
        for j in range(i+1,n):
            d=np.min(s[i]+s[j])
            if s[i,j]!=d:
                c+=s[i,j]
    else:
        print(c)
### 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(dp[n])


### 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 ###

from collections import deque


def bfs():
    for i in range(n):
        q = deque(tree[i])
        while q:
            v = q.popleft()
            for node in tree[v]:
                q.append(node)
                tree[i].append(node)


n, q = map(int, input().split())
tree = [[] for i in range(n)]
operate = [0] * n
ans = [0] * n
for _ in range(0, n - 1):
    a, b = map(int, input().split())
    tree[a - 1].append(b - 1)

bfs()

for _ in range(q):
    p, x = map(int, input().split())
    operate[p - 1] += x
for i in range(0, n):
    ans[i] += operate[i]
    for j in tree[i]:
        ans[j] += operate[i]
print(*ans)


### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
# 深さ優先探索で各直線を考える


def main():
    def dfs(v, p):
        for u in tree[v]:
            if u == p:
                continue
            # 累積和の計算
            ans[u] += ans[v]
            dfs(u, v)

    n, q = map(int, input().split())
    # tree[i]: 頂点i+1の子どもたち
    tree = [[] for i in range(n)]
    ans = [0] * n

    for _ in range(0, n - 1):
        a, b = map(int, input().split())
        tree[a - 1].append(b - 1)
        tree[b - 1].append(a - 1)

    for _ in range(q):
        p, x = map(int, input().split())
        ans[p - 1] += x

    # 根ノードの頂点 1 から開始
    dfs(0, -1)

    print(*ans)


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

import math
from math import floor
A,B,N = map(int,input().split())
maxi = 0
Npower = 0
diff = 0
S = N
while S/10 >= 1:
    Npower += 1
    S /=10
if Npower >= 7:
    for i in range(0,10**6+10**5):
        maxi = max(floor((A*i)/B)-A*floor(i/B),maxi)
    for i in range(N-3*10**6,N+1):
        maxi = max(floor((A*i)/B)-A*floor(i/B),maxi)
else:
    for i in range(0,N+1):
        maxi = max(floor((A*i)/B)-A*floor(i/B),maxi)
print(max(maxi,0))


### FIXED CODE ###

import math
from math import floor
A,B,N = map(int,input().split())
def f(x):
  return floor(A*x/B) - A*floor(x/B)
print(f(min(B-1,N)))
### BUGGY CODE ###

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


X = [[0] * W for i in range(H)]
for h in range(H):
    for w in range(W):
        X[h][w] = abs(A[h][w] - B[h][w])


# dp[h][w][x] := (h, w)の時点で差をxにできるか？
M = H * W * 80
dp = [[[False] * (M + 1) for j in range(W)] for i in range(H)]
dp[0][0][X[0][0]] = True


for h in range(H):
    for w in range(W):
        for m in range(M):
            nx = X[h][w]
            if (0 <= h - 1) and abs(m + X[h][w] <= M):
                dp[h][w][m] = dp[h][w][m] or dp[h - 1][w][abs(m + X[h][w])]

            if (0 <= h - 1) and abs(m - X[h][w] <= M):
                dp[h][w][m] = dp[h][w][m] or dp[h - 1][w][abs(m - X[h][w])]

            if (0 <= w - 1) and abs(m + X[h][w] <= M):
                dp[h][w][m] = dp[h][w][m] or dp[h][w - 1][abs(m + X[h][w])]

            if (0 <= w - 1) and abs(m + X[h][w] <= M):
                dp[h][w][m] = dp[h][w][m] or dp[h][w - 1][abs(m - X[h][w])]


ans = float('inf')
for x in range(M + 1):
    if dp[H - 1][W - 1][x]:
        ans = min(ans, x)

print(ans)


### FIXED CODE ###

def main():
    import sys

    H, W = map(int, sys.stdin.readline().split())
    A = [list(map(int, sys.stdin.readline().split())) for i in range(H)]
    B = [list(map(int, sys.stdin.readline().split())) for i in range(H)]
    X = [[0] * W for i in range(H)]
    for h in range(H):
        for w in range(W):
            X[h][w] = abs(A[h][w] - B[h][w])

    dp = [[set() for j in range(W)] for i in range(H)]
    dp[0][0].add(X[0][0])
    dp[0][0].add(-X[0][0])

    for h in range(H):
        for w in range(W):
            if h == 0 and w == 0:
                continue
            x = X[h][w]
            s = set()

            if h > 0:
                for d in dp[h - 1][w]:
                    s.add(d + x)
                    s.add(abs(d - x))

            if w > 0:
                for d in dp[h][w - 1]:
                    s.add(d + x)
                    s.add(abs(d - x))

            dp[h][w] = s

    ans = min([abs(s) for s in dp[H - 1][W - 1]])
    print(ans)


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

#!/usr/bin/env python3
h,w,d = map(int,input().split())
ans = 0
x = [0]*(h*w+1)
y = [0]*(h*w+1)
for i in range(h):
    a = list(map(int,input().split()))
    for j in range(w):
        x[a[j]] = j
        y[a[j]] = i
q = int(input())
for i in range(q):
    l,r = map(int,input().split())
    ans = 0
    for i in range((r-l)//d): 
        ans += abs(x[l+d*i]-x[l+d*(i+1)])+abs(y[l+d*i]-y[l+d*(i+1)])
    print(ans)

### FIXED CODE ###

#!/usr/bin/env python3
import sys
input = sys.stdin.readline
h,w,d = map(int,input().split())
ans = 0
x = [0]*(h*w+1)
y = [0]*(h*w+1)
for i in range(h):
    a = list(map(int,input().split()))
    for j in range(w):
        x[a[j]] = j
        y[a[j]] = i
q = int(input())
#飛び飛びの累積和をとる　視点と
cum_sum_d = [0]*(h*w+1)
for i in range(d,h*w+1):
    cum_sum_d[i] =  cum_sum_d[i-d] + abs(x[i]-x[i-d])+abs(y[i]-y[i-d])
for i in range(q):
    l,r = map(int,input().split())
    ans = cum_sum_d[r] - cum_sum_d[l]
    
    """ #TLE解
    for i in range((r-l)//d): 
        ans += abs(x[l+d*i]-x[l+d*(i+1)])+abs(y[l+d*i]-y[l+d*(i+1)])
        """
    print(ans)
### BUGGY CODE ###

n, q = map(int, input().split())
s = input()
l = [0] * q
r = [0] * q
for i in range(0, q):
    l[i], r[i] = map(int, input().split())
for i in range(0,q):
    print(s[l[i] - 1:r[i]].count('AC'))

### FIXED CODE ###

n, q = map(int, input().split())
s = ' ' + input()
heap = [0] * (n + 1)
cnt = 0
for i in range(2, n + 1):
    if s[i - 1] == 'A' and s[i] == 'C':
        cnt += 1;
    heap[i] = cnt
ans = []
for i in range(q):
    l, r = map(int, input().split())
    ans.append(heap[r] - heap[l])
for i in ans:
    print(i)
### BUGGY CODE ###

N=int(input())
import sys
ans=[]
A=list(map(int,sys.stdin.readline().split()))
def divisor(N):
   S=[]
   for i in range(1,int(N**0.5)+1):
      if N%i==0:
         S.append(i)
         if N//i != i:
            S.append(N//i)
   return S
for i in reversed(range(1,N+1)):
   if A[i-1] == 1:
      ans.append(i)
      tmp=divisor(i)
      for j in tmp:
         A[j-1] = A[j-1] ^ 1
if ans == []:
   print(0)
   exit()
else:
   print(len(ans))
   print(*ans)

### FIXED CODE ###

N = int(input())
l = list(map(int, input().split()))
a = [0] * (N+1)
for k in reversed(range(1, N+1)):
    num = sum([a[k*i] for i in range(1, N//k+1)])
    if num % 2 != l[k-1]:
        a[k] = 1
M = sum(a)
ans = [i for i in range(1, N+1) if a[i] > 0]
 
print(M)
print(' '.join(map(str, ans)))
### BUGGY CODE ###

def main():
    I=lambda:list(map(int,input().split()))
    n,m=I()
    e=eval('(I()[0],I()),'*m)
    I=9**9
    dp=[I]*2**n
    dp[0]=0
    for i,dpi in enumerate(dp):
        if dpi==I:continue
        for a,c in e:
            b=i
            for j in c:b|=2**(n-j)
            cost=dpi+a
            if dp[b]>cost:dp[b]=cost
    print(-(dp[-1]==I)or dp[-1])
main()

### FIXED CODE ###

import sys
input=sys.stdin.readline
n,m=map(int,input().split())
e=[(int(input().split()[0]),list(map(int,input().split())))for _ in range(m)]
INF=10**18
dp=[INF]*2**n
dp[0]=0
for i in range(2**n):
    if dp[i]>=INF:continue
    for a,c in e:
        bit=i
        for j in c:
            bit|=2**(n-j)
        dp[bit]=min(dp[bit],dp[i]+a)
a=dp[-1]
if a>=INF:
    print(-1)
else:
    print(dp[-1])
### BUGGY CODE ###

x, y, z, k = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))

a.sort(reverse=True)
b.sort(reverse=True)
c.sort(reverse=True)

ab = []
for i in a[:k]:
    for j in b[:k]:
        ab.append(i+j)
ab.sort(reverse=True)
ab = ab[:k]

abc = []
for i in ab:
    for j in c[:k]:
        abc.append(i+j)
abc.sort(reverse=True)

for i in abc[:k]:
    print(i)


### FIXED CODE ###

x, y, z, k = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))

ab = []
for i in a:
    for j in b:
        ab.append(i+j)
ab.sort(reverse=True)
ab = ab[:k]

abc = []
for i in ab:
    for j in c:
        abc.append(i+j)
        
abc.sort(reverse=True)
for i in abc[:k]:
    print(i)
### BUGGY CODE ###

from statistics import mean
n,k = map(int,input().split())
list = input().split()
expectation = []
for i in range(len(list)):
  expectation.append((1+int(list[i]))/2)
max = 0
for i in range(n-k+1):
  tmp = sum(expectation[i:i+k])
  if tmp > max:
    max = tmp
print(max)

### FIXED CODE ###

N,K=map(int,input().split())
p=list(map(int,input().split()))
ave=[0]*(N-K+1)
tmp=0
for i in range(K):
    tmp+=(p[i]+1)/2
ave[0]=tmp
for i in range(1,N-K+1):
    ave[i]=ave[i-1]-(p[i-1]+1)/2 + (p[i+K-1]+1)/2
print(max(ave))
### BUGGY CODE ###

#!/usr/bin/env python3


def read_h(typ=int):
    return list(map(typ, input().split()))


def read_v(n, m=1, typ=int):
    return [read_h() if m > 1 else typ(input()) for _ in range(n)]


def main():
    N, = read_h()
    A = read_h()

    import numpy as np

    a = np.asarray([[1 if i == j or i - 1 == j or i + N - 1 == j else 0
                     for j in range(N)]
                    for i in range(N)])
    b = np.asarray(A) * 2
    inv_a = np.linalg.pinv(a)
    x = list(map(int, map(np.round, np.dot(inv_a, b))))

    print(x[-1], *x[:-1])


if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3


def read_h(typ=int):
    return list(map(typ, input().split()))


def read_v(n, m=1, typ=int):
    return [read_h() if m > 1 else typ(input()) for _ in range(n)]


def main():
    N, = read_h()
    A = read_h()

    x1 = sum(A) - 2 * sum(a for i, a in enumerate(A) if i % 2 != 0)
    ans = [x1]

    for i in range(N - 1):
        ans.append(2 * A[i] - ans[i])

    print(*ans)


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

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

amounts = [0] * N

for n in range(N):
    spot = A[:n] + A[(n+1):]

    amount = 0
    for i in range(1, N - 1):
        amount += abs(spot[i-1] - spot[i])
    amount += abs(spot[0])
    amount += abs(spot[N - 2])
    amounts[n] = amount

for i in range(N):
    print(amounts[i])


### FIXED CODE ###

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

total = 0
total = abs(A[0])
total += abs(A[N - 1])
for i in range(1, N):
    total += abs(A[i - 1] - A[i])

amounts = [0] * N
for i in range(N):
    left = 0
    right = 0
    if i > 0:
        left = A[i - 1]
    if i < N - 1:
        right = A[i + 1]
    amounts[i] = total + abs(left - right) - (abs(left - A[i]) + abs(A[i] - right))

for i in range(N):
    print(amounts[i])
### BUGGY CODE ###

def comb(n,k):
    nCk = 1
    MOD = 10**9+7
    # X
    for i in range(n-k+1, n+1):
        nCk *= i
        nCk %= MOD

    # Y
    for i in range(1,k+1):
        nCk *= pow(i,MOD-2,MOD)
        nCk %= MOD
    return nCk

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

cnt = [0]*(n+1)
total = 0
ans = 0

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

for i in range(n):
    total += comb(cnt[i], 2)

for i in range(n):
    print(total - comb(cnt[a[i]], 2) + comb(cnt[a[i]] - 1, 2))

### FIXED CODE ###

def nC2(n):
    return n*(n-1)//2

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

cnt = [0]*(n+1)
total = 0
ans = 0

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

for i in range(1, n+1):
    total += nC2(cnt[i])

for i in range(n):
    print(total - nC2(cnt[a[i]]) + nC2(cnt[a[i]] - 1))
### BUGGY CODE ###

def partition(A,p,r):
    x=A[r][1]
    i=p-1
    for j in xrange(p,r):
        if A[j][1]<=x:
            i+=1
            A[i],A[j]=A[j],A[i]
    A[i+1],A[r]=A[r],A[i+1]
    return i+1

def quicksort(A,p,r):
    if p<r:
        q=partition(A,p,r)
        quicksort(A,p,q-1)
        quicksort(A,q+1,r)

def bubblesort(a,n):
    flag=1
    while flag:
        flag=0
        if n==0:
            break
        else :
            for i in xrange(n-1,0,-1):
                if a[i][1]<a[i-1][1]:
                    a[i-1],a[i]=a[i],a[i-1]
                    flag=1

n=input()
card_1=[[0]*2 for i in xrange(n)]

for i in xrange(n):
    card_1[i][0],card_1[i][1]=map(str,raw_input().split())
    card_1[i][1]=int(card_1[i][1])

card_2=list(card_1)
quicksort(card_1,0,n-1)
bubblesort(card_2,n)

if card_1==card_2:
    print("Stable")
else :
    print("Not stable")

for i in xrange(n):
    card_1[i]=map(str,card_1[i])
    print(" ".join(card_1[i]))

### FIXED CODE ###

def partition(A,p,r):
    x=A[r][1]
    i=p-1
    for j in xrange(p,r):
        if A[j][1]<=x:
            i+=1
            A[i],A[j]=A[j],A[i]
    A[i+1],A[r]=A[r],A[i+1]
    return i+1

def quicksort(A,p,r):
    if p<r:
        q=partition(A,p,r)
        quicksort(A,p,q-1)
        quicksort(A,q+1,r)

def merge(A,left,mid,right):
    n1=mid-left
    n2=right-mid
    l=[A[left+i] for i in xrange(n1)]
    r=[A[mid+i] for i in xrange(n2)]
    l.append([0,float('inf')])
    r.append([0,float('inf')])
    i=0
    j=0
    for k in xrange(left,right):
        if l[i][1]<=r[j][1]:
            A[k]=l[i]
            i=i+1
        else:
            A[k]=r[j]
            j=j+1

def mergesort(A,left,right):
    if left+1<right:
        mid=(left+right)/2
        mergesort(A,left,mid)
        mergesort(A,mid,right)
        merge(A,left,mid,right)
        
n=input()
card_1=[[0]*2 for i in xrange(n)]

for i in xrange(n):
    card_1[i][0],card_1[i][1]=map(str,raw_input().split())
    card_1[i][1]=int(card_1[i][1])

card_2=list(card_1)
quicksort(card_1,0,n-1)
mergesort(card_2,0,n)

if card_1==card_2:
    print("Stable")
else :
    print("Not stable")

for i in xrange(n):
    card_1[i]=map(str,card_1[i])
    print(" ".join(card_1[i]))
### BUGGY CODE ###

N = int(input())
A = []
for i in range(N):
	l = list(map(int,input().split()))
	A.append([i-1 for i in l])
match_num = [0 for i in range(N)]
match_dict = {}
idx = 0
for i in range(N-1):
	for j in range(i+1, N):
		match_dict[(i,j)] = idx
		idx += 1
M = idx
edge = [[] for i in range(M)]
parent = [[] for i in range(M)]
for i in range(N):
	for j in range(N-2):
		a = A[i][j]
		a_nxt = A[i][j+1]
		x,y = min(i,a), max(i,a)
		z,w = min(i,a_nxt), max(i,a_nxt)
		m1 = match_dict[(x,y)]
		m2 = match_dict[(z,w)]
		edge[m1].append(m2)
		parent[m2].append(m1)
finish = [False for i in range(M)]
candidate = [(i, 0) for i in range(M) if len(parent[i]) == 0]
depth = [-1 for i in range(M)]

# circuit check
search = [c[0] for c in candidate]
edge_copy = [[e for e in edge[i]] for i in range(M)]
parent_copy = [[p for p in parent[i]] for i in range(M)]
while len(search) > 0:
	s = search.pop()
	del_list = []
	for e in edge_copy[s]:
		parent_copy[e].remove(s)
		if len(parent_copy[e]) == 0:
			search.append(e)
			del_list.append(e)
	for e in del_list:
		edge_copy[s].remove(e)
if sum([sum(parent_copy[i]) for i in range(M)]) > 0:
	print(-1)
	exit()

while len(candidate) > 0:
	x = candidate.pop()
	c,d = x[0], x[1]
	if depth[c] >= d:
		continue
	depth[c] = d
	finish[c] = True
	e = None
	for e in edge[c]:
		if depth[e] < d+1:
			candidate.append((e, d+1))
all_finished = all(finish)
if all_finished:
	print(max(depth) + 1)
else:
	print(-1)


### FIXED CODE ###

N = int(input())
A = []
for i in range(N):
	l = list(map(int,input().split()))
	A.append([i-1 for i in l])
match_num = [0 for i in range(N)]
match_dict = {}
idx = 0
for i in range(N-1):
	for j in range(i+1, N):
		match_dict[(i,j)] = idx
		idx += 1
M = idx
edge = [[] for i in range(M)]
parent = [[] for i in range(M)]
for i in range(N):
	for j in range(N-2):
		a = A[i][j]
		a_nxt = A[i][j+1]
		x,y = min(i,a), max(i,a)
		z,w = min(i,a_nxt), max(i,a_nxt)
		m1 = match_dict[(x,y)]
		m2 = match_dict[(z,w)]
		edge[m1].append(m2)
		parent[m2].append(m1)
finish = [False for i in range(M)]
candidate = [i for i in range(M) if len(parent[i]) == 0]
depth = [-1 for i in range(M)]


day = 0
while len(candidate) > 0:
	new_candidate = []
	for c in candidate:
		finish[c] = True
		for e in edge[c]:
			parent[e].remove(c)
			if len(parent[e]) == 0:
				new_candidate.append(e)
		edge[c] = []
	candidate = new_candidate
	day += 1
print(day if all(finish) else -1)
### BUGGY CODE ###

import heapq
import sys

sys.setrecursionlimit(10000)
INF = float('inf')

N, M = list(map(int, input().split()))
A = list(map(int, input().split()))
B, C = zip(*[list(map(int, input().split())) for _ in range(M)])

heap = A
heapq.heapify(heap)


for b, c in zip(B, C):
    for _ in range(b):
        a = heapq.heappop(heap)
        if a < c:
            heapq.heappush(heap, c)
        else:
            heapq.heappush(heap, a)
            break

print(sum(heap))


### FIXED CODE ###

import sys

sys.setrecursionlimit(10000)
INF = float('inf')

N, M = list(map(int, input().split()))
A = list(map(int, input().split()))
CB = [list(map(int, reversed(input().split()))) for _ in range(M)]

A.sort()
CB.sort()

ans = 0
for _ in range(N):
    a = A[-1] if A else -INF
    c, b = CB[-1] if CB else (-INF, -INF)
    if a > c:
        ans += a
        A.pop()
    else:
        ans += c
        CB[-1][1] -= 1
        if CB[-1][1] <= 0:
            CB.pop()
print(ans)