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

from collections import defaultdict
n,m=map(int,input().split())
A=[int(i) for i in input().split()]
A.sort()
D=defaultdict(int)
for i in range(m):
  b,c=map(int,input().split())
  D[c]+=b
D=sorted(D.items(),key=lambda x:x[0],reverse=True)
DD=[0]*n
ct=0
for x,y in D:
  for i in range(y):
    if i+ct<n:
      DD[i+ct]+=x
  ct+=y
ans=0
for i in range(n):
  ans+=max(A[i],DD[i])
print(ans)


### FIXED CODE ###

from collections import defaultdict
from collections import Counter
n,m=map(int,input().split())
A=[int(i) for i in input().split()]
AA=dict(Counter(A))
D=defaultdict(int)
for i in range(m):
  b,c=map(int,input().split())
  D[c]+=b
for x in AA.keys():
  D[x]+=AA[x]
D=sorted(D.items(),key=lambda x:x[0],reverse=True)
ans,tot=0,0
for x,y in D:
  if tot+y<=n:
    ans+=x*y
    tot+=y
  else:
    ans+=x*(n-tot)
    tot+=n-tot
  if tot==n:
    break
print(ans)
### BUGGY CODE ###

import itertools
n = int(input())
s = input()
itr = itertools.combinations(range(n), 3)
cnt = 0
for tpl in itr:
  if (tpl[2] - tpl[1] != tpl[1] - tpl[0] and 
      len(set([s[tpl[0]], s[tpl[1]], s[tpl[2]]])) == 3):
    cnt += 1
print(cnt)

### FIXED CODE ###

n = int(input())
s = input()
cnt = s.count('R') * s.count('G') * s.count('B')
for i in range(n - 1):
  for j in range(i + 1, n):
    if 2 * j - i <= n - 1 and len(set([s[i], s[j], s[2 * j - i]])) == 3:
      cnt -= 1
print(cnt)
### BUGGY CODE ###

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

for i in range(N):
	t = A[i]
	A[i] = 0
	print(max(A))
	A[i] = t



### FIXED CODE ###

N = int(input())
A = []
M = 0
p = 0
for i in range(N):
	t = int(input())
	A.append(t)
	if M < t:
		M = t
		p = i

A[p] = 0
sec = max(A)

for i in range(N):
	if i == p:
		print(sec)
	else:
		print(M)
### BUGGY CODE ###

a = input()
q = int(input())
for i in range(q):
    qi=input()
    if qi==str(1):
        a = a[::-1]
    else:
        qi = qi.split()
        if qi[1]==str(1):
            a = qi[2]+a
        else:
            a = a + qi[2]
print(a)

### FIXED CODE ###

import collections
 
s = collections.deque(list(input()))
q = int(input())
rev = 0
for i in range(q):
    tfc = list(input().split())
    if tfc[0]=='1':
        rev = abs(rev-1)
    else:
        t,f,c = tfc
        if rev:
            if f=='1':
                s.append(c)
            else:
                s.appendleft(c)
        else:
            if f=='1':
                s.appendleft(c)
            else:
                s.append(c)
if rev:
    t = []
    for i in range(len(s)):
        t.append(s.pop())
    print(''.join(t))
else:
    print(''.join(s))
### BUGGY CODE ###

N = int(input())
l = [-1] * N

def get(v1, v2):
    print(v1, flush=True)
    s = input()
    if s=="Male":
        l[v1] = 0
    elif s=="Female":
        l[v1] = 1
    else:
        print(v1)
        return -1

    print(v2, flush=True)
    s = input()
    if s=="Male":
        l[v2] = 0
    elif s=="Female":
        l[v2] = 1
    else:
        print(v2)
        return -1
    
    return l[v2]==l[v1]


left, right = 0, N
while 1:
    mid = (left+right)//2
    v = get(left, mid)
    if v==-1:
        break
    elif v==True and (mid-left)%2:
        right = m
    else:
        left = m

    

### FIXED CODE ###

N = int(input())
l = [-1] * N

print(0)
s = input()
if s=="Male":
    l[0] = 0
elif s=="Female":
    l[0] = 1
else:
    exit(0)

print(N-1)
s = input()
if s=="Male":
    l[N-1] = 0
elif s=="Female":
    l[N-1] = 1
else:
    exit(0)

left, right = 0, N-1
while right-left>1:
    mid = (left+right)//2

    print(mid)
    s = input()
    if s=="Male":
        l[mid] = 0
    elif s=="Female":
        l[mid] = 1
    else:
        exit(0)

    if (l[mid]==l[left] and (mid-left)%2) or (l[mid]!=l[left] and (mid-left)%2==0):
        left, right = left, mid
    else:
        left, right = mid, right
### BUGGY CODE ###

from collections import deque
N = input()
A = []
for i in range(N):
	a = input()
	A.append(a)

A = sorted(A)
res = []
begin = 0
end = len(A) - 1
res = deque()
res.append(A[begin])
res.append(A[end])
begin += 1
end -= 1
for i in range(N - 2):
	l = [abs(res[0] - A[begin]), abs(res[0] - A[end]), abs(res[-1] - A[begin]), abs(res[-1] - A[end])]
	cand = l.index(max(l))
	if cand == 0:
		res.appendleft(A[begin])
		begin += 1
	elif cand == 1:
		res.appendleft(A[end])
		end -= 1
	elif cand == 2:
		res.append(A[begin])
		begin += 1
	elif cand == 3:
		res.append(A[end])
		end -= 1
sum_diff = 0
for i in range(N - 1):
	 sum_diff += abs(res[i] - res[i + 1])
print sum_diff


### FIXED CODE ###

from collections import deque
N = input()
A = [int(input()) for i in range(N)]
coef = [2] * N
coef[0] = 1
coef[-1] = 1
coef1 = [coef[i] if i % 2 == 0 else coef[i] * -1 for i in range(N)]
coef2 = [coef[i] if i % 2 != 0 else coef[i] * -1 for i in range(N)]

A = sorted(A)
coef1 = sorted(coef1)
coef2 = sorted(coef2)
res1 = 0
for i in range(N):
	res1 += A[i] * coef1[i]
res2 = 0
for i in range(N):
	res2 += A[i] * coef2[i]
print max(res1, res2)
### BUGGY CODE ###

n = int(input())
s = input()
q = int(input())
k = list(map(int,input().split()))
k = [[x,i] for i,x in enumerate(k)]
k.sort()
MAX = k[-1][0]
ans = [[0,-1] for i in range(q)]
for i in range(q):
    ans[i][1] = k[i][1]

def search(x):
    ind = x
    m = 0
    c = 0
    count = 0
    for num,i in enumerate(k):
        while ind+count < n and count < i[0]:
            if s[ind+count] == "M":
                m += 1
            elif s[ind+count] == "C":
                c += 1
                ans[num][0]+=m
            count += 1
    
for i in range(n):
    if s[i] == "D":
        search(i)

for i in range(1,q):
    ans[i][0] += ans[i-1][0]
ans.sort(key=lambda x: x[1])
for i,j in ans:
    print(i)

### FIXED CODE ###

from collections import deque
n = int(input())
s = input()
q = int(input())
k = list(map(int,input().split()))

def search(k):
    d = 0
    m = 0
    count = 0
    ans = 0
    q = deque([])
    for i in range(n):
        if s[i] == "D":
            d += 1
        elif s[i] == "M":
            m += 1
            count += d
            q.append(d)
        elif s[i] == "C":
            ans += count
        if i>= k-1:
            if s[i-k+1] == "D":
                d -= 1
                count -= m
            elif s[i-k+1] == "M":
                m -= 1
                
        
    return ans
for i in k:
    print(search(i))
### BUGGY CODE ###

def main():
    h,w=map(int,input().split())
    a=[list(map(int,input().split())) for _ in [0]*h]
    b=[list(map(int,input().split())) for _ in [0]*h]
    c=[[abs(a[i][j]-b[i][j]) for j in range(w)] for i in range(h)]
    t=7160
    dp1=[[False]*(t+1) for _ in [0]*w]
    dp1[0][c[0][0]]=True
    for j in range(1,w):
        v=c[0][j]
        for k in range(t+1):
            if dp1[j-1][k]==True:
                if v+k<=t:
                    dp1[j][v+k]=True
                if abs(v-k)<=0:
                    dp1[j][abs(v-k)]=True
    for i in range(1,h):
        dp2=[[False]*(t+1) for _ in [0]*w]
        for j in range(w):
            v=c[i][j]
            for k in range(t+1):
                if dp1[j][k]==True:
                    if v+k<=t:
                        dp2[j][v+k]=True
                    if abs(v-k)<=t:
                        dp2[j][abs(v-k)]=True
        for j in range(1,w):
            v=c[i][j]
            for k in range(t+1):
                if dp2[j-1][k]==True:
                    if v+k<=t:
                        dp2[j][v+k]=True
                    if abs(v-k)<=t:
                        dp2[j][abs(v-k)]=True  
        dp1=dp2
    for i,j in enumerate(dp1[w-1]):
        if j==True:
            print(i)
            break
main()


### FIXED CODE ###

def main():
    h,w=map(int,input().split())
    a=[list(map(int,input().split())) for _ in [0]*h]
    b=[list(map(int,input().split())) for _ in [0]*h]
    c=[[abs(a[i][j]-b[i][j]) for j in range(w)] for i in range(h)]
    t=7160
    dp1=[[False]*(t+1) for _ in [0]*w]
    dp1[0][c[0][0]]=True
    for j in range(1,w):
        v=c[0][j]
        for k in range(t+1):
            if dp1[j-1][k]==True:
                if v+k<=t:
                    dp1[j][v+k]=True
                if abs(v-k)<=0:
                    dp1[j][abs(v-k)]=True
    for i in range(1,h):
        dp2=[[False]*(t+1) for _ in [0]*w]
        for j in range(w):
            v=c[i][j]
            for k in range(t+1):
                if dp1[j][k]==True:
                    if v+k<=t:
                        dp2[j][v+k]=True
                    if abs(v-k)<=t:
                        dp2[j][abs(v-k)]=True
        for j in range(1,w):
            v=c[i][j]
            for k in range(t+1):
                if dp2[j-1][k]==True:
                    if v+k<=t:
                        dp2[j][v+k]=True
                    if abs(v-k)<=t:
                        dp2[j][abs(v-k)]=True  
        dp1=dp2
    for i,j in enumerate(dp1[w-1]):
        if j==True:
            print(i)
            break
main()
### BUGGY CODE ###

n, k = map(int, input().split())
p_n = list(map(int, input().split()))

s = 0
max_s = 0

for i in range(n - k + 1):
    s = sum(p_n[i:i + k])

    if s > max_s:
        max_s = s

print((max_s + k) / 2)


### FIXED CODE ###

n, k = map(int, input().split())
p = list(map(int, input().split()))

s = sum(p[:k])
max_s = s

for i in range(n - k):
    s = s - p[i] + p[i + k]

    if max_s < s:
        max_s = s

print((max_s + k) / 2)
### BUGGY CODE ###

N = int(input())
S = input()
ans = 0
for i in range(0, N):
    for j in range(i, N):
        if i ==j or S[i] == S[j]:
            continue
        for k in range(j, N):
            if j == k or S[j] == S[k]:
                continue
            elif j-i != k-j and S[i] != S[k]:
                ans += 1
print(ans)

### FIXED CODE ###

N = int(input())
S = input()
ans = S.count("R") * S.count("G") * S.count("B")
for i in range(N):
    for j in range(i + 1, N):
        k = j - i + j
        if k < N:
            if {S[i], S[j], S[k]} == {"R", "G", "B"}:
                ans -= 1
print(ans)
### BUGGY CODE ###

n,m=map(int,input().split())
M,F=10**9+7,[1]
for i in range(m): F+=[-~i*F[i]%M]
c=lambda n,r: F[n]*pow(F[r]*F[n-r],-1,M)
p=lambda n,r: F[n]*pow(F[n-r],-1,M)
print(sum((-1)**k*c(n,k)*p(m,k)*p(m-k,n-k)**2 for k in range(n+1))%M)

### FIXED CODE ###

M=10**9+7
n,m=map(int,input().split())
F=[1]
for i in range(1,m+1): F+=[i*F[-1]%M]
a=0
for k in range(n+1):
  a+=(-1)**k*F[m-k]*pow(F[k]*F[n-k],-1,M)%M
print(a*F[n]*F[m]*pow(F[m-n]**2,-1,M)%M)
### BUGGY CODE ###

def Binit(B,siz):
  while len(B)<siz+1:
    B.append(0)
  while len(B)>siz+1:
    del B[-1]
  for i in range(siz+1):
    B[i]=0
  B.append(siz)

def Badd(B,a,x):
  z=a
  while z<=B[-1]:
    B[z]+=x
    z+=(z&(-z))

def Bsum(B,a):
  r=0
  z=a
  while z>0:
    r+=B[z]
    z-=(z&(-z))
  return r

def Bssum(B,a,b):
  return Bsum(B,max(a,b))-Bsum(B,min(a,b)-1)

N=int(input())
X=[list(map(int,input().split())) for i in range(N)]
X.sort()
for i in range(N):
  X[i][0]=i
D=dict()
Y=sorted([X[i][1] for i in range(N)])
for i in range(N):
  D[Y[i]]=i
for i in range(N):
  X[i][1]=D[X[i][1]]
B1,B2=[],[]
Binit(B1,N+1)
Binit(B2,N+1)
for i in range(N):
  Badd(B2,i+1,1)
mod=998244353
P=N*pow(2,N-1,mod)%mod
Z=[[1,1,1,1],[1,1,1,0],[1,1,0,1],[1,0,1,1],[1,0,0,1],[0,1,1,1],[0,1,1,0]]
A=0
for i in range(N):
  Badd(B2,X[i][1]+1,-1)
  V=[Bsum(B1,X[i][1]+1),Bsum(B2,X[i][1]+1)]
  for j in range(7):
    A=1
    if Z[j][0]:
      A=A*(pow(2,V[0],mod)-1)%mod
    if Z[j][1]:
      A=A*(pow(2,i-V[0],mod)-1)%mod
    if Z[j][2]:
      A=A*(pow(2,V[1],mod)-1)%mod
    if Z[j][3]:
      A=A*(pow(2,N-i-1-V[1],mod)-1)%mod
    P=(P+A)%mod
  Badd(B1,X[i][1]+1,1)
print(P)

### FIXED CODE ###

import sys
S=sys.stdin.readlines()
def Binit(B,siz):
  while len(B)<siz+1:
    B.append(0)
  while len(B)>siz+1:
    del B[-1]
  for i in range(siz+1):
    B[i]=0
  B.append(siz)

def Badd(B,a,x):
  z=a
  while z<=B[-1]:
    B[z]+=x
    z+=(z&(-z))

def Bsum(B,a):
  r=0
  z=a
  while z>0:
    r+=B[z]
    z-=(z&(-z))
  return r

def Bssum(B,a,b):
  return Bsum(B,max(a,b))-Bsum(B,min(a,b)-1)

N=int(S[0])
X=[list(map(int,S[i+1].split())) for i in range(N)]
X.sort()
for i in range(N):
  X[i][0]=i
D=dict()
Y=sorted([X[i][1] for i in range(N)])
for i in range(N):
  D[Y[i]]=i
for i in range(N):
  X[i][1]=D[X[i][1]]
B1,B2=[],[]
Binit(B1,N+1)
Binit(B2,N+1)
for i in range(N):
  Badd(B2,i+1,1)
mod=998244353
P=N*pow(2,N-1,mod)%mod
Z=[[1,1,1,1],[1,1,1,0],[1,1,0,1],[1,0,1,1],[1,0,0,1],[0,1,1,1],[0,1,1,0]]
A=0
for i in range(N):
  Badd(B2,X[i][1]+1,-1)
  V=[Bsum(B1,X[i][1]+1),Bsum(B2,X[i][1]+1)]
  W=[pow(2,V[0],mod)-1,pow(2,i-V[0],mod)-1,pow(2,V[1],mod)-1,pow(2,N-i-1-V[1],mod)-1]
  for j in range(7):
    A=1
    if Z[j][0]:
      A=A*W[0]%mod
    if Z[j][1]:
      A=A*W[1]%mod
    if Z[j][2]:
      A=A*W[2]%mod
    if Z[j][3]:
      A=A*W[3]%mod
    P=(P+A)%mod
  Badd(B1,X[i][1]+1,1)
print(P)
### BUGGY CODE ###

import math
N = int(input())
for n in range(1,N+1):
    r_n = math.floor(math.sqrt(n))
    count = 0
    start = math.floor(r_n/3)
    if(n >= 6):
        for x in range(start,r_n):
            for y in range(1,x+1):
                for z in range(1,y+1):
                    if (x*x + y*y + z*z + x*y + y*z + z*x) == n:
                        if (x == y and y ==z):
                            count+=1
                        elif(x == y or y==z or z == x):
                            count+=3
                        else:
                            count+=6
    print(count)

### FIXED CODE ###

import math
N = int(input())
ans = [0 for _ in range(10050)]
r_n = math.floor(math.sqrt(N))
count = 0
for x in range(1,r_n):
    for y in range(1,r_n):
        for z in range(1,r_n):
            n = x*x + y*y + z*z + x*y + y*z + z*x
            if n < 10050:
                ans[n]+=1
for i in range(N):
    print(ans[i+1])
### BUGGY CODE ###

def is_ok(idx,key,target):
########## wirte criteria here ##########
    if target[idx] > key:
        return True
    return False

def meguru_bisect(key,target):
    left = -1
    right = len(target)
    while (abs(right - left) > 1):
        mid = left + (right - left) // 2
        if is_ok(mid,key,target):
            right = mid
        else:
            left = mid
    return target[right:]

N = int(input())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
C = list(map(int,input().split()))
A.sort()
B.sort()
C.sort()
ans = []
cnt = 0
for i in A:
    ans += meguru_bisect(i,B)
for i in ans:
    cnt += len(meguru_bisect(i,C))

print(cnt)

### FIXED CODE ###

# abc077_c.py
'''
多分あとは、Bで重複がある場合は探索しないで個数かけていくとかにしないといけない。
'''
def is_okC(idx,key,target):
########## wirte criteria here ##########
    if target[idx] > key:
        return True
    return False

def meguru_bisectC(key,target):
    left = -1
    length = len(target)
    right = length
    while (abs(right - left) > 1):
        mid = left + (right - left) // 2
        if is_okC(mid,key,target):
            right = mid
        else:
            left = mid
    return length-right


def is_okA(idx,key,target):
########## wirte criteria here ##########
    if target[idx] >= key:
        return True
    return False

def meguru_bisectA(key,target):
    left = -1
    length = len(target)
    right = length
    while (abs(right - left) > 1):
        mid = left + (right - left) // 2
#        print("mid : " , mid)
        if is_okA(mid,key,target):
            right = mid
        else:
            left = mid
    return right

N = int(input())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
C = list(map(int,input().split()))
A.sort()
C.sort()
a = 0
c = 0
ans = 0
#print(A)
#print(B)
#print(C)
for i in B:
    a = meguru_bisectA(i,A)
#    print(A[:a] )
#    print("i : ",i)
    c = meguru_bisectC(i,C)
#    print(C[c:])
    ans += a*c
#    print()

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

import math
N = int(input())
for i in range(1, N+1):
    ans = 0
    for x in range(1, round(math.sqrt(i))):
        for y in range(1, round(math.sqrt(i))):
            for z in range(1, round(math.sqrt(i))):
                tmp = x**2 + y**2 + z**2 + x*y + y*z + z*x
                if tmp == i:
                    ans += 1
    print(ans)

### FIXED CODE ###

N = int(input())

ans = [0 for _ in range(10**4+50)]

for x in range(1, 105):
    for y in range(1, 105):
        for z in range(1, 105):
            tmp = x**2 + y**2 + z**2 + x*y + y*z + z*x
            if tmp < 10**4+50:
                ans[tmp] += 1

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

n = int(input())
a_list = []

a_list = map(int,input().split())

result = 1
for a in a_list:
    result *= a

if result > 10 ** 18:
    print(-1)
else:
    print(result)


### FIXED CODE ###

import sys

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

if 0 in a:
    print(0)
else:
    cur = 1
    for x in a:
        cur *= x
        if cur > 10 ** 18:
            print(-1)
            sys.exit()
    print(cur)
### 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()))
e=[]
for ai in a:
    for bi in b:
        e.append(ai+bi)
e.sort(reverse=True)
e=e[:k]
ans=[]
for ci in c:
    for ei in e:
        ans.append(ci+ei)
ans.sort(reverse=True)
for i in range(k):
    print(ans[i])

### FIXED CODE ###

x,y,z,k=map(int,input().split())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
c=list(map(int,input().split()))
e=[]
for ai in a:
    for bi in b:
        e.append(ai+bi)
e.sort(reverse=True)
e=e[:k]
ans=[]
for ci in c:
    for ei in e:
        ans.append(ci+ei)
ans.sort(reverse=True)
for i in range(k):
    print(ans[i])
### BUGGY CODE ###

N = int(input())
import numpy as np
li = np.array([0]*N)

for i in range(N):
    li[i:N:i+1]+=1
    li[i]*=(i+1)
    

print(sum(li))


### FIXED CODE ###

N = int(input())

counter = 0
for n in range(1,N+1):
    a = N//n
    counter += a*(a+1)*n//2


print(counter)
### BUGGY CODE ###

#from numba import jit

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


Money=1000
Kabu=0

#@jit
def MoneyWar(Money,Kabu,A,N):
  for i in range(N-1):
    if A[i]<A[i+1]:
      while True:
        if Money-A[i]>=0:
          Money-=A[i]
          Kabu+=1
        else:
          break
    if A[i]>A[i+1]:
      while True:
        if Kabu>0:
          Money+=A[i]
          Kabu-=1
        else:
          break

  if Kabu>0:
    Money+=Kabu*A[-1]
    
  return Money

print(MoneyWar(Money,Kabu,A,N))


### FIXED CODE ###

import math

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

Money=1000
Kabu=0

def MoneyWar(Money,Kabu,A,N):
  for i in range(N-1):
    if A[i]<A[i+1]:
      Kounyu=math.floor(Money/A[i])
      Money-=A[i]*Kounyu
      Kabu+=Kounyu

    if A[i]>A[i+1]:
      Money+=Kabu*A[i]
      Kabu=0

      
  if Kabu>0:
    Money+=Kabu*A[-1]
    
  return Money

print(MoneyWar(Money,Kabu,A,N))
### BUGGY CODE ###

n,k=map(int,input().split())
dp2=list(map(int,input().split()))
    
for ki in range(1,k+1):
    ims=[0]*(n+1)
    for ni in range(n):
        if 0>ni-dp2[ni]:
            ims[0]+=1
        else:
            ims[ni-dp2[ni]]+=1
        if n<ni+dp2[ni]+1:
            ims[n]-=1
        else:
            ims[ni+dp2[ni]+1]-=1

    dp2[0]=ims[0]
    for ni in range(1,n):
        dp2[ni]=dp2[ni-1]+ims[ni]
           
for i in range(n):
    print(dp2[i],end=" ")
print()


### FIXED CODE ###

n,k=map(int,input().split())
dp2=list(map(int,input().split()))
    
k=min(k,41)
for ki in range(1,k+1):
    ims=[0]*(n+1)
    for ni in range(n):
        if 0>ni-dp2[ni]:
            ims[0]+=1
        else:
            ims[ni-dp2[ni]]+=1
        if n<ni+dp2[ni]+1:
            ims[n]-=1
        else:
            ims[ni+dp2[ni]+1]-=1

    dp2[0]=ims[0]
    for ni in range(1,n):
        dp2[ni]=dp2[ni-1]+ims[ni]
    
for i in range(n):
    print(dp2[i],end=" ")
print()
### BUGGY CODE ###

# import bisect
from collections import Counter, deque
# import copy
# from heapq import heappush, heappop, heapify
# from fractions import gcd
# import itertools
# from operator import attrgetter, itemgetter
# import math

import sys

# import numpy as np

ipti = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    n, m = list(map(int, ipti().split()))
    node_next = [set() for _ in range(n)]

    for i in range(m):
        u, v = list(map(int, ipti().split()))
        node_next[u-1].add(v-1)

    s, t = list(map(int, ipti().split()))
    s, t = s - 1, t - 1

    seen = [[0] * n for _ in range(3)]

    que = deque()
    que.append((s, 0, 0))

    while que:
        cnode, cstate, dist = que.popleft()
        seen[cstate][cnode] = 1
        dist += 1
        nstate = (cstate + 1) % 3
        for nnode in node_next[cnode]:
            if seen[nstate][nnode] == 0:
                if nstate == 0 and nnode == t:
                    print(dist // 3)
                    sys.exit()
                else:
                    que.append((nnode, nstate, dist))

    print(-1)


if __name__ == '__main__':
    main()


### FIXED CODE ###

# import bisect
from collections import Counter, deque
# import copy
# from heapq import heappush, heappop, heapify
# from fractions import gcd
# import itertools
# from operator import attrgetter, itemgetter
# import math

import sys

# import numpy as np

ipti = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    n, m = list(map(int, ipti().split()))
    node_next = [set() for _ in range(n)]

    for i in range(m):
        u, v = list(map(int, ipti().split()))
        node_next[u - 1].add(v - 1)

    s, t = list(map(int, ipti().split()))
    s, t = s - 1, t - 1

    dist = [[INF] * n for _ in range(3)]
    dist[0][s] = 0

    que = deque()
    que.append((0, s))

    while que:
        cstate, cnode = que.popleft()
        d = dist[cstate][cnode]
        nstate = (cstate + 1) % 3
        for nnode in node_next[cnode]:
            if dist[nstate][nnode] == INF:
                dist[nstate][nnode] = d + 1
                que.append((nstate, nnode))

    if dist[0][t] != INF:
        print(dist[0][t] // 3)
    else:
        print(-1)


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

import sys
input = sys.stdin.readline
from collections import deque
n,m,s,t = map(int,input().split())
es = deque([])
der = deque([])
for i in range(m):
  u,v,a,b = map(int,input().split())
  es.append((u-1,v-1,a))
  es.append((v-1,u-1,a))
  der.append((u-1,v-1,b))
  der.append((v-1,u-1,b))

es = tuple(es)
der = tuple(der)
def shortest_path(S,g,w,es): 
  d = [10**15] * n #d[i] : s→iの最短距離
  d[S] = 0
  while True:
    update = False
    for p,q,r in es: # e: 辺iについて [from,to,cost]
      if d[p] != 10**15 and d[q] > d[p] + r:
        d[q] = d[p] + r
        update = True       
    if not update:
      break
  return d[g]

chk = [0]*(n+1)
for i in range(n-1,-1,-1):
  chk[i] = max(chk[i+1],10**15-shortest_path(s-1,i,m*2,es)-shortest_path(t-1,i,m*2,der))

chk = tuple(chk)
for i in range(n):
  print(chk[i])

### FIXED CODE ###

import sys
input = sys.stdin.readline
from collections import deque
n,m,s,t = map(int,input().split())
egg = [[] for i in range(n)]
es = [[] for i in range(n)]
for i in range(m):
  u,v,a,b = map(int,input().split())
  es[u-1].append([a,v-1])
  es[v-1].append([a,u-1]) 
  egg[u-1].append([b,v-1])
  egg[v-1].append([b,u-1]) 

es = tuple(es)
egg = tuple(egg)

import heapq
def dijkstra_heap(s,edge):
    #始点sから各頂点への最短距離
    d = [10**18] * n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for e in edge[s]:
        heapq.heappush(edgelist,e)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge[1]]:
            continue
        v = minedge[1]
        d[v] = minedge[0]
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,[e[0]+d[v],e[1]])
    return d

ES = dijkstra_heap(s-1,es)
EDGE = dijkstra_heap(t-1,egg)
cost = 0
chk = [0]*n
for i in range(n-1,-1,-1):
  cost = max(cost,10**15-ES[i]-EDGE[i])
  chk[i] = cost
chk = tuple(chk)
print(*chk, sep="\n")