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

s=input()
flag=1
length=len(s)
s_flag=[1 for _ in range(length)]
while flag:
    l=sum(s_flag)
    if l<=1:
        break
    comp=0
    while s_flag[comp]==0:
        comp+=1
    for i in range(comp+1,length):
        if s_flag[i]:
            if s[comp]!=s[i]:
                s_flag[comp]=0
                s_flag[i]=0
                break
            elif i==length-1:
                flag=0
print(length-sum(s_flag))


### FIXED CODE ###


s=input()
length=len(s)
cnt=[0,0]
for i in range(length):
    if s[i]=='0':
        cnt[0]+=1
    else:
        cnt[1]+=1
print(min(cnt)*2)
### BUGGY CODE ###

S=input()
T=input()
len0=len(S)
while len(S)<len(T)*2:
    S=S+S

S=S+S

p=26
mod=(1<<50)+1# 互いに素なものを指定

TABLE=[0]# Rolling Hashのテーブル. 最初は0
LEN=len(S)

for i in range(LEN):
    TABLE.append((p*TABLE[-1]%mod+ord(S[i])-97)%mod)# テーブルを埋める

TABLE2=[0]# Rolling Hashのテーブル. 最初は0
LEN2=len(T)

for i in range(LEN2):
    TABLE2.append((p*TABLE2[-1]%mod+ord(T[i])-97)%mod)# テーブルを埋める

TH=TABLE2[-1]

def hash_ij(i,j): # [i,j)のハッシュ値を求める
    return (TABLE[j]-TABLE[i]*pow(p,j-i,mod))%mod

OK=[0]*LEN

for i in range(LEN2,LEN):
    if hash_ij(i-LEN2,i)==TH:
        OK[i-LEN2]=1

OK=OK[:len0]

ANS=0

for i in range(len0):
    if OK[i]==1:
        USED=[0]*len0

        j=i
        count=0

        while OK[j]==1:
            if USED[j]==1:
                print(-1)
                import sys
                sys.exit()
            count+=1
            USED[j]=1
            j=(j+LEN2)%len0

        ANS=max(ANS,count)

print(ANS)

### FIXED CODE ###

S=list(input())
T=list(input())
len0=len(S)
S=S*(len(T)//len0+1)

S=S+S

p=26
mod=(1<<31)+7# 互いに素なものを指定

TABLE=[0]# Rolling Hashのテーブル. 最初は0
LEN=len(S)

for i in range(LEN):
    TABLE.append((p*TABLE[-1]%mod+ord(S[i])-97)%mod)# テーブルを埋める

NOW=0
LEN2=len(T)

for i in range(LEN2):
    NOW=(p*NOW%mod+ord(T[i])-97)%mod

TH=NOW

def hash_ij(i,j): # [i,j)のハッシュ値を求める
    return (TABLE[j]-TABLE[i]*pow(p,j-i,mod))%mod

OK=[0]*LEN

for i in range(LEN2,LEN):
    if hash_ij(i-LEN2,i)==TH:
        OK[i-LEN2]=1

OK=OK[:len0]

ANS=0

ST=[-1]*len0

for i in range(len0):
    if OK[i]==1 and ST[i]==-1:

        j=i
        count=0

        while OK[j]==1:
            
            if ST[j]!=-1:
                count+=ST[j]
                break
            
            count+=1
            ST[j]=1
            j=(j+LEN2)%len0
            if j==i:
                print(-1)
                import sys
                sys.exit()

        ST[i]=count
        ANS=max(ANS,count)

print(ANS)
### BUGGY CODE ###

from collections import deque
import numpy as np

n, m  = map(int, input().split())
g     = {}
maxD  = np.array([-1 for i in range(n)])
color = np.array([0  for _ in range(n)])

for _ in range(m):
    u, v = map(int, input().split())
    u-=1
    v-=1
    if u not in g:
        g[u] = []
    if v not in g:
        g[v] = []
    g[u].append(v)
    g[v].append(u)
    
q = int(input())
Q = []

for _ in range(q):
    node, dis, col = map(int, input().split())
    Q.append([node-1, dis, col])
Q = Q[::-1]

def bfs(curQ):
    while len(curQ) > 0:
        node, dis, col = curQ.popleft()
    
        if maxD[node] > dis:
            continue
            
        if dis < 0:
            continue
            
        maxD[node] = dis
    
        if color[node] == 0:
            color[node] = col

        if node in g:
            for v in g[node]:
                curQ.append([v, dis-1, col])
                    
for node, dis, col in Q:
    curQ = deque()
    curQ.append([node, dis, col])
    bfs(curQ)

ans = ''
for x in color:
    ans += str(x)+'\n'
print(ans)    


### FIXED CODE ###

n, m  = map(int, input().split())
g     = {}
used  = {i:[False for _ in range(11)] for i in range(n)}
color     = [0  for _ in range(n)]

for _ in range(m):
    u, v = map(int, input().split())
    u-=1
    v-=1
    if u not in g:
        g[u] = []
    if v not in g:
        g[v] = []
    g[u].append(v)
    g[v].append(u)
    
q = int(input())
Q = []

for _ in range(q):
    node, dis, col = map(int, input().split())
    Q.append([node-1, dis, col])
Q = Q[::-1]

def bfs(now, dist, col):
    if dist < 0:
        return
    
    if used[now][dist]:
        return
 
    used[now][dist] = True
    
    if not color[now]:
        color[now] = col
 
    if now in g:
        for x in g[now]:
            bfs(x, dist - 1, col)
            
for node, dis, col in Q:
    bfs(node, dis, col)

for x in color:
    print(x)
### BUGGY CODE ###

from bisect import bisect_left
from bisect import bisect_right


N = int(input())
L = list(map(int, input().split()))
L.sort()

"""
短いほうから２本固定して条件に合うものをさがす（長いほうから２本固定でもOK）
最長と最短を固定するとややこしくなるから、こういう場合は最長/最短どちらかから固定するほうがいいか
"""


ans = 0
for i in range(N):
    for j in range(i+1, N):
        l = L[j] - L[i]
        r = L[j] + L[i]

        #  a < b < c（場合によっては等号を含む）で考えたときの、b - a < cを満たすもの 
        il = bisect_right(L, l, lo=j)
        #  a < b < c（場合によっては等号を含む）で考えたときの、c < a + bを満たすもの
        ir = bisect_left(L, r, lo=j)
        # b - a < cを満たすものがない場合、飛ばす
        if il == N-1:
            break
        
        ans += ir - il - 1

print(ans)


### FIXED CODE ###

from bisect import bisect_left
from bisect import bisect_right


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):
        l = L[j] - L[i]
        r = L[j] + L[i]

        il = bisect_right(L, l, j)
        ir = bisect_left(L, r, j)

        if il == N-1:
            break

        ans += ir - il - 1

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

from collections import deque

if(__name__ == "__main__"):
    N = int(input())
    a = [int(i) for i in input().split()]
    #print(a,b)
    
    #print(maxlist)
    sunuke = a[:1]
    arai = a[1:]
    darai = deque(arai)
    #print(sunuke)
    #print(darai)
    distmin = abs(sum(sunuke) - sum(darai))
    
    for i in range(1,N-1):
        sunuke.append(a[i])
        darai.popleft()
        #print(sunuke)
        #print(darai)
        dist = abs(sum(sunuke) - sum(darai))
        if(distmin > dist):
            distmin = dist
    
    print(distmin)

### FIXED CODE ###

if(__name__ == "__main__"):
    N = int(input())
    a = [int(i) for i in input().split()]
    #print(a,b)
    
    #print(maxlist)
    sumsunuke = a[0]
    arai = a[1:]
    sumarai = sum(arai)
    #darai = deque(arai)
    #print(sumsunuke)
    #print(sumarai)
    distmin = abs(sumsunuke - sumarai)
    
    for i in range(1,N-1):
        sumsunuke += a[i]
        sumarai -= a[i]
        #print(sunuke)
        #print(darai)
        dist = abs(sumsunuke - sumarai)
        if(distmin > dist):
            distmin = dist
    
    print(distmin)
### BUGGY CODE ###

from itertools import combinations
N = int(input())
L = [int(i) for i in input().split()]
c = 0


def check(a, b, c):
    return (a < b+c) and (b < c+a) and (c < a+b)


for i, j, k in combinations(L, 3):
    c += check(i, j, k)

print(c)


### FIXED CODE ###

from bisect import bisect_left
N = int(input())
L = sorted([int(i) for i in input().split()])

res = 0

for i in range(N):
    for j in range(i+1, N):
        r = bisect_left(L, L[i]+L[j])
        res += max(r-(j+1), 0)

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

from scipy.sparse.csgraph import dijkstra

class UnionFind():
  def __init__(self,n):
    self.n=n
    self.root=[-1]*(n+1)
    self.rank=[0]*(n+1)
  def FindRoot(self,x):
    if self.root[x]<0:
      return x
    else:
      self.root[x]=self.FindRoot(self.root[x])
      return self.root[x]
  def Unite(self,x,y):
    x=self.FindRoot(x)
    y=self.FindRoot(y)
    if x==y:
      return
    else:
      if self.rank[x]>self.rank[y]:
        self.root[x]+=self.root[y]
        self.root[y]=x
      elif self.rank[x]<=self.rank[y]:
        self.root[y]+=self.root[x]
        self.root[x]=y
        if self.rank[x]==self.rank[y]:
          self.rank[y]+=1
  def isSameGroup(self,x,y):
    return self.FindRoot(x)==self.FindRoot(y)
  def Count(self,x):
    return -self.root[self.FindRoot(x)]

n=int(input())
arr=[list(map(int,input().split())) for _ in range(n)]
edge=[]
for i in range(n):
  for j in range(n):
    if i>=j:
      continue
    edge.append((arr[i][j],(i,j)))
edge=sorted(edge,key=lambda x:x[0])
g=[[float('inf')]*n for _ in range(n)]
ans=0
cnt=0
i=0
t=UnionFind(n)
checked=[0]*((n*(n-1))//2)
while cnt<n-1:
  w,(a,b)=edge[i]
  if t.isSameGroup(a,b)==False:
    g[a][b]=w
    g[b][a]=w
    checked[i]=1
    ans+=w
    t.Unite(a,b)
    cnt+=1
  i+=1
for i in range((n*(n-1))//2):
  if checked[i]==1:
    continue
  w,(a,b)=edge[i]
  cost=int(dijkstra(g,indices=a)[b])
  if w==cost:
    continue
  elif w<cost:
    g[a][b]=w
    g[b][a]=w
    ans+=w
  elif w>cost:
    print(-1)
    break
else:
  print(ans)

### FIXED CODE ###

def Warshall_Floyd(edges,N):
  for k in range(N):
    for i in range(N):
      for j in range(N):
        edges[i][j]=min(edges[i][j],edges[i][k]+edges[k][j])
  return edges

n=int(input())
arr=[list(map(int,input().split())) for _ in range(n)]
edge=[]
for i in range(n):
  for j in range(n):
    if i>=j:
      continue
    edge.append((arr[i][j],(i,j)))
edge=sorted(edge,key=lambda x:x[0])
g=[[float('inf')]*n for _ in range(n)]
for i in range(n):
  for j in range(n):
    g[i][j]=arr[i][j]
d=Warshall_Floyd(g,n)
ans=0
for w,(a,b) in edge:
  if d[a][b]<w:
    print(-1)
    break
  else:
    tmp=10**10
    for k in range(n):
      if k==a or k==b:
        continue
      tmp=min(tmp,d[a][k]+d[k][b])
    if w==tmp:
      continue
    else:
      ans+=w
else:
  print(ans)
### BUGGY CODE ###

import sys
s=list(input())
t=list(input())
n=len(s)
for i in range(n):
  if s.count(s[0])>1:
    if t[0]!=t[s[1:].index(s[0])+1]:
      print('No')
      sys.exit()
  if t.count(t[0])>=2:
    if s[0]!=s[t[1:].index(t[0])+1]:
      print('No')
      sys.exit()
  s.pop(0)
  t.pop(0)
print('Yes')
            

### FIXED CODE ###

from collections import Counter
s=Counter(list(input()))
t=Counter(list(input()))
s,t=list(s.values()),list(t.values())
print("Yes" if sorted(s)==sorted(t) else "No")
### BUGGY CODE ###

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

if a == [1]:
  print(0)
  exit()

if 1 not in a:
  print("-1")
  exit()
else:
  nokosu = 1
  a=a[a.index(1)+1:]

for i in range(2,n+1):
  if i not in a:
    print(n - nokosu)
    exit()
  else:
    nokosu += 1
    if len(a)==1:
      print(n - nokosu)
      exit()
    a = a[a.index(i)+1:]

### FIXED CODE ###

n=int(input())
a = list(map(int,input().split()))
b=1
ans=0

if 1 not in a:
    print(-1)
    exit()

for i in a:
  if i==b:
    b+=1
  else:
    ans+=1
print(ans)
### BUGGY CODE ###

H,W=map(int,input().split())

def g(j):
    if j==".":
        return 1 #白
    else:
        return 0 #黒
    
S=[]
for j in range(H):
    S.append(list(map(g,input())))

def m(x,y):
    if (x,y)==(W-1,H-1):
        return 0
    elif x==W-1:
        if S[y][x]==1 and S[y+1][x]==0:
            return m(x,y+1)+1
        else:
            return m(x,y+1)
    
    elif y==H-1:
        if S[y][x]==1 and S[y][x+1]==0:
            return m(x+1,y)+1
        else:
            return m(x+1,y)

    else:
        v=m(x+1,y)
        u=m(x,y+1)
        
        s=S[y][x]
        if s==1 and S[y][x+1]==0:
            v+=1
        if s==1 and S[y+1][x]==0:
            u+=1

        return min(u,v)

print(m(0,0)+1-S[0][0])


### FIXED CODE ###

H,W=map(int,input().split())

def g(j):
    if j==".":
        return 1 #白
    else:
        return 0 #黒
    
S=[]
for j in range(H):
    S.append(list(map(g,input())))


Z=[[0]*W for i in range(H)]

for y in range(H):
    if y==0:
        for x in range(W):
            if x==0:
                Z[0][0]=1-S[0][0]
            else:
                Z[y][x]=Z[y][x-1]+(S[y][x-1]==1 and S[y][x]==0)
    else:
        for x in range(W):
            if x==0:
                Z[y][x]=Z[y-1][x]+(S[y-1][x]==1 and S[y][x]==0)
            else:
                Z[y][x]=min(Z[y][x-1]+(S[y][x-1]==1 and S[y][x]==0),Z[y-1][x]+(S[y-1][x]==1 and S[y][x]==0))

print(Z[H-1][W-1])
### BUGGY CODE ###

S = list(input())
T = list(input())

w = [0 for _ in range(200)]

def ans():
    for s, t in zip(S, T):
        if w[ord(s)] > 0:
            # print("a", w[ord(s)], ord(t))
            if w[ord(s)] != ord(t):
                return("No")
        elif ord(t) in w:
            # print("b")
            return("No")

        w[ord(s)] = ord(t)
        

    for i in range(ord("a"), ord("z")):
        # print(i)
        if w[i] > 0:
            # print(chr(w[w[i]]), chr(i))
            tmp = w[i]
            tmp2 = w[i]
            while(True):
                if w[w[i]] != i:
                    r = w[w[i]]
                    w[w[i]] = w[i]
                    w[i] = r
                else:
                    break
                tmp = w[i]
                if tmp == tmp2:
                    return("No")
    return("Yes")

print(ans())



### FIXED CODE ###

S = list(input())
T = list(input())

w = [0 for _ in range(200)]

def ans():
    for s, t in zip(S, T):
        if w[ord(s)] > 0:
            # print("a", w[ord(s)], ord(t))
            if w[ord(s)] != ord(t):
                return("No")
        elif ord(t) in w:
            # print("b")
            return("No")

        w[ord(s)] = ord(t)
        

    for i in range(ord("a"), ord("z")):
        # print(i)
        if w[i] > 0:
            # print(chr(w[w[i]]), chr(i))
            tmp = w[i]
            tmp2 = w[i]
            while(True):
                if w[w[i]] !=0 and w[w[i]] != i:
                    r = w[w[i]]
                    w[w[i]] = w[i]
                    w[i] = r
                else:
                    break
                tmp = w[i]
                if tmp == tmp2:
                    return("No")
    return("Yes")

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

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

import collections
import copy
import math
def combinations_count(n, r):
    if n < 2:
        return 0
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

c = collections.Counter(A)
c_copy = copy.copy(c)
for ai in A:
    c[ai] -= 1
    ans = 0
    for i in c:
        ans += combinations_count(c[i], 2)
    c = copy.copy(c_copy)
    print(ans)

### FIXED CODE ###

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

d = {}
for a in A:
    if a in d:
        d[a] += 1
    else:
        d[a] = 1

s = 0
for k in d:
    s += d[k] * (d[k] - 1) // 2

for i in range(N):
    t = d[A[i]]
    print(s - t * (t - 1) // 2 + (t - 1) * (t - 2) // 2)
### BUGGY CODE ###

import sys
from collections import defaultdict


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


sys.setrecursionlimit(20000000)


def main():
    H, W, D = map(int, input().split())
    A = [list(map(int, input().split())) for _ in range(H)]
    M = defaultdict(list)
    for h in range(H):
        for w in range(W):
            M[A[h][w]] = [h, w]

    Q = int(input())
    for i in range(Q):
        L, R = map(int, input().split())
        d = R - L
        ans = 0
        lh = M[L][0]
        lw = M[L][1]
        while L != R:
            nh = M[L + D][0]
            nw = M[L + D][1]
            ans += abs(nh - lh) + abs(nw - lw)
            L += D
            lh = nh
            lw = nw
        print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
from collections import defaultdict


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


sys.setrecursionlimit(20000000)


def main():
    H, W, D = map(int, input().split())
    A = [list(map(int, input().split())) for _ in range(H)]
    M = defaultdict(list)
    for h in range(H):
        for w in range(W):
            M[A[h][w]] = [h, w]
    P = defaultdict(list)
    for d in range(1, D + 1):
        a = d
        while a <= H * W - D:
            p = abs(M[a][0] - M[a + D][0]) + abs(M[a][1] - M[a + D][1])
            if P[d]:
                P[d].append(P[d][-1] + p)
            else:
                P[d] = [0, p]
            a += D
    # print(P)
    Q = int(input())
    for i in range(Q):
        L, R = map(int, input().split())
        d = L % D
        l = L // D
        r = R // D
        if d == 0:
            d = D
            if len(P[d]) > 0:
                print(P[d][r - 1] - P[d][l - 1])
            else:
                print(0)
        else:
            if len(P[d])>0:
                print(P[d][r] - P[d][l])
            else:
                print(0)


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

n, k = [int(x) for x in input().split()]
arr = [int(x) for x in input().split()]
p = 1
for i in range(k):
    p *= arr[i]
for i in range(k, n):
    l = p
    l /= arr[i-k]
    l *= arr[i]
    if l > p:
        print("Yes")
    else:
        print("No")
    p = l

### FIXED CODE ###

n, k = [int(x) for x in input().split()]
arr = [int(x) for x in input().split()]
for i in range(k, n):
    if arr[i] > arr[i-k]:
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

n = int(input())
rslt = 1
while n > 1:
    rslt *= n
    n -= 1
print(rslt%(10**9+7))

### FIXED CODE ###

import math
n = int(input())
print( math.factorial(n)%(10**9+7) )
### BUGGY CODE ###

N = int(input())

def prime_factorization(n):
    factor = []
    f = 2
    while f ** 2 <= n:
        if n % f == 0:
            factor.append(f)
            n //= f
        else:
            f += 1
    if n > 1:
        factor.append(n)
    return factor

p = prime_factorization(N)
from itertools import combinations as cb
from functools import reduce
from operator import mul

s = float('inf')
for i in range(1,len(p)+1):
    for j in cb(p, i):
        A = reduce(mul, j)
        B = N//A
        s = min(s, A+B)

print(s-2)

### FIXED CODE ###

N = int(input())
S = N+1
from math import sqrt
for a in range(int(sqrt(N))+2, 0, -1):
    b, y = divmod(N, a)
    if y != 0:
        continue
    S = min(S, a+b)
print(S-2)
### BUGGY CODE ###

n = int(input())
ans = max(2, n)
while True:
    if ans%2 == ans%n == 0:
        break
    ans += 1
print(ans)  

### FIXED CODE ###

n = int(input())
print(n if n%2==0 else 2*n)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

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

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

### FIXED CODE ###

N, K, Q = map(int, input().split())
 
P = [0] * N
for i in range(Q):
    tmp = int(input()) - 1
    P[tmp] += 1
 
sumP = sum(P)
for n in range(N):
    ans = 'No'
    total = sumP - P[n]
    if  K - total > 0:
        ans = 'Yes'
    print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline


def main():
    N, W = [int(i) for i in input().strip().split()]
    items = [[int(i) for i in input().strip().split()] for _ in range(N)]

    dp = [[0 for _ in range(N)] for _ in range(W + 1)]

    for i in range(N):
        for capacity in range(W + 1):
            if i == 0:
                if capacity >= items[i][0]:
                    dp[capacity][i] = items[i][1]
                else:
                    dp[capacity][i] = 0
            else:
                if capacity >= items[i][0]:
                    dp[capacity][i] = max(
                        dp[capacity][i - 1], dp[capacity - items[i][0]][i - 1] + items[i][1])
                else:
                    dp[capacity][i] = dp[capacity][i-1]

    return dp[-1][-1]


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


### FIXED CODE ###

class Solver():
    def __init__(self, N, W, items):
        self.N = N
        self.W = W
        self.items = items

    def solve(self):
        dp = [[0 for _ in range(self.W+1)] for _ in range(self.N+1)]
        for i in range(self.N):
            for w in range(self.W+1):
                if w - self.items[i][0] >= 0:
                    dp[i+1][w] = max(dp[i+1][w], dp[i][w - self.items[i][0]] + self.items[i][1])

                dp[i + 1][w] = max(dp[i + 1][w], dp[i][w])
        return dp[self.N][self.W]


def main():
    N, W = [int(i) for i in input().split()]
    items = [[int(i) for i in input().split()] for _ in range(N)]
    solver = Solver(N, W, items)
    print(solver.solve())


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

N, S = map(int, input().split())
A = [int(a) for a in input().split()]
X = [0] * 3001
ans = 0
P = 998244353
for i, a in enumerate(A):
    X[0] += 1
    for j in range(S, a-1, -1):
        X[j] = (X[j] + X[j-a]) % P
    ans += X[S]
print(ans % P)

### FIXED CODE ###

N, S = map(int, input().split())
A = [int(a) for a in input().split()]
X = [0] * 3001
pre = 0
ans = 0
P = 998244353
for i, a in enumerate(A):
    for j in range(S, a, -1):
        X[j] = (X[j] + X[j-a]) % P
    X[a] = (X[a] + i + 1) % P
    ans = (ans + (X[S] - pre) * (N - i)) % P
    pre = X[S]
print(ans)
### BUGGY CODE ###

a, b, x = map(int, input().split())
cnt = 0
for i in range(a, b+1):
    if i % x == 0:
        cnt += 1
print(cnt)

### FIXED CODE ###

a, b, x = map(int, input().split())
A = (a-1) // x
B = b // x
print(B - A)
### BUGGY CODE ###

n,k=map(int,input().split())
x,y=[[0,0] for i in range(n)],[[0,0] for i in range(n)]
xy=[list(map(int,input().split())) for i in range(n)]
for i in range(n):
    x_sub,y_sub=xy[i]
    x[i][0]=x_sub
    x[i][1]=i
    y[i][0]=y_sub
    y[i][1]=i
x.sort()
y.sort()
ans=(10**18)*5
for i1 in range(n):
    for l1 in range(n-i1,1,-1):
        for i2 in range(n):
            for l2 in range(n-i2,1,-1):
                x_sub1=x[i1][0]
                x_sub2=x[i1+l1-1][0]
                y_sub1=y[i2][0]
                y_sub2=y[i2+l2-1][0]
                z=[0]*n
                for i in range(n):
                    if x_sub1<=xy[i][0]<=x_sub2:
                        if y_sub1<=xy[i][1]<=y_sub2:
                            z[i]=1
                if sum(z)>=k:
                    ans=min((x_sub2-x_sub1)*(y_sub2-y_sub1),ans)
                else:
                    break
print(ans)


### FIXED CODE ###

n,k=map(int,input().split())
x,y=[[0,0] for i in range(n)],[[0,0] for i in range(n)]
xy=[list(map(int,input().split())) for i in range(n)]
for i in range(n):
    x_sub,y_sub=xy[i]
    x[i][0]=x_sub
    x[i][1]=i
    y[i][0]=y_sub
    y[i][1]=i
x.sort()
y.sort()
ans=(10**18)*5
for i1 in range(n):
    for l1 in range(n-i1,1,-1):
        for i2 in range(n):
            for l2 in range(n-i2,1,-1):
                x_sub1=x[i1][0]
                x_sub2=x[i1+l1-1][0]
                y_sub1=y[i2][0]
                y_sub2=y[i2+l2-1][0]
                z=[0]*n
                for i in range(n):
                    if x_sub1<=xy[i][0]<=x_sub2 and y_sub1<=xy[i][1]<=y_sub2:
                        z[i]=1
                if sum(z)>=k:
                    ans=min((x_sub2-x_sub1)*(y_sub2-y_sub1),ans)
                else:
                    break
print(ans)
### 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()))
D = []
E2 = []
F = []

# A + Bの全列挙 からのソート 

for i in A : 
    for j in B : 
        D.append(i+j)
        
E = sorted(D, reverse = True)

if len(E) > K : 
    for i in range(K) : 
        E2.append(E[i])
else : 
    E2 = E
        
####

for i in E2 : 
    for j in C : 
        F.append(i+j)
        
G = sorted(F, reverse = True)

for i in range(K) : 
    print(G[i])

### FIXED CODE ###

X,Y,Z,K = map(int, input().split())

A = sorted(list(map(int, input().split()))[:K])
B = sorted(list(map(int, input().split()))[:K])
C = sorted(list(map(int, input().split()))[:K])

ab = sorted(list(a+b for a in A for b in B), reverse = True)[:K]
abc = sorted(list(ab+c for ab in ab for c in C), reverse = True)[:K]

for i in abc : 
    print(i)
### BUGGY CODE ###

import bisect

n, m = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
for j in range(m):
    b, c = map(int, input().split())
    idx = bisect.bisect_left(a, c)
    if idx >= b:
        a = a[b:idx] + [c] * b + a[idx:]
    else:
        a = [c] * idx + a[idx:]
print(sum(a))


### FIXED CODE ###

import bisect

n, m = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
c = [None] * m
for j in range(m):
    c[j] = list(map(int, input().split()))
c.sort(key=lambda x: x[1], reverse=True)
k = 0
ans = 0
for i in range(n):
    if k >= m:
        ans += sum(a[i:])
        break
    if a[i] >= c[k][1]:
        ans += a[i]
    else:
        ans += c[k][1]
        c[k][0] -= 1
        if c[k][0] == 0:
            k += 1
print(ans)