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

import sys
input = sys.stdin.readline
#n = int(input())
#l = list(map(int, input().split()))
'''
A=[]
B=[]
for i in range():
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)'''

import bisect
n, m = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
#print(a)

bc=[]
for i in range(m):
    B = list(map(int, input().split()))
    bc.append(B)
bc.sort(key=lambda x: x[1])
#print(bc)

for i in range(m):
    x = bisect.bisect_left(a, bc[i][1])
    if x!=0:
        a += [bc[i][1]]*min(bc[i][0],x)
    #print(a)
a.sort()
print(sum(a[len(a)-n:]))

### FIXED CODE ###

import sys
input = sys.stdin.readline
#n = int(input())
#l = list(map(int, input().split()))
'''
A=[]
B=[]
for i in range():
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)'''

n,m=map(int,input().split())
a=list(map(int,input().split()))
a.sort()
bc=[list(map(int,input().split())) for _ in range(m)]
bc.sort(key=lambda x: x[1],reverse=True)
#print(bc)
cnt=0
for i in range(n):
    if bc[cnt][0]>0:
        if bc[cnt][1]>a[i]:
            a[i]=bc[cnt][1]
        bc[cnt][0]-=1
    else:
        cnt+=1
        if cnt==len(bc):
            break
        if bc[cnt][1]>a[i]:
            a[i]=bc[cnt][1]
        bc[cnt][0]-=1
    #print(cnt,bc,a)
print(sum(a))
### BUGGY CODE ###

from fractions import gcd

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

max_g = As[1]
for i in range(2, N):
    max_g = gcd(As[i], max_g)

for i in range(1, N):
    g = As[0]
    for j in range(1, N):
        if j == i:
            continue
        g = gcd(As[j], g)
    max_g = max(max_g, g)

print(max_g)

### FIXED CODE ###

nl = lambda: list(map(int, input().split()))
sl = lambda: input().split()
n = lambda: int(input())
s = lambda: input()

N = n()
As = nl()

from fractions import gcd
gcds_left = [0] * N
gcds_right = [0] * N
gcds_left[0] = As[0]
gcds_right[N-1] = As[N-1]

for i in range(1, N):
    gcds_left[i] = gcd(As[i], gcds_left[i-1])
    gcds_right[N-1-i] = gcd(As[N-1-i], gcds_right[N-i])

max_gcd = -1
for i in range(1, N-1):
    g = gcd(gcds_left[i-1], gcds_right[i+1])
    if g > max_gcd:
        max_gcd = g
print(max(max_gcd, gcds_right[1], gcds_left[N-2]))
### BUGGY CODE ###

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

l=[]

for i in range(m):
  a,b = map(int,input().split())
  c = [int(x) for x in input().split()]
  s = 0
  for j in c:
    s += 2**(j-1)
  l.append([s,a])

#print(l)

v=[[10**7 for x in range(2**n)] for y in range(2)]
v[0][0]=0

i=0
for s,a in l:
  for j in range(2**n):
    v[(i+1)%2][j] = v[i%2][j]
  for j in range(2**n):
    if v[i%2][j] != 10**7:
      v[(i+1)%2][j|s] = min(v[(i+1)%2][j|s], v[i%2][j]+a)
  i+=1

print(v[(i+1)%2][2**n-1] if v[(i+1)%2][2**n-1] != 10**7 else -1)


### FIXED CODE ###

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

f=[10**7 for x in range(2**n)]
for i in range(m):
  a,b = map(int,input().split())
  c = [int(x) for x in input().split()]
  s = 0
  for j in c:
    s += 2**(j-1)
  f[s]=min(f[s],a)

l=[]
for i in range(2**n):
  if f[i] != 10**7:
    l.append([i,f[i]])

v=[10**7 for x in range(2**n)]
v[0]=0

for s,a in l:
  for j in range(2**n):
    if v[j] != 10**7:
      v[j|s] = min(v[j|s], v[j]+a)

print(v[2**n-1] if v[2**n-1] != 10**7 else -1)
### BUGGY CODE ###

N = int(input())
s = input()

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

for i in range(N-1, 0, -1):
  for j in range(N-1, 0, -1):
    if s[i] != s[j]:
      dp[i][j] = 0
    else:
      dp[i][j] = dp[i+1][j+1] + 1
    
ans = 0
for i in range(N):
  for j in range(N):
    if i >= j:
      continue
    now = min(dp[i][j], j - i)
    ans = max(ans, now)
print(ans)


### FIXED CODE ###

N = int(input())
s = input()

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

for i in range(N-1, -1, -1):
  for j in range(N-1, -1, -1):
    if s[i] != s[j]:
      dp[i][j] = 0
    else:
      dp[i][j] = dp[i+1][j+1] + 1
    
ans = 0
for i in range(N):
  for j in range(N):
    if i >= j:
      continue
    now = min(dp[i][j], j - i)
    ans = max(ans, now)
print(ans)
### BUGGY CODE ###

n = int(input())
t = list(map(int, input().split()))
r = []
ans = 0
for i in range(len(t)):
  r.append(i+1 + t[i])
for i in range(len(t)):
  if((i+1 - t[i]) >= 1):
    ans += r.count(i+1-t[i])
print(ans)

### FIXED CODE ###

n = int(input())
t = list(map(int, input().split()))
r = {}
ans = 0
for i in range(len(t)):
  try:
    r[i+1 + t[i]] += 1
  except KeyError:
    r[i+1 + t[i]] = 1
for i in range(len(t)):
  if((i+1 - t[i]) >= 1):
    try:
      ans += r[i+1-t[i]]
    except KeyError:
      continue
print(ans)
### BUGGY CODE ###

import itertools
n = int(input())
s = list(map(str,input()))
count =0
for i in range(1, len(s)+1):
    cand = list(itertools.combinations(s, i))
    if i ==1:
        count += len(cand)
    else:
        for j in range(len(cand)):
            if len(set(cand[j])) == i:
                count +=1
print(count % (10**9 + 7 ))

### FIXED CODE ###

n = int(input())
s = list(map(str,input()))
count = 1
unique = list(set(s))
for i in unique:
    count *= (s.count(i) + 1)
count -=1
print(count % (10**9 + 7))
### BUGGY CODE ###

import queue
import sys
sys.setrecursionlimit(10**7)
N, Q = map(int, input().split())

edges = [[] for _ in range(N)]
for i in range(N-1):
    a, b = map(int, input().split())
    edges[a-1].append(b-1)
    edges[b-1].append(a-1)

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

def dfs(v, par):
    for nv in edges[v]:
        if nv == par:
            continue
        points[nv] += points[v]
        dfs(nv, v)

dfs(0, -1)

print(*points)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
N, Q = map(int, input().split())

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

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

def dfs(v, par):
    for nv in edges[v]:
        if nv == par:
            continue
        points[nv] += points[v]
        dfs(nv, v)

dfs(0, -1)

print(*points)
### BUGGY CODE ###

from collections import deque
import sys
input = sys.stdin.readline


a = list(input())
a.pop(-1)

Q = int(input())
count = 0
for _ in range(Q):
    q = list(input().split())
    if q[0] == "1":
        count += 1
        # a.reverse()
    else:
        if count % 2 == 0:
            if q[1] == "1":
                # a.insert(0, q[2])
                b = deque(a)
                b.appendleft(q[2])
                a = list(b)
            else:
                a.append(q[2])
        else:
            if q[1] == "1":
                a.append(q[2])
            else:
                # a.insert(0, q[2])
                b = deque(a)
                b.appendleft(q[2])
                a = list(b)

if count % 2 != 0:
    a.reverse()
print("".join(a))


### FIXED CODE ###

from collections import deque
import sys
input = sys.stdin.readline
sys.setrecursionlimit(4100000)


def main():
    a = deque(input())
    a.pop()

    a_append = a.append
    a_appendleft = a.appendleft

    Q = int(input())
    count = 0
    for _ in range(Q):
        q = list(input().split())
        if q[0] == "1":
            count += 1
        else:
            if count % 2 == 0:
                if q[1] == "1":
                    a_appendleft(q[2])
                else:
                    a_append(q[2])
            else:
                if q[1] == "1":
                    a_append(q[2])
                else:
                    a_appendleft(q[2])

    b = list(a)
    if count % 2 != 0:
        b.reverse()
    print("".join(b))


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

n,a,b,k=map(int,input().split())
def kai(n):
    k=1
    s=1
    while k<=n:
        s=(s*k)%998244353
        k=k+1
    return int(s%998244353)

def com(n,m):
    l=((kai(n)%998244353)/((kai(m)%998244353)*(kai(n-m)%998244353)))%998244353
    return int(l)

def rbg(n,a,b,k):
    x=0
    while x<=b:
        if (a*x)%b==k%b:
            y=(k-a*x)/b
            s=0
            while y>=0:
                    c=x+y
                    if c<=n:
                        d=0
                    else:
                        d=c-n
                    e=min(x,y)
                    z=0
                    while d<=e:
                        z=(z+(com(n,d)%998244353)*(com(n-d,x-d)%998244353)*(com(n-x,y-d)%998244353))%998244353
                        d=d+1
                    s=(s+z)%998244353
                    x=x+b
                    y=y-a
            return(s%998244353)
        x=x+1
    return False
print(rbg(n,a,b,k))

### FIXED CODE ###

n, a, b, kk = map(int, input().split())

MOD = 998244353
N = n + 10
fact = [0 for _ in range(N)]
invfact = [0 for _ in range(N)]
fact[0] = 1
for i in range(1, N):
    fact[i] = fact[i - 1] * i % MOD

invfact[N - 1] = pow(fact[N - 1], MOD - 2, MOD)

for i in range(N - 2, -1, -1):
    invfact[i] = invfact[i + 1] * (i + 1) % MOD
def nCk(n, k):
    if k < 0 or n < k:
        return 0
    else:
        return fact[n] * invfact[k] * invfact[n - k] % MOD
        
ans = 0
for i in range(n + 1):
    j = (kk - a * i)
    if j % b != 0:
        continue
    ans += nCk(n, i) * nCk(n, j // b)
    ans %= MOD
    
print(ans)
### BUGGY CODE ###

import bisect
n , m = map(int, input().split())
a = list(map(int,input().split()))
a.sort()

for i in range(m):
    t = a[n-1]//2
    index = bisect.bisect_left(a,t)
    a.insert(index,t)

a=a[:n]
print(sum(a))


### FIXED CODE ###

import heapq
n , m = map(int, input().split())
a = list(map(int,input().split()))
for i in range(n):
    a[i]*=-1
heapq.heapify(a)

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

print(sum(a)*(-1))
### BUGGY CODE ###

from collections import Counter
N =int(input())
A = Counter(list(map(int,input().split())))
B = Counter(list(map(int,input().split())))
C = Counter(list(map(int,input().split())))
A_sort = sorted(A.items())
B_sort = sorted(B.items())
C_sort = sorted(C.items())

BtoC = []
ans = 0
start_j = 0
start_k = 0
sum_val = N
for j in range(len(B_sort)):
    for k in range(start_k , len(C_sort)):
        if B_sort[j][0] >= C_sort[k][0]:
            sum_val -= C_sort[k][1]
            start_k = k + 1
        else:
            BtoC.append([B_sort[j][0] , sum_val * B_sort[j][1]])
            break

for i in range(len(A_sort)):
    for j in range(start_j , len(BtoC)):
        if A_sort[i][0] >= BtoC[j][0]:
            start_j = j + 1
            continue
        else:
            ans += A_sort[i][1] * BtoC[j][1]
print(ans)

### FIXED CODE ###

from collections import Counter
N =int(input())
A = Counter(list(map(int,input().split())))
B = Counter(list(map(int,input().split())))
C = Counter(list(map(int,input().split())))
A_sort = sorted(A.items())
B_sort = sorted(B.items())
C_sort = sorted(C.items())

BtoC = []
ans = 0
start_j = 0
start_k = 0
sum_val = N
for j in range(len(B_sort)):
    for k in range(start_k , len(C_sort)):
        if B_sort[j][0] >= C_sort[k][0]:
            sum_val -= C_sort[k][1]
            start_k = k + 1
        else:
            BtoC.append([B_sort[j][0] , sum_val * B_sort[j][1]])
            break
#print(BtoC)
work = 0
for i in range(len(BtoC) - 2 , -1 , -1):
    BtoC[i][1] = BtoC[i+1][1] + BtoC[i][1]
    work = BtoC[i+1][1]
#print(BtoC)
for i in range(len(A_sort)):
    for j in range(start_j , len(BtoC)):
        if A_sort[i][0] >= BtoC[j][0]:
            start_j = j + 1
        else:
            ans += A_sort[i][1] * BtoC[j][1]
            break
print(ans)
### BUGGY CODE ###

A, B, C = map(int, input().split())
K = int(input())

i = 0

while i<K:
  if B<=A:
    B *= 2
    i += 1
  elif C<=B:
    C*= 2
    i += 1

if A<B and B<C:
  print('Yes')
else:
  print('No')


### FIXED CODE ###

A, B, C = map(int, input().split())
K = int(input())

i = 0

while B<=A:
  i += 1
  B *= 2

while C<=B:
  i += 1
  C *= 2

if i<=K:
  print('Yes')
else:
  print('No')
### BUGGY CODE ###

import numpy as np
from fractions import gcd

MOD = 10**9+7
N = int(input())
A = list(map(int, input().split()))

x = 1
ans = 0
for i in range(N):
    tmp = gcd(x, A[i])
    # ans += (i) * A[i] // tmp + A[i] * x //tmp  
    x = (x * A[i]) // tmp
    
b = 0
for i in range(N):
    b += x // A[i]
    
print(b%MOD)


### FIXED CODE ###

import fractions 
#from functools import reduce
import functools

MOD = 10**9+7


def main():
    # N = int(input())
    # A = list(map(int, input().split()))
    N, *A = map(int, open(0).read().split())
            
    x = 1
    for a in A:
        x *= a //  fractions.gcd(x, a)
        
    b = sum(x//a for a in A)
    print(b%MOD)
    
if __name__== "__main__":
    main()
### BUGGY CODE ###

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

ans = 1

for i in range(1, len(list_P)) :
    if list_P[i] == min(list_P[:(i+1)]) :
        ans += 1

print(ans)


### FIXED CODE ###

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

ans = 0
min = N+1

for i in list_P :
    if i < min :
        ans += 1
        min = i

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

n=int(input())
th,ah=1,1
for i in range(n):
    t,a=map(int,input().split())
    while 1:
        if th*a>ah*t:ah+=1
        elif th*a<ah*t:th+=1
        elif th*a==ah*t:break
print(th+ah)

### FIXED CODE ###

n=int(input())
th,ah=1,1
for i in range(n):
    t,a=map(int,input().split())
    n=max((th+t-1)//t,(ah+a-1)//a)
    th,ah=n*t,n*a
print(th+ah)
### BUGGY CODE ###

n = int(input())
an = list(map(int, input().split()))
bn = list(set(an))
allcount = 0
for i in bn:
    a = an.count(i)
    allcount += a*(a-1)//2
daburi = []
for i in an:
    daburi.append(an.count(i))
for i in daburi:
    ans = allcount - (i-1)
    print(ans)

### FIXED CODE ###

n = int(input())
an = list(map(int, input().split()))
import collections

c = collections.Counter(an)
allcount = 0

for i in c.values():
    allcount += i*(i-1)//2

for i in an:
    print(allcount - (c[i]-1))
### BUGGY CODE ###

import sys

def prime(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for j in range(4, n+1, 2):
        is_prime[j] = False
    for i in range(3, int(n**0.5) + 1, 2):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    return [i for i in range(n + 1) if is_prime[i]]

def main():
    input = sys.stdin.readline
    mod = pow(10,9)+7
    n = int(input())
    a = [int(x) for x in input().split()]
    
    prime_list = prime(max(a))
    len_list = len(prime_list)
    L_prime = [0]*len_list
    for i in range(n):
        judge = a[i]
        for j in range(len_list):
            count = 0
            while not judge%prime_list[j]:
                count += 1
                judge //= prime_list[j]
            if count > L_prime[j]:
                L_prime[j] = count
    ans = 0
    for i in range(n):
        key = 1
        judge = a[i]
        for j in range(len(prime_list)):
            count = 0
            while not judge%prime_list[j]:
                count += 1
                judge //= prime_list[j]
            key *= pow(prime_list[j], L_prime[j]-count, mod)
            key %= mod
        ans += key
        ans %= mod
    
    print(ans)
            


if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
from collections import Counter

def prime_factorize(n):
    ans = []
    while not n%2:
        ans.append(2)
        n //= 2
    mod = 3
    while mod**2 <= n:
        if n%mod == 0:
            ans.append(mod)
            n //= mod
        else:
            mod += 2
    if n != 1:
        ans.append(n)
    counter = Counter(ans)
    return counter

def main():
    input = sys.stdin.readline
    mod = pow(10,9)+7
    n = int(input())
    a = [int(x) for x in input().split()]
    
    prime_list = dict()
    for i in range(n):
        primes = prime_factorize(a[i])
        for key, value in primes.items():
            if key in prime_list:
                if prime_list[key] < value:
                    prime_list[key] = value
            else:
                prime_list[key] = value
    
    L = 1
    for key, value in prime_list.items():
        L *= pow(key, value, mod)
        L %= mod
        
    ans = 0
    for i in range(n):
        ans += (L*pow(a[i], mod-2, mod))%mod
        ans %= mod
    
    print(ans)
            


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

count = 0

def rec(l, r):
    global count
    global h

    if l >= r:
        return

    zero = list()
    for i in range(l, r):
        if h[i] == 0:
            zero.append(i)

    if len(zero) > 0:
        for i in zero:
            rec(l, i)
            rec(i+1, r)
    else:
        for i in range(l, r):
            h[i] -= 1
        count += 1
        rec(l, r)

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

rec(0, len(h))
print(count)


### FIXED CODE ###

count = 0

def rec(l, r):
    global count
    global h
    global s

    if l >= r:
        return

    zero = list()
    for i in range(l, r):
        if h[i] == 0:
            zero.append(i)

    if len(zero) > 0:
        for i in zero:
            if not (l, i) in s:
                rec(l, i)
                s.add((l, i))
            if not (i+1, r) in s:
                rec(i+1, r)
                s.add((i+1, r))
    else:
        for i in range(l, r):
            h[i] -= 1
        count += 1
        rec(l, r)

n = int(input())
h = list(map(int, input().split()))
s = set()

rec(0, len(h))
print(count)
### BUGGY CODE ###

s = input()
n = len(s)
mod = 10**9+7
DP = [[0 for i in range(13)] for j in range(n+1)]
DP[0][0] = 1
for i in range(n):
    if s[i] != "?":
        x = int(s[i])
        for j in range(13):
            DP[i+1][(j*10+x)%13] = (DP[i+1][(j*10+x)%13]+DP[i][j])%mod
    else:
        for j in range(13):
            for k in range(10):
                DP[i+1][(j*10+k)%13] = (DP[i+1][(j*10+k)%13]+DP[i][j])%mod
print(DP[n][5])


### FIXED CODE ###

s = input()
n = len(s)
mod = 10**9+7
DP = [[0 for i in range(13)] for j in range(n+1)]
DP[0][0] = 1
for i in range(n):
    if s[i] != "?":
        x = int(s[i])
        for j in range(13):
            DP[i+1][(j*10+x)%13] = (DP[i+1][(j*10+x)%13]+DP[i][j])%mod
    else:
        for j in range(13):
            for k in range(10):
                DP[i+1][(j*10+k)%13] = (DP[i+1][(j*10+k)%13]+DP[i][j])%mod
print(DP[n][5])
### BUGGY CODE ###

import math
N,W = list(map(int, input().split(" ")))

items= [list(map(int, input().split(" "))) for _ in range(N)]


dp = [[0 for _ in range(W+1)] for _ in range(N + 1) ]
#dp[今何個目か][重さ何キロ持つか] = その時の価値の最大値
dp[0][0] = 0
for j in range(N): #j 個目の荷物で
    for i in range(W+1): #重さ i のときに得られる価値
        w,v = items[j]
        if i >= w: # w > i だと前提が破綻するので
            #遷移 d[j + 1][i] =  (d[j][i - w] + v ) 新しい荷物を選んだ場合
            dp[j + 1 ][i] = dp[j][i - w]  + v  # dp[j][i - w]  + v → j 個持ったところに、更に 価値v のitemが追加されて j+ 1になった
        dp[j + 1][i] =  max(dp[j + 1][i] ,dp[j][i]) #選ばなかった場合
print(dp[-1][-1])

### FIXED CODE ###

import math
N,W = list(map(int, input().split(" ")))

items= [list(map(int, input().split(" "))) for _ in range(N)]


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


        w,v = items[i]
        if w_sum - w >= 0:
            dp[i + 1][w_sum]  = dp[i][w_sum - w] + v
        # print(dp[i + 1][w],dp[i][w])
        a,b = dp[i + 1][w_sum],dp[i][w_sum]
        dp[i + 1][w_sum] = max(a,b)

print(dp[-1][-1])
### BUGGY CODE ###

n,k,q=map(int,input().split())
a=[int(input()) for i in range(q)]
ans = []
for i in range(n):
  ans.append(k)
for i in range(q):
  for j in range(n):
    if a[i] != j +1:
      ans[j] -= 1

for i in range(n):
  if ans[i] <= 0:
    print("No")
  else:
    print("Yes")

### FIXED CODE ###

n,k,q=map(int,input().split())
a=[int(input()) for i in range(q)]
ans = []
def calc(n):
    return n-q
for i in range(n):
  ans.append(k)
ans = list(map(calc, ans))
for i in range(q):
  ans[a[i]-1]+= 1
for i in range(n):
  if ans[i] <= 0:
    print("No")
  else:
    print("Yes")
### BUGGY CODE ###

n = int(input())
a = [int(i) for i in input().split()]
b = [int(i) for i in input().split()]
c = [int(i) for i in input().split()]



#%%
# n = 6
# a = [3, 14, 159, 2, 6, 53]
# b = [58, 9, 79, 323, 84, 6]
# c = [2643, 383, 2, 79, 50, 288]

#%%
a.sort()
b.sort()
c.sort()

#%%
ans = 0

for ci in c:
    for bi in b:
        if ci > bi:
            for ai in a:
                if bi > ai:
                    # print(ci, bi, ai)
                    ans += 1
                else:
                    break
        else:
            break

#%%
print(ans)

#%%


### FIXED CODE ###

def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
# import bisect

N = INT()
A = LIST()
B = LIST()
C = LIST()

A.sort()
B.sort()
C.sort()

def binsearch(lst, th, ud="up"):
    left, right = -1, len(lst)
    while right - left > 1:
        mid = (left + right) // 2
        if ud == "up":
            if lst[mid] > th:
                right = mid
            else:
                left = mid
        else:
            if lst[mid] >= th:
                right = mid
            else:
                left = mid
        
    return right if ud == "up" else left


ans = 0
# for ai in A:
#     i = bisect.bisect_right(B, ai)
#     for bi in B[i:]:
#         j = bisect.bisect_right(C, bi)
#         ans += len(C[j:])

for bi in B:
    i = binsearch(A, bi, "down")
    j = binsearch(C, bi, "up")
    ans += (i+1) * (N-j)


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

import sys
import numpy as np
from scipy.sparse.csgraph import dijkstra
from scipy.sparse import csr_matrix

read = sys.stdin.read
readline = sys.stdin.readline

n, m, s, t, *uvab = map(int, read().split())
s -= 1
t -= 1
u = np.array(uvab[::4], np.int64) - 1
v = np.array(uvab[1::4], np.int64) - 1
a = np.array(uvab[2::4], np.float_)
b = np.array(uvab[3::4], np.float_)

yen_matrix = csr_matrix((a, (u, v)), shape=(n, n))
snuuk_matrix = csr_matrix((b, (u, v)), shape=(n, n))

yen = dijkstra(yen_matrix, directed=False, indices=s)
snuuk = dijkstra(snuuk_matrix, directed=False, indices=t)

costs = (yen + snuuk).astype(int)
answer = 10 ** 15 - np.minimum.accumulate(costs[::-1])[::-1]
print(*answer.tolist(), sep='\n')


### FIXED CODE ###

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

import numpy as np
from heapq import heappush, heappop

N,M,S,T, *uvab = map(int,input().split())
graph = [[] for _ in range(N+1)]
for u,v,a,b in zip(*[iter(uvab)]*4):
    graph[u].append((v,a,b))
    graph[v].append((u,a,b))

def dijkstra(start, mode):
    INF = 10 ** 15
    dist = [INF] * (N+1)
    dist[start] = 0
    q = [(0,start)]
    while q:
        d,v = heappop(q)
        if dist[v] < d:
            continue
        for w,*a in graph[v]:
            d1 = d + a[mode]
            if dist[w] > d1:
                dist[w] = d1
                heappush(q, (d1,w))
    return dist

d1 = np.array(dijkstra(S,0))
d2 = np.array(dijkstra(T,1))

d1 += d2
answer = 10 ** 15 - np.minimum.accumulate(d1[::-1])[::-1][1:]
print('\n'.join(map(str, answer.tolist())))
### BUGGY CODE ###

s = list(input())

ans = 0
for i in range(len(s)):
    for j in range(len(s) - 1):
        if s[j] == "B" and s[j + 1] == "W":
            ans += 1
            s[j] = "W"
            s[j + 1] = "B"


print(ans)

### FIXED CODE ###

s = list(input())

ans = 0
x = len(s) - 1
for i in range(len(s) - 1, -1, -1):
    if s[i] == "B":
        ans += x - i
        x -= 1

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

import math

n = int(input())
lst = list(map(float, input().split()))

dp = [[0] * (n+1) for _ in range(n+1)] #行は表の枚数、列は試行回数
dp[0][0] = 1
for i in range(0, n):
    for j in range(0, n):
        dp[i+1][j+1] += dp[i][j] * lst[i] #表のとき
        dp[i+1][j] += dp[i][j] * (1 - lst[i]) #裏のとき
        
hlf = math.ceil(n/2)
ansl = dp[n][hlf:n+1]
ans = sum(ansl)
print(ans)

### FIXED CODE ###

import math

n = int(input())
lst = list(map(float, input().split()))

dp = [[0] * (n+1) for _ in range(n+1)] #行は表の枚数、列は試行回数
dp[0][0] = 1
for i in range(0, n):
    for j in range(0, n):
        dp[i+1][j+1] += dp[i][j] * lst[i] #表のとき
        dp[i+1][j] += dp[i][j] * (1 - lst[i]) #裏のとき
        
hlf = math.ceil(n/2)
ansl = dp[n][hlf:n+1]
ans = sum(ansl)
print(ans)