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

# -*- coding: utf-8 -*-
"""
D - Lamp
https://atcoder.jp/contests/abc129/tasks/abc129_d

"""
import sys


def solve(H, W, grid):
    res_x = [[0]*W for _ in range(H)]
    x, y = 0, 0
    while y < H:
        while x < W:
            if grid[y][x] == '#':
                x += 1
                continue
            rx = x
            while rx < W and grid[y][rx] != '#':
                rx += 1
            for xx in range(x, rx):
                res_x[y][xx] = rx-x
            x = rx
        x = 0
        y += 1

    res_y = [[0]*W for _ in range(H)]
    x, y = 0, 0
    while x < W:
        while y < H:
            if grid[y][x] == '#':
                y += 1
                continue
            ry = y
            while ry < H and grid[ry][x] != '#':
                ry += 1
            for yy in range(y, ry):

                res_y[yy][x] = ry-y
            y = ry
        y = 0
        x += 1

    ans = 0
    for y in range(H):
        for x in range(W):
            t = res_x[y][x] + res_y[y][x] - 1
            if t > ans:
                ans = t
    return ans


def main(args):
    H, W = map(int, input().split())
    grid = [input() for _ in range(H)]
    ans = solve(H, W, grid)
    print(ans)


if __name__ == '__main__':
    main(sys.argv[1:])


### FIXED CODE ###

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



"""
import sys


def solve(H, W, grid):
    res_x = [[0]*W for _ in range(H)]
    x, y = 0, 0
    while y < H:
        while x < W:
            if grid[y][x] == '#':
                x += 1
                continue
            rx = x
            while rx < W and grid[y][rx] != '#':
                rx += 1
            for xx in range(x, rx):
                res_x[y][xx] = rx-x
            x = rx
        x = 0
        y += 1

    res_y = [[0]*W for _ in range(H)]
    x, y = 0, 0
    while y < H:
        while x < W:
            if grid[y][x] == '#' or res_y[y][x] != 0:
                x += 1
                continue
            dy = y
            while dy < H and grid[dy][x] != '#':
                dy += 1
            for yy in range(y, dy):
                if res_y[yy][x] == 0:
                    res_y[yy][x] = dy-y
            x += 1
        x = 0
        y += 1

    ans = 0
    for y in range(H):
        for x in range(W):
            t = res_x[y][x] + res_y[y][x] - 1
            if t > ans:
                ans = t
    return ans


def main(args):
    H, W = map(int, input().split())
    grid = [input() for _ in range(H)]
    ans = solve(H, W, grid)
    print(ans)


if __name__ == '__main__':
    main(sys.argv[1:])
### BUGGY CODE ###

# -*- coding: utf-8 -*-
"""
Created on Wed Jun 24 20:53:22 2020

@author: NEC-PCuser
"""

def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

if __name__ == '__main__':
    K = int(input())
    n = len(input())
    mod = 10**9+7 #出力の制限
    #25 25 a 25 25 25 b 25 25  c  26 26
    
    ans = 0
    for i in range(0, K + 1):
        ans1 = (((25 ** i) % (mod)) * cmb(n + i - 1, n - 1)) % mod
        ans2 = (26 ** (K - i)) % mod
        ans += (ans1 * ans2) % mod
    
    print(ans)
        

### FIXED CODE ###

n = int(input())
s = input()
 
S = len(s)
mod = 10 ** 9 + 7
 
tmp_ans = pow(26, n, mod)
div = pow(26, -1, mod)
 
ans = tmp_ans
 
for i in range(1, n+1):
    tmp_ans = (tmp_ans * 25 * div) % mod
    tmp_ans = ((tmp_ans * (S-1+i)) * pow(i, -1, mod)) % mod
    ans = (ans + tmp_ans) % mod
 
ans %= mod
 
print(ans)
### BUGGY CODE ###

import sys
import bisect
 
N, Q = map(int, input().split(' '))
G = [list(map(int, sys.stdin.readline().split(' '))) for _ in range(N)]
T = [int(sys.stdin.readline()) for _ in range(Q)]
 
G.sort(key = lambda x : -x[2])

class SegTree :
    def __init__(self, n) :
        self.n = n
        self.A = [None] * (2 << (n + 1).bit_length())
 
    def update(self, i, l, r, ll, rr, val) :
        if r <= ll or rr <= l :
            return
        if ll <= l and r <= rr :
            self.A[i] = val
            return
 
        if self.A[i] != None :
            self.A[i * 2] = self.A[i * 2 + 1] = self.A[i]
            self.A[i] = None
 
        m = (l + r) // 2
        self.update(i * 2, l, m, ll, rr, val)
        self.update(i * 2 + 1, m, r, ll, rr, val)
 
    def get(self, i, l, r, p) :
        if self.A[i] != None or l + 1 == r :
            return self.A[i]
        m = (l+r) // 2
        if p < m :
            return self.get(i * 2, l, m, p)
        else :
            return self.get(i * 2 + 1, m, r, p)
 
ST = SegTree(Q)
for g in G :
    s = max(0, g[0] - g[2])
    e = g[1] - g[2]
    if e <= 0 :
        continue
 
    ll = bisect.bisect_left(T, s)
    rr = bisect.bisect_left(T, e)
 
    if ll == rr :
        continue
 
    ST.update(1, 0, Q, ll, rr, g[2])
 
for i in range(Q) :
    ans = ST.get(1, 0, Q, i)
    if ans == None :
        print(-1)
    else :
        print(ans)


### FIXED CODE ###

import sys
import bisect
 
N, Q = map(int, input().split(' '))
G = [list(map(int, sys.stdin.readline().split(' '))) for _ in range(N)]
T = [int(sys.stdin.readline()) for _ in range(Q)]

class SegTree :
    def __init__(self, n) :
        self.n = n
        self.A = [10**15] * (2 << (n + 1).bit_length())
 
    def update(self, l, r, val) :
      l += len(self.A) // 2
      r += len(self.A) // 2
      while l < r:
          if l & 1 :
              self.A[l] = min(self.A[l], val)
              l += 1
          if r & 1:
              self.A[r-1] = min(self.A[r-1], val)
              r -= 1
          l //= 2
          r //= 2

    def get(self, i) :
      i += len(self.A) // 2
      ret = self.A[i]
      while i > 0 :
          i //= 2
          ret = min(ret, self.A[i])
      return ret if ret < 10**15 else -1

ST = SegTree(Q)
for g in G :
    s = g[0] - g[2]
    e = g[1] - g[2]
 
    ll = bisect.bisect_left(T, s)
    rr = bisect.bisect_left(T, e)
 
    if ll == rr :
        continue
 
    ST.update(ll, rr, g[2])
 
for i in range(Q) :
    ans = ST.get(i)
    print(ans)
### BUGGY CODE ###

n = int(input())
lst = [int(i) for i in input().split()]
ans = 1
for i in lst:
    ans *=  i#input().split()
if(ans > 1.0e+18):
    print(-1)
    exit()

print(ans)


### FIXED CODE ###

n = int(input())
lst = [int(i) for i in input().split()]
if(lst.count(0) > 0):
    print(0)
    exit()

ans = 1
for i in lst:
    ans *=  i#input().split()
    if(ans > 1.0e+18):
        print(-1)
        exit()

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

n = int(raw_input())
data = raw_input().split()
s = ''
for i in range (1, n + 1):
    j = 0
    while (int(data[j]) != i):
        j+=1
    s += str(j + 1) + ' '
print (s)


### FIXED CODE ###

n = int(raw_input())
data = raw_input().split()
tab = range(n)

for i in range (0, n):
    tab[int(data[i]) - 1] = i + 1
s = ''
for i in tab:
    s += str(i) + ' '

print (s)
### BUGGY CODE ###

#!/usr/bin/env python
from __future__ import division, print_function

import os
import sys
from io import BytesIO, IOBase

if sys.version_info[0] < 3:
    from __builtin__ import xrange as range
    from future_builtins import ascii, filter, hex, map, oct, zip


def main():
    pass


# region fastio

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


def print(*args, **kwargs):
    """Prints the values to a stream, or to sys.stdout by default."""
    sep, file = kwargs.pop("sep", " "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", "\n"))
    if kwargs.pop("flush", False):
        file.flush()


if sys.version_info[0] < 3:
    sys.stdin, sys.stdout = FastIO(sys.stdin), FastIO(sys.stdout)
else:
    sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)

input = lambda: sys.stdin.readline().rstrip("\r\n")

# endregion

if __name__ == "__main__":
    main()


a, b = map(int, input().split())
c = 1
for i in range(a, b+1):
    c *= i
if c>0:
    print("Positive")
elif c<0:
    print("Negative")
else:
    print("Zero")

### FIXED CODE ###

a, b = map(int, input().split())
if a>0 and b>0:
    print("Positive")
elif a==0 or b==0:
    print("Zero")
elif (a>0 and b<0) or (a<0 and b>0):
    print("Zero")
elif ((a+b)+1)%2==0:
    print("Positive")
else:
    print("Negative")
### BUGGY CODE ###

import sys
sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))
from collections import defaultdict
def resolve():
    N, M, S = lr()
    uvab = [[] for i in range(N)]
    amax = 0
    for i in range(M):
        u, v, a, b = lr()
        uvab[u-1].append([v-1, a, b])
        uvab[v-1].append([u-1, a, b])
        amax = max(amax, a)
    cd = []
    for i in range(N):
        cd.append(lr())
    dp = defaultdict(lambda: float('inf'))
    A = amax*(N-1)
    dp[0, min(S, A)] = 0
    s = [[0, min(S, A), 0]]
    while len(s) > 0:
        s = sorted(s, key=lambda x: x[2])[::-1]
        u, i, x  = s.pop()
        if dp[u, i] != x:
            continue
        c, d = cd[u]
        ni = min(i+c, A)
        if dp[u, ni] > dp[u, i]+d:
            dp[u, ni] = dp[u, i]+d
            s.append([u, ni, dp[u, ni]])
        for vab in uvab[u]:
            v, a, b = vab
            if i >= a and i < A and dp[v, i-a] > dp[u, i] + b:
                dp[v, i-a] = dp[u, i] + b
                s.append([v, i-a, dp[v, i-a]])
            elif i == A and dp[v, i] > dp[u, i] + b:
                dp[v, i] = dp[u, i] + b
                s.append([v, i, dp[v, i]])
    for i in range(1, N):
        ans = float('inf')
        for j in range(A+1):
            ans = min(dp[i, j], ans)
        print(ans)
resolve()

### FIXED CODE ###

import sys
sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))
from collections import defaultdict
from heapq import heappop, heappush
def resolve():
    N, M, S = lr()
    uvab = [[] for i in range(N)]
    amax = 0
    for i in range(M):
        u, v, a, b = lr()
        uvab[u-1].append([v-1, a, b])
        uvab[v-1].append([u-1, a, b])
        amax = max(amax, a)
    cd = []
    for i in range(N):
        cd.append(lr())
    dp = defaultdict(lambda: float('inf'))
    A = amax*(N-1)
    dp[0, min(S, A)] = 0
    s = [[0, 0, min(S, A)]]
    while len(s) > 0:
        x, u, i  = heappop(s)
        if dp[u, i] != x:
            continue
        c, d = cd[u]
        ni = min(i+c, A)
        if dp[u, ni] > dp[u, i]+d:
            dp[u, ni] = dp[u, i]+d
            heappush(s, [dp[u, ni], u, ni])
        for vab in uvab[u]:
            v, a, b = vab
            if i >= a and i < A and dp[v, i-a] > dp[u, i] + b:
                dp[v, i-a] = dp[u, i] + b
                heappush(s, [dp[v, i-a], v, i-a])
            elif i == A and dp[v, i] > dp[u, i] + b:
                dp[v, i] = dp[u, i] + b
                heappush(s, [dp[v, i], v, i])
    for i in range(1, N):
        ans = float('inf')
        for j in range(A+1):
            ans = min(dp[i, j], ans)
        print(ans)
resolve()
### BUGGY CODE ###

#!/usr/bin/env python

from collections import deque
import itertools as it
import sys
import math

sys.setrecursionlimit(1000000)

INF = 10 ** 18
MOD = 10 ** 9 + 7

N, P = map(int, raw_input().split())

if N == 1:
    print P
    exit()

num = 1
ans = 0
while True:
    if P % (num ** N) == 0:
        ans = num
    if P < (num ** N):
        break
    num += 1

print ans

### FIXED CODE ###

#!/usr/bin/env python

from collections import deque
import itertools as it
import sys
import math

sys.setrecursionlimit(1000000)

INF = 10 ** 18
MOD = 10 ** 9 + 7

N, P = map(int, raw_input().split())

if N == 1:
    print P
    exit()

if N > 60:
    print 1
    exit()

num = 1
ans = 0
while True:
    if P % (num ** N) == 0:
        ans = num
    if P < (num ** N):
        break
    num += 1

print ans
### BUGGY CODE ###

N = int(input())

A = sorted(list(map(int,input().split())))
B = [sum(A[:i+1]) for i in range(N)][::-1]
A.reverse()

min_abs = A[0]
ans = 1
for i in range(1,N):
    if A[i]*2 >= min_abs:
        ans += 1
    elif B[i]*2 >= min_abs:
        ans += 1
    else:
        break
    min_abs = A[i]
    
print(ans)

### FIXED CODE ###

N = int(input())

A = sorted(list(map(int,input().split())),reverse=True)

min_abs = A[0]
ans = 1
for i in range(1,N):
    if A[i]*2 >= min_abs:
        ans += 1
    elif sum(A[i:])*2 >= min_abs:
        ans += 1
    else:
        break
    min_abs = A[i]
    
print(ans)
### BUGGY CODE ###

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

s = 0
for i in range(n-1):
    v = 0
    for j in range(i+1, n):
        v += a[j]
    s += (a[i] * v % (10**9 + 7))

s %= (10**9 + 7)

print(s)


### FIXED CODE ###

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

s = 0
ss = 0
for i in range(n):
    j = n - i - 1
    s += (a[j] * ss % (10**9 + 7))
    s %= (10**9 + 7)
    ss += a[j]

print(s)
### BUGGY CODE ###

n = int(input(''))
adl = input('')

a = list(map(int,adl.split(' ')))

number = 0

mod = 1000000007

amari = 0

for i in range(n):
    aa = 0
    for e in range(n-i-1):
        j = i+e+1
        if i != j:
            aa = aa + a[j]
    number = number + ((a[i] % mod) * (aa % mod))
    number = number % mod
amari = number % mod
print(amari)


### FIXED CODE ###

n = int(input(''))
adl = input('')

a = list(map(int,adl.split(' ')))

number = 0

mod = 1000000007

amari = 0

all_a = 0

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

for i in range(n):
    all_a = all_a - a[i]
    number = number + (a[i] * all_a)
    number = number % mod
amari = number % mod
print(amari)
### BUGGY CODE ###

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


# 最小値更新して越えてたらアウト
resultCount = 0
minNum = P[0]
for i in range(N):
    isMitasu = True
    if i != 0:
        if P[i] > minNum:
            isMitasu = False
        else:
            for j in range(i):
                if P[i] > P[j]:
                    isMitasu = False
                    # 最小値更新
                    if P[i] < minNum:
                        minNum = P[i]
                    break
    if isMitasu:
        resultCount += 1
print(resultCount)

### FIXED CODE ###

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


# 最小値更新して越えてたらアウト
resultCount = 0
minNum = P[0]
for i in range(N):
    isMitasu = True
    if i != 0:
        if P[i] > minNum:
            isMitasu = False
        else:
            # 最小値更新
            minNum = P[i]
    if isMitasu:
        resultCount += 1
print(resultCount)
### BUGGY CODE ###

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

cards=set([i+1 for i in range(n)])


for j in range(m):

    l,r = map(int,input().split())

    gates = set([j for j in range(l,r+1)])

    cards = cards&gates


print(len(cards))



### FIXED CODE ###

n,m=map(int,input().split())
l = 1
r = n
for j in range(m):

    l_i,r_i = map(int,input().split())

    l = max(l,l_i)
    r = min (r,r_i)

if r>=l:
    print(r-l+1)
else:
    print(0)
### BUGGY CODE ###


def main():
    data = input()

    while 'ST' in data:
        data = data.replace('ST', '')
    print(len(data))




if __name__ == '__main__':
    main()

### FIXED CODE ###


def main():
    data  = list(input())

    ans = len(data)
    count_s = 0
    for i in range(len(data)):
        if data[i] == 'S':
            count_s += 1
        else:
            if count_s > 0:
                count_s -= 1
                ans -= 2

    print(ans)




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

import sys
def main():
    INF=sys.maxsize
    N,K=tuple(map(int,sys.stdin.readline().split()))
    h=tuple(map(int,sys.stdin.readline().split()))
    dp=[INF for _ in range(N)]
    dp[0]=0
    for i in range(N-1):
        for j in range(1,K+1):
            if i+j<N:dp[i+j]=min([dp[i+j],dp[i]+abs(h[i+j]-h[i])])
    print(dp[N-1])
if __name__=='__main__':main()

### FIXED CODE ###

import sys
def main():
    INF=sys.maxsize
    N,K=tuple(map(int,sys.stdin.readline().split()))
    h=tuple(map(int,sys.stdin.readline().split()))
    dp=[INF for _ in range(N)]
    dp[0]=0
    for i in range(N-1):
        for j in range(1,K+1):
            if i+j<N:dp[i+j]=min([dp[i+j],dp[i]+abs(h[i+j]-h[i])])
    print(dp[N-1])
if __name__=='__main__':main()
### BUGGY CODE ###

import bisect
MOD = 10**9+7
N,M = map(int,input().split())
A = sorted(list(map(int,input().split())))
B = sorted(list(map(int,input().split())))
a = set(A)
b = set(B)
check = True
if len(a) != N or len(b) != M:
    check = False
ans = 1
for num in range(N*M,0,-1):
    tmp = 0
    if num in A and num in B: continue
    elif num in A:
        tmp = M - bisect.bisect_left(B,num)
    elif num in B:
        tmp = N - bisect.bisect_left(A,num)
    else:
        x = bisect.bisect_left(A,num)
        y = bisect.bisect_left(B,num)
        tmp = (N-x)*(M-y) - (M*N-num) 
    
    if tmp < 0 or check == False:
        check = False
        break
    ans *= tmp
    ans %= MOD

print(ans if check else 0)

### FIXED CODE ###

import bisect

N,M = map(int,input().split())
A = sorted(list(map(int,input().split())))
B = sorted(list(map(int,input().split())))
MOD = 10**9+7
sa = set(A)
sb = set(B)
ok = True
if len(sa) != N or len(sb) != M:
    ok = False
    exit
ans = 1
vacant = 1
for i in range(N*M,0,-1):
    if i in sa and i in sb: continue
    if i in sa:
        vacant = M - bisect.bisect_left(B,i)
    elif i in sb:
        vacant = N - bisect.bisect_left(A,i)
    else:
        x = M - bisect.bisect_left(B,i)
        y = N - bisect.bisect_left(A,i)
        vacant = x*y - (N*M-i)
    if vacant < 0:
        ok = False
        exit
    ans *= vacant
    ans %= MOD
print(ans if ok else 0)
### BUGGY CODE ###

f = lambda: list(map(int,input().split()))
f_ = lambda: [int(x)-1 for x in input().split()]

n,k = f()
l = []
for _ in range(n):
    a,b = f()
    l += [a]*b
print(sorted(l)[k-1])

### FIXED CODE ###

f = lambda: list(map(int,input().split()))
f_ = lambda: [int(x)-1 for x in input().split()]

n,k = f()
d = []
for _ in range(n):
    a,b = f()
    d.append((a,b))
d.sort(key=lambda x: x[0])
count = 0
for x,y in d:
    count += y
    if count >= k:
        break
print(x)
### BUGGY CODE ###

n,m=map(int,input().split())
a=[int(input()) for _ in range(m)]
dp=[-1 for _ in range(n+1)]
dp[0]=dp[1]=1
def step(s):
    if s in a:
        dp[s]=0
        return
    elif dp[s]>=0:
        return 
    else:
        dp[s]=dp[s-1]+dp[s-2] 
        return
for i in range(n+1):
    step(i)
print(dp[-1]%1000000007)

### FIXED CODE ###

n,m=map(int,input().split())
a=[]
mod=1000000007
for _ in range(m):
    a.append(int(input()))
a=set(a)
ans=[1]+[0]*(n)
for i in range(1,n+1):
    if i in a:
        ans[i]=0
    else:
        ans[i]=(ans[i-1]+ans[i-2])%mod
print(ans[n])
### BUGGY CODE ###

n,m=map(int,input().split())
fromto=[list(map(int,input().split()))for _ in range(n+m-1)]
m += n-1
fr = [[]for _ in range(n+1)]
to = [0]*(n+1)
ans = [0]*(n+1)
for f,t in fromto:
    fr[f].append(t)
    to[t]+=1
for i in range(1,n+1):
    if to[i] is 0:
        root = i
q=[root]
while q:
    now = q.pop(0)
    for nex in fr[now]:
        to[nex] -= 1
        if to[nex] is 0:
            ans[nex] = now
            q.append(nex)

for i in range(1,n+1):
    print(ans[i])

### FIXED CODE ###

import queue

n,m=map(int,input().split())
fromto=[list(map(int,input().split()))for _ in range(n+m-1)]
m += n-1
fr = [[]for _ in range(n+1)]
to = [0]*(n+1)
ans = [0]*(n+1)
for f,t in fromto:
    fr[f].append(t)
    to[t]+=1
for i in range(1,n+1):
    if to[i] is 0:
        root = i
q=queue.Queue()
q.put(root)
while not q.empty():
    now = q.get()
    for nex in fr[now]:
        to[nex] -= 1
        if to[nex] is 0:
            ans[nex] = now
            q.put(nex)

for i in range(1,n+1):
    print(ans[i])
### BUGGY CODE ###

import bisect
import numpy as np
n,m=map(int,input().split())
A=list(map(int,input().split()))
A=sorted(A)
A=np.array(A, dtype=np.int64)
BC=[]
for _ in range(m):
    b,c=map(int,input().split())
    BC.append((b,c))
BC=sorted(BC, reverse=True, key=lambda x: x[1])

for i in range(m):
    b,c=BC[i]
    ind=bisect.bisect_left(A, c)
    if ind>0:
        x,y=min(ind, b), max(ind, b)
        A=np.concatenate([A[x:y],np.array([c]*x,dtype=np.int64),A[y:]])
    else:
        break
print(sum(A))

### FIXED CODE ###

import numpy as np
n,m=map(int,input().split())
A=list(map(int,input().split()))
A=sorted(A)
A=np.array(A, dtype=np.int64)
BC=[]
for _ in range(m):
    b,c=map(int,input().split())
    BC.append((b,c))
BC=sorted(BC,reverse=True, key=lambda x:x[1])
D=[]
cnt=0
for i in range(m):
    b,c=BC[i]
    cnt+=b
    D+=[c]*b
    if cnt>=n:
        break
if cnt>=n:
    D=D[:n]
else:
    D+=[0]*(n-cnt)
D=np.array(D, dtype=np.int64)

A=np.maximum(A,D)
print(np.sum(A))
### BUGGY CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

from heapq import heappop, heappush

N = int(input())
A = [int(x) for x in input().split()]
B = [int(x) for x in input().split()]

q = []
push = lambda x,i: heappush(q, (-x,i))
def pop():
    x,i = heappop(q)
    return -x,i

for i,x in enumerate(B):
    push(x,i)

answer = 0
while q:
    x,i = pop()
    if x < A[i]:
        answer = -1
        break
    dx = x-A[i]
    nbd = B[(i-1)%N] + B[(i+1)%N]
    t = dx // nbd
    if t == 0:
        if x == A[i]:
            continue
        answer = -1
        break
    B[i] -= nbd * t
    answer += t
    push(B[i],i)

print(answer)

### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

from heapq import heappop, heappush

N = int(input())
A = [int(x) for x in input().split()]
B = [int(x) for x in input().split()]

q = []
push = lambda x,i: heappush(q, (-x,i))
for i,x in enumerate(B):
    push(x,i)

answer = 0
while q:
    x,i = heappop(q)
    x = -x
    if x < A[i]:
        answer = -1
        break
    dx = x-A[i]
    nbd = B[(i-1)%N] + B[(i+1)%N]
    t = dx // nbd
    if t == 0:
        if x == A[i]:
            continue
        answer = -1
        break
    B[i] -= nbd * t
    answer += t
    push(B[i],i)

print(answer)