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

from math import sqrt

N0,D1,D2 = map(int,input().split())
N = 2*N0
banned = set()
for d in [D1,D2]:
  for x in range(0, int(sqrt(d/2)+1)):
    y = sqrt(d-x*x)
    if y == int(y):
      y = int(y)
      banned.add((x,y))
      banned.add((y,x))

grid = [[True for _ in range(N*2)] for _ in range(N*2)]

points = []

for y in range(N0):
  g = grid[y]
  for x in range(N0):

    if g[x]:
      points.append((x,y))

      for dx,dy in banned:
        if x+dx < N0 and y+dy < N0:
          grid[y+dy][x+dx] = False

from time import sleep

if len(points) < N0**2:
  sleep(3)

for x,y in points[:N0**2]:
  print(x,y)

### FIXED CODE ###

from math import sqrt
from itertools import product

import numpy as np

def helper(N,D):
  if D%2 == 1:
    grid = np.zeros((N,N),dtype=bool)
    grid[::2,:] = True
    grid[:,1::2] = ~grid[:,1::2]
  elif D%4 == 2:
    grid = np.zeros((N,N),dtype=bool)
    grid[::2,:] = True
  else:
    M = (N-1)//2+1
    D //= 4
    g = helper(M, D)
    grid = np.zeros((2*M,2*M),dtype=bool)
    grid[::2,::2] = g
    grid[1::2,::2] = g
    grid[::2,1::2] = g
    grid[1::2,1::2] = g
    grid = grid[:N,:N]
  return grid


N,D1,D2 = map(int,input().split())
M = N*2
g1 = helper(N*2,D1)
g2 = helper(N*2,D2)
ans = g1&g2


for x,y in np.transpose(np.nonzero(ans))[:N*N]:
  print(x,y)
### BUGGY CODE ###

N,Q = map(int, input().split())

A=[[0]*2 for i in range(N)]
Ans=[0]*(N+1)
P=[[0]*2 for i in range(Q)]

for i in range(N-1):
    A[i][0],A[i][1] = map(int, input().split())
for i in range(Q):
    P[i][0],P[i][1] = map(int, input().split())
    Ans[P[i][0]]+=P[i][1]

A.sort()

for i in range(N):
    Ans[A[i][1]]+=Ans[A[i][0]]

for i in range(1,N+1):
    print(Ans[i],end=" ")


### FIXED CODE ###

import sys

n, q = [int(i) for i in sys.stdin.readline().split()]
graph = {i: [] for i in range(n)}
ct = [0 for i in range(n)]
for i in range(n - 1):
    a, b = [int(i) for i in sys.stdin.readline().split()]
    a -= 1
    b -= 1
    graph[a].append(b)
    graph[b].append(a)

for i in range(q):
    p, x = [int(i) for i in sys.stdin.readline().split()]
    p -= 1
    ct[p] += x
already = {0}
stack = [(0, ct[0], -1)]
res = [0 for i in range(n)]
while len(stack) > 0:
    cur, cost, _from = stack.pop(-1)
    res[cur] = cost
    for _next in graph[cur]:
        if _next == _from:
            continue
        next_cost = ct[_next]
        stack.append((_next, cost + next_cost, cur))
        already.add(cur)
print(" ".join([str(r) for r in res]))
### BUGGY CODE ###

n,W=map(int,input().split())
values=[]
weights=[]

for _ in range(n):

    a,b=map(int,input().split())
    weights.append(a)
    values.append(b)

ans=[[0]*(W+1) for _ in range(n)]

for i in range(0,n):
    for j in range(1,W+1):
        p=0
        if j>=weights[i] :
            p=ans[i-1][j-weights[i]]+values[i]
        ans[i][j]=max(ans[i-1][j],p)

print(ans[-1][W])



### FIXED CODE ###

n,W=map(int,input().split())
values=[]
weights=[]

for _ in range(n):

    a,b=map(int,input().split())
    weights.append(a)
    values.append(b)

ans=[[0]*(W+1) for _ in range(n)]

for i in range(0,n):
    for j in range(1,W+1):
        p=0
        if j>=weights[i] :
            p=ans[i-1][j-weights[i]]+values[i]
        ans[i][j]=max(ans[i-1][j],p)

print(ans[-1][W])
### BUGGY CODE ###

N, X = map(int, input().split())
items = []
for i in range(N):
    b, l, u = map(int, input().split())
    items.append((b, l, u, u * (X - b), - b * l))

items = sorted(items, key=lambda x: -(x[3] - x[4]))


def f(num):
    cnt = num // X
    mod = num % X
    point = 0
    for i in range(cnt):
        point += items[i][3]
    for i in range(cnt, N):
        point += items[i][4]

    if mod == 0:
        if point >= 0:
            return True
        else:
            return False
    else:
        tmp = -float("inf")
        for i, tmp2 in enumerate(items):
            b, l, u, d1, d2 = tmp2
            if mod >= b:
                mul = u * (mod - b)
            else:
                mul = l * (mod - b)

            if i < cnt:
                tmp = max(tmp, point - d1 + mul + items[cnt][3] - items[cnt][4])
            else:
                tmp = max(tmp, point - d2 + mul)
        if tmp >= 0:
            return True
        else:
            return False

ok = N * X + 1
ng = - 1
while (ok - ng) > 1:
    mid = (ok + ng) // 2
    if f(mid):
        ok = mid
    else:
        ng = mid
print(ok)


### FIXED CODE ###

N, X = map(int, input().split())
items = []
for i in range(N):
    b, l, u = map(int, input().split())
    items.append((b, l, u, u * (X - b), - b * l))

items = sorted(items, key=lambda x: -(x[3] - x[4]))


def f(num):
    cnt = num // X
    mod = num % X
    point = 0
    for i in range(cnt):
        point += items[i][3]
    for i in range(cnt, N):
        point += items[i][4]

    if mod == 0:
        if point >= 0:
            return True
        else:
            return False
    else:
        tmp = -float("inf")
        for i in range(N):
            b, l, u, d1, d2 = items[i]
            if mod >= b:
                mul = u * (mod - b)
            else:
                mul = l * (mod - b)

            if i < cnt:
                tmp = max(tmp, point - d1 + mul + items[cnt][3] - items[cnt][4])
            else:
                tmp = max(tmp, point - d2 + mul)
        if tmp >= 0:
            return True
        else:
            return False

ok = N * X + 1
ng = - 1
while (ok - ng) > 1:
    mid = (ok + ng) // 2
    if f(mid):
        ok = mid
    else:
        ng = mid
print(ok)
### BUGGY CODE ###

while 1:
	N,M = map(int,raw_input().split())
	if N == 0: break
	T = [[0]*1261 for i in range(M)]
	r = input()
	tnms = sorted([map(int,raw_input().split()) for i in range(r)], key = lambda x:x[1])
	for i in range(0,r,2):
		t1,n,m,s = tnms[i]
		t2,n,m,s = tnms[i+1]
		T[m-1][t1:t2] = [1 for j in range(t1,t2)]
	for m in range(M):
		c = 0
		for i in range(540,1260):
			if T[m-1][i]:
				c += 1
			T[m-1][i] = c - T[m-1][i+1]
	for i in range(input()):
		ts,te,m = map(int,raw_input().split())
		print T[m-1][te] - T[m-1][ts]

### FIXED CODE ###

while 1:
	N,M = map(int,raw_input().split())
	if N == 0: break
	T = [[0]*1261 for i in range(M)]
	r = input()
	tnms = sorted([map(int,raw_input().split()) for i in range(r)], key = lambda x:x[1])
	for i in range(0,r,2):
		t1,n,m,s = tnms[i]
		t2,n,m,s = tnms[i+1]
		T[m-1][t1:t2] = [1 for j in range(t1,t2)]
	for i in range(input()):
		ts,te,m = map(int,raw_input().split())
		print sum(T[m-1][ts:te])
### BUGGY CODE ###

S=input()
count=0
for i in range(len(S)):
  for j in range(i+1,len(S)):
    if int(S[i:j+1])%2019==0:
      count+=1
print(count)

### FIXED CODE ###

from collections import defaultdict
S=input()
D=defaultdict(int)
D[0]=1
n=0
i=0
a=[0]*len(S)
b=1
for s in S[::-1]:
  n+=int(s)*b
  a[i]=n%2019
  i+=1
  b=(b*10)%2019


for i in range(len(a)):
  D[a[i]]+=1

ans=sum([i*(i-1)//2 for i in D.values()])
print(ans)
### BUGGY CODE ###

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

ans = 1
for a in A:
    ans *= a
if ans > 10**18:
    ans = -1
print(ans)


### FIXED CODE ###

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

if A.count(0):
    print(0)
    import sys
    sys.exit()

ans = 1
for a in A:
    ans *= a
    if ans > 10**18:
        print(-1)
        import sys
        sys.exit()

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

def f_c():
    n = int(input())
    s = input()

    stack, c = 1, 1
    for si in s[1:]:
        if si=="B":
            if stack%2==0:
                stack += 1
            else:
                c *= stack
                stack -= 1
        else:
            if stack%2==0:
                c *= stack
                stack -= 1
            else:
                stack += 1
    if stack!=0 or c==0:
        print(0)
    else:
        for i in range(1, n+1):
            c*=i
        print(c%(10**9+7))

if __name__ == "__main__":
    f_c()


### FIXED CODE ###

# import sys
# input = sys.stdin.readline
Q = 10**9+7
def main():
    N = int( input())
    S = input()
    left = 0
    ans = 1
    # for i in range(N*2):
    #     s = S[i]
    for s in S:
        if s == "B":
            if left%2 == 0:
                left += 1
            else:
                ans *= left
                left -= 1
        else:
            if left%2 == 1:
                left += 1
            else:
                ans *= left
                left -= 1
        ans %= Q
    if left > 0 or ans == 0:
        print(0)
        return
    for i in range(1,N+1):
        ans *= i
        ans %= Q
    print(ans)
if __name__ == '__main__':
    main()
### BUGGY CODE ###

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


def dp(n):
    if n == 0 or n == 1:
        return 1

    for i in xrange(n):
        return dp(n - 1) + dp(n - 2)


if __name__ == '__main__':
    n = input()
    print dp(n)

### FIXED CODE ###

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

memo = ['' for i in xrange(45)]
dp = [0 for i in xrange(45)]


# ?????°?????¨?¨??????????O(2^n)?????????
def recursion(n):
    if n == 0 or n == 1:
        return 1

    return recursion(n - 1) + recursion(n - 2)


# ?????¢??????????????°?¨??????????O(n)?????§????????§??????
def memo_search(n):
    if memo[n] != '':
        return memo[n]
    else:
        if n == 0 or n == 1:
            memo[n] = 1
            return 1
        memo[n] = memo_search(n - 1) + memo_search(n - 2)
        return memo[n]


# ???????¨?????????§????¨??????????O(n)??¨??????
def dynamic_programming(n):
    for i in xrange(n + 1):
        if i == 0 or i == 1:
            dp[i] = 1
        else:
            dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]


if __name__ == '__main__':
    n = input()
    # print recursion(n)
    # print memo_search(n)
    print dynamic_programming(n)
### BUGGY CODE ###

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


def cal_xor(xor_list, rm_ind):
    ans = None
    for i, xi in enumerate(xor_list):
        if i!=rm_ind:
            if ans is not None:
                ans = ans^xi
            else:
                ans = xi
    return ans

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

ans_str = ''

if N==2:
    print("{} {}".format(a[1], a[0]))
else:

    xors = []
    for i in range(N//2):
        xors.append(a[2*i]^a[2*i+1])

    for i, ai in enumerate(a):
        sum_xor = cal_xor(xors, i//2)
        if i%2==0:
            ind = i+1
        else:
            ind = i-1

        ans = sum_xor^a[ind]
        ans_str += str(ans)+' '
    print(ans_str[:-1])


### FIXED CODE ###

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


def cal_xor(xor_list):
    ans = None
    for xi in xor_list:
        if ans is not None:
            ans = ans^xi
        else:
            ans = xi
    return ans

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

ans_str = ''

if N==2:
    print("{} {}".format(a[1], a[0]))
else:

    xors = []
    for i in range(N//2):
        xors.append(a[2*i]^a[2*i+1])

    sum_xor = cal_xor(xors)
    for i, ai in enumerate(a):
        tmp_xor = sum_xor^xors[i//2]
        if i%2==0:
            ind = i+1
        else:
            ind = i-1

        ans = tmp_xor^a[ind]
        ans_str += str(ans)+' '
    print(ans_str[:-1])
### BUGGY CODE ###

import collections

h, w = map(int, input().split())
grid = [list(input()) for _ in range(h)]

INF = 10 ** 8
dist = [[INF] * w for _ in range(h)]
dy = [1, 0, -1, 0]
dx = [0, 1, 0, -1]


def bfs():
    q = collections.deque()
    for i in range(h):
        for j in range(w):
            if grid[i][j] == '#':
                q.append((i, j))
                dist[i][j] = 0
                # grid[i][j] = str(0)

    while len(q):
        py, px = q.popleft()
        for i in range(4):
            ny = py + dy[i]
            nx = px + dx[i]
            if -1 < ny < h and -1 < nx < w and grid[ny][nx] == '.' and dist[ny][nx] == INF:
                q.append((ny, nx))
                dist[ny][nx] = dist[py][px] + 1
                # grid[ny][nx] = str(dist[py][px] + 1)

    return max(max(dist, key=lambda x: max(x)))


if __name__ == '__main__':
    print(bfs())
    # for g in grid:
    #     for s in g:
    #         print(s,end='')
    #     print()
    # print()
    # for d in dist:
    #     for i in d:
    #         print(i,end='')
    #     print()


### FIXED CODE ###

import collections

h, w = map(int, input().split())
grid = [list(input()) for _ in range(h)]

INF = 10 ** 8
dist = [[INF] * w for _ in range(h)]
dy = [1, 0, -1, 0]
dx = [0, 1, 0, -1]


def bfs():
    q = collections.deque()
    for i in range(h):
        for j in range(w):
            if grid[i][j] == '#':
                q.append((i, j))
                dist[i][j] = 0
                # grid[i][j] = str(0)

    while len(q):
        py, px = q.popleft()
        for i in range(4):
            ny = py + dy[i]
            nx = px + dx[i]
            if -1 < ny < h and -1 < nx < w and grid[ny][nx] == '.' and dist[ny][nx] == INF:
                q.append((ny, nx))
                dist[ny][nx] = dist[py][px] + 1
                # grid[ny][nx] = str(dist[py][px] + 1)

    return max(max(dist, key=lambda x: max(x)))


if __name__ == '__main__':
    print(bfs())
    # for g in grid:
    #     for s in g:
    #         print(s,end='')
    #     print()
    # print()
    # for d in dist:
    #     for i in d:
    #         print(i,end='')
    #     print()
### BUGGY CODE ###

import bisect

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

for i in range(m):
    a = A.pop(-1)
    a //= 2
    bisect.insort_left(A, a)

print(sum(A))


### FIXED CODE ###

import heapq

n, m = map(int, input().split())
A = sorted(list(map(lambda x: int(x)*(-1), input().split())))

heapq.heapify(A)

for i in range(m):
    a = heapq.heappop(A)
    a = a * (-1) // 2
    heapq.heappush(A, -a)

print(-sum(A))
### BUGGY CODE ###

from heapq import heappush, heappop
import sys
input = sys.stdin.readline

N, M, L = map(int, input().split())
inf = 10**15
d = [[] for _ in range(N)]

for _ in range(M):
    A, B, C = map(int, input().split())
    if C>L:continue
    d[A-1].append((B-1, C))
    d[B-1].append((A-1, C))

dists = []
for j in range(N):
    dist = [(inf,inf)]*N
    dist[j] = (0, 0)
    q = [(0, 0, j)]
    while q:
        charged, used, u = heappop(q)
        if (charged, used) > dist[u]:
            continue
        for v, next_cost in d[u]:
            c = (charged+1, next_cost) if used+next_cost>L else (charged, used+next_cost)
            if dist[v] > c:
                dist[v] = c
                heappush(q, c+(v,))
    dists.append(dist)

Q = int(input())
for _ in range(Q):
    s, t = map(int, input().split())
    ans = dists[s-1][t-1][0]
    print(ans if ans!=inf else -1)


### FIXED CODE ###

from heapq import heappush, heappop
import sys
input = sys.stdin.readline

N, M, L = map(int, input().split())
inf = 10**15
V = [[] for _ in range(N)]

for _ in range(M):
    A, B, C = map(int, input().split())
    if C>L:continue
    V[A-1].append((B-1, C))
    V[B-1].append((A-1, C))

dists = []
for i in range(N):
    dist = [(inf,inf)] * N
    dist[i] = (0, 0)
    u = [False] * N
    for _ in range(N):
        (charged, used), j = min([(dist[i], i) for i in range(N) if not u[i]])
        u[j] = True
        for k, next_cost in V[j]:
            if j==k: continue
            c = (charged+1, next_cost) if used+next_cost>L else (charged, used+next_cost)
            if dist[k] > c:
                dist[k] = c
    dists.append(dist)

Q = int(input())
for _ in range(Q):
    s, t = map(int, input().split())
    ans = dists[s-1][t-1][0]
    print(ans if ans!=inf else -1)
### BUGGY CODE ###

N=int(input())
for n in range(1,N+1):
    ans = 0
    for i in range(1,int((N**0.5)+1)):
        for j in range(i,int((N**0.5)+1)):
            for k in range(j,int((N**0.5)+1)):
                if i**2+j**2+k**2+i*j+j*k+k*i==n:
                    if i == j and j == k:
                        ans += 1
                    else:
                        ans += 3

    print(ans)


### FIXED CODE ###

N=int(input())
ans = [0]*10000000
for i in range(1,100):
    for j in range(1,100):
        for k in range(1,100):
            ans[i**2+j**2+k**2+i*j+j*k+i*k] += 1
for i in range(1,N+1):
    print(ans[i])
### BUGGY CODE ###

n = int(input())
x = list(map(int,input().split()))
for i in range(n):
    xx = x[:i] + x[i+1:]
    xx.sort()
    print(xx[n//2 - 1])


### FIXED CODE ###

n = int(input())
x = list(map(int,input().split()))
y = list(x)
y.sort()
z = n // 2 - 1
a = y[z]
b = y[z + 1]
for i in x:
    if i <= a :
        ans = b
    else:
        ans = a
    print(ans)
### BUGGY CODE ###

def main():
    n = int(input())
    a = [int(i) for i in input().split()]
    c = 0
    for i, ai in enumerate(a):
        for j in range(i + ai + 1, n):
            if j - i == ai + a[j]:
                c += 1
    print(c)

if __name__ == '__main__':
    main()

### FIXED CODE ###

from collections import defaultdict

def main():
    n = int(input())
    l = defaultdict(int)
    r = defaultdict(int)
    for i, ai in enumerate(map(int, input().split())):
        l[i - ai] += 1
        r[i + ai] += 1
    print(sum(l[i] * r[i] for i in range(1, n - 1)))

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

K,S=[int(i) for i in input().split()]
a=0
for x in range(K+1):
    for y in range(K+1):
        for z in range(K+1):
            if x+y+z==S:
                a+=1
print(a)

### FIXED CODE ###

K,S=[int(i) for i in input().split()]
a=0
for x in range(K+1):
    for y in range(K+1):
        z=S-x-y
        if 0<=z and K>=z:
            a+=1
print(a)
### BUGGY CODE ###

n = int(input())
rides = [0]*5
for i in range(5):
    rides[i] = int(input())

time = 0
p = [0]*6
p[0] = n
while p[5] != n:
    time+=1
    for i in range(4,-1,-1):
        if p[i] > 0:
            if p[i] >= rides[i]:
                p[i+1] += rides[i]
                p[i] -= rides[i]
            else:
                p[i+1] += p[i]
                p[i] = 0

print(time)


### FIXED CODE ###

import math

n = int(input())
rides = [0]*5
for i in range(5):
    rides[i] = int(input())

time = 0
mini = min(rides)
time = math.ceil(n/mini)+4

print(time)
### BUGGY CODE ###

from collections import deque
import bisect
from copy import copy

n = int(input())
a = list(map(int, input().split()))
to=[list() for _ in range(n)]

for i in range(n-1):
    u,v = map(int, input().split())
    u-=1
    v-=1
    to[u].append(v)
    to[v].append(u)

d= deque()
INF=10010001001
dpinit = [a[0]]
d.append((0,-1,copy(dpinit)))
ansls=[0]*n
ansls[0]=1
while d:
    u,p,dp = d.pop()
    for v in to[u]:
        if v==p:
            continue
        dp2=copy(dp)
        idx=bisect.bisect_left(dp2,a[v])
        if idx<len(dp2):
            dp2[idx]=a[v]
        else:
            dp2.append(a[v])
        ansls[v]=len(dp2)
        d.append((v,u,dp2))

print(*ansls,sep='\n')
        










### FIXED CODE ###

from collections import deque
import bisect
import sys
sys.setrecursionlimit(500000)

n = int(input())
a = list(map(int, input().split()))
to=[list() for _ in range(n)]

for i in range(n-1):
    u,v = map(int, input().split())
    u-=1
    v-=1
    to[u].append(v)
    to[v].append(u)

INF=1001001001
dp = [INF]*n
dp[0]=a[0]
ansls=[0]*n
ansls[0]=1
history=deque()
def dfs(u,p,rank):
    for v in to[u]:
        if v==p:
            continue
        idx=bisect.bisect_left(dp,a[v])
        prv=dp[idx]
        dp[idx]=a[v]       
        history.append((idx,prv))
        ansls[v]=bisect.bisect_left(dp,INF)
        dfs(v,u,rank+1)
        while len(history)>rank:
            idx,prv =history.pop()
            dp[idx] = prv

dfs(0,-1,0)

print(*ansls,sep='\n')
### BUGGY CODE ###

#!/usr/bin/env python3
import sys


def solve(S: str):
    ans = 0
    if S == '0':
        print(ans)
        return
    N = len(S)
    for i in range(min(S.count('0'), S.count('1'))):
        if len(S) > 0:
            S = S.replace('10', '')
            S = S.replace('01', '')
        else:
            break
        if S.count('10') == 0 and S.count('01') == 0:
            break
    ans = N - len(S)
    print(ans)

# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    S = str(input())
    solve(S)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys


def solve(S: str):
    stack = []
    N = len(S)
    for i, s in enumerate(S):
        if i == 0:
            stack.append(s)
        else:
            if len(stack) == 0:
                stack.append(s)
            else:
                if s != stack[-1]:
                    tmp = stack.pop()
                else:
                    stack.append(s)
    print(N - len(stack))

# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    S = str(input())
    solve(S)

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

from collections import Counter

mod = 10 ** 9 + 7
N = int(input())
X = list(map(int,input().split()))
L = [0] * N
for i in range(N):
    cnt = 0
    for j in range(i):
        if X[j] > cnt * 2:
            cnt += 1
    L[i] = i - cnt
d = Counter(L)
ans = 1
tmp = 0
for i in range(10 ** 5):
    tmp += d[i]
    if tmp == 0:
        break
    ans *= tmp
    ans %= mod
    tmp -= 1
print(ans)

### FIXED CODE ###

from collections import Counter

mod = 10 ** 9 + 7
N = int(input())
X = list(map(int,input().split()))
L = [0] * N
for i in range(N-1):
    L[i+1] += L[i]
    if X[i] > L[i] * 2:
        L[i+1] += 1

for i in range(N):
    L[i] = i - L[i]

d = Counter(L)
ans = 1
tmp = 0
for i in range(10 ** 5):
    tmp += d[i]
    if tmp == 0:
        break
    ans *= tmp
    ans %= mod
    tmp -= 1
print(ans)
### BUGGY CODE ###

n,m = map(int,input().split())
A = list(map(int,input().split()))
A.sort()
B=[]
C=[]
for i in range(m):
  b,c = map(int,input().split())
  B.append(b)
  C.append(c)
L = list(zip(C,B))
L.sort(reverse = True)
L2 = []
for i in range(m):
  L2.extend([L[i][0]]*L[i][1])
#print(L2)
ans = 0
for i in range(n):
  if i >= len(L2): ans+=A[i]
  else:
    if L2[i] > A[i]:ans+=L2[i]
    else: ans+=A[i]
print(ans)

### FIXED CODE ###

n,m = map(int,input().split())
A = list(map(int,input().split()))
CntA = [1 for i in range(n)]
for i in range(m):
  b,c = map(int,input().split())
  A.append(c)
  CntA.append(b)
Z = list(zip(A,CntA))
Z.sort(reverse=True)
ans = 0
for z in Z:
  if n>z[1]:
    ans+=z[1]*z[0]
    n-=z[1]
  else:
    ans+=n*z[0]
    break
print(ans)
### BUGGY CODE ###

# 2019-11-13 08:30:54(JST)
import sys
# import collections
# import math
# from string import ascii_lowercase, ascii_uppercase, digits
# from bisect import bisect_left as bi_l, bisect_right as bi_r
# import itertools
# from functools import reduce
# import operator as op
# from scipy.misc import comb # float
# import numpy as np 

def main():
    n, m = [int(x) for x in sys.stdin.readline().split()]

    l, r = [], []
    for _ in range(m):
        li, ri = [int(x) for x in sys.stdin.readline().split()]
        l.append(li)
        r.append(ri)
    
    all_mighty_cards = set(range(1,n+1))
    for i in range(m):
        all_mighty_cards &= set(l[i:] + r[:i+1])
    


    print(max(all_mighty_cards) - min(all_mighty_cards) + 1 if all_mighty_cards else 0)

    

if __name__ == "__main__":
    main()


### FIXED CODE ###

# 2019-11-13 08:30:54(JST)
import sys
# import collections
# import math
# from string import ascii_lowercase, ascii_uppercase, digits
# from bisect import bisect_left as bi_l, bisect_right as bi_r
# import itertools
# from functools import reduce
# import operator as op
# from scipy.misc import comb # float
# import numpy as np 

def main():
    n, m = [int(x) for x in sys.stdin.readline().split()]

    l, r = [], []
    for _ in range(m):
        li, ri = [int(x) for x in sys.stdin.readline().split()]
        l.append(li)
        r.append(ri)
    
    print(min(r) - max(l) + 1 if min(r) >= max(l) else 0)



if __name__ == "__main__":
    main()