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

n, q = map(int, input().split())
Qs = list(map(int, input().split()))
Qs = [set([Qs[i]]) for i in range(n)]

#####segfunc######
def segfunc(x,y):
  return x | y

def init(init_val):
  #set_val
  for i in range(n):
    seg[i+num-1]=init_val[i]  
  #built
  for i in range(num-2,-1,-1) :
    seg[i]=segfunc(seg[2*i+1],seg[2*i+2]) 
  
def update(k,x):
  k += num-1
  seg[k] = x
  while k:
    k = (k-1)//2
    seg[k] = segfunc(seg[k*2+1],seg[k*2+2])
  
def query(p,q):
  if q<=p:
    return ide_ele
  p += num-1
  q += num-2
  res=ide_ele
  while q-p>1:
    if p&1 == 0:
      res = segfunc(res,seg[p])
    if q&1 == 1:
      res = segfunc(res,seg[q])
      q -= 1
    p = p//2
    q = (q-1)//2
  if p == q:
    res = segfunc(res,seg[p])
  else:
    res = segfunc(segfunc(res,seg[p]),seg[q])
  return res

#####単位元######
ide_ele = set([])

#num:n以上の最小の2のべき乗
num =2**(n-1).bit_length()
seg=[ide_ele]*2*num
init(Qs)

for _ in range(q):
  l, r = map(int, input().split())
  print(len(query(l-1,r)))

### FIXED CODE ###

from sys import stdin
input = stdin.readline
class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
 
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i
 
n, q = map(int, input().split())
tmp = list(map(int, input().split()))
color = [-1]
for v in tmp:
    color.append(v)
qry = [None]*q
ans = [0]*q
p = 0
for _ in ans:
    l, r = map(int, input().split())
    qry[p] = [l-1, r, p]
    p += 1
qry.sort(key=lambda x: x[1])
dic = {}
last_update_idx = 1
bit = Bit(n)
for l, r, i in qry:
    if last_update_idx < r+1:
        st = set()
        for j in range(last_update_idx, r+1):
            if not color[j] in st and color[j] in dic:
                bit.add(dic[color[j]], -1)
            dic[color[j]] = j
            st.add(color[j])
        for v in st:
            bit.add(dic[v], 1)
        last_update_idx = r+1
    ans[i] = bit.sum(r) - bit.sum(l)
for v in ans:
    print(v)
### BUGGY CODE ###

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

for i in range(n):
    print(a.count(i+1))

### FIXED CODE ###

import collections

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

c = collections.Counter(a)

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

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

if a >0:
    print("Positive")
elif a < 1 and b >-1:
    print("Zero")
else:
    index=a
    count=0
    while index < b+1:
        if index <0:
            count+=1
        index+=1
    if count%2==0:
        print("Positive")
    else:
        print("Negative")

### FIXED CODE ###

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

if a >0:
    print("Positive")
elif a < 1 and b >-1:
    print("Zero")
else:
    if (b-a+1)%2==0:
        print("Positive")
    else:
        print("Negative")
### BUGGY CODE ###


N, M = map(int, input().split())
A = [];
B = [];

for i in range(N):
    Aap, Bap = map(int, input().split())
    A.append(Aap);
    B.append(Bap);

cost = 0;

while(M>0):
    lowestPrice = min(A);
    num = A.index(lowestPrice);
    if (B[num] >= M):
        cost += M*lowestPrice;
        M = 0;
    else:
        cost += B[num]*lowestPrice;
        M -= B[num];
        del A[num];
        del B[num];

print(cost);


### FIXED CODE ###


N, M = map(int, input().split())
shopList = [];

for i in range(N):
    Aap, Bap = map(int, input().split())
    listap = [Aap, Bap]
    shopList.append(listap);

cost = 0;
shopList.sort();

while(M>0):
    lowestPrice = shopList[0][0];
    if (shopList[0][1] >= M):
        cost += M*lowestPrice;
        M = 0;
    else:
        cost += shopList[0][1]*lowestPrice;
        M -= shopList[0][1];
        del shopList[0];

print(cost);
### BUGGY CODE ###

n,m=map(int,input().split())
a=[]
b=[]
C=[1]
D=[1]
s=[0 for i in range(n)]
s[0] = "Yes"
 
for i in range(m):
  c,d=map(int,input().split())
  a.append(c)
  b.append(d)
 
def Next(be):
  A=[a[i] for i in range(len(a)) if a[i] == be or b[i] == be]
  B=[b[i] for i in range(len(b)) if b[i] == be or a[i] == be]
  A=[i for i in A if i != be]
  B=[i for i in B if i != be]
  A.extend(B)
  for i in A:
    if s[i-1] == 0:
      s[i-1] = be
  return A
 
while True:
  if s.count(0)==0:
    break
  for i in C:
    D=Next(i)
    C = D
for i in s:
  print(i)

### FIXED CODE ###

from collections import deque

N, M=map(int,input().split())
a=[]
b=[]
for i in range(M):
  A,B=map(int,input().split())
  a.append(A)
  b.append(B)

graph = [[] for _ in range(N + 1)]
for i in range(M):
  graph[a[i]].append(b[i])
  graph[b[i]].append(a[i])

    # bfs
queue = deque([1])
signposts = [0] * (N + 1)
signposts[1] = 1
while queue:#キューが空になるまで
  u = queue.popleft()
  for v in graph[u]:
    if not signposts[v]:
      signposts[v] = u
      queue.append(v)
 
if all(signposts[2:]):
  print("Yes")
  print("\n".join(map(str, signposts[2:])))
else:
  print("No")
### BUGGY CODE ###

import bisect
N = int(input())
A = sorted(map(int, input().split()))
B = list(map(int, input().split()))
C = sorted(map(int, input().split()))
print(sum(len(A[:bisect.bisect_left(A, b)]) * len(C[bisect.bisect(C, b):]) for b in B))


### FIXED CODE ###

import bisect
N = int(input())
A = sorted(map(int, input().split()))
B = map(int, input().split())
C = sorted(map(int, input().split()))
print(sum(bisect.bisect_left(A, b) * (N - bisect.bisect(C, b)) for b in B))
### BUGGY CODE ###

import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

n = int(input())
s = input()
# combinationの準備
md = 10 ** 9 + 7
n_max = 3005
fac = [1]
inv = [1] * (n_max + 1)
k_fac_inv = 1
for i in range(1, n_max + 1):
    k_fac_inv = k_fac_inv * i % md
    fac.append(k_fac_inv)
k_fac_inv = pow(k_fac_inv, md - 2, md)
for i in range(n_max, 1, -1):
    inv[i] = k_fac_inv
    k_fac_inv = k_fac_inv * i % md

def com(com_n, com_r):
    return fac[com_n] * inv[com_r] * inv[com_n - com_r] % md

def way(s):
    sn = len(s)
    if sn <= 1: return 1
    if s in memo: return memo[s]
    res = 0
    if s[0] == "<": res += way(s[1:])
    if s[-1] == ">": res += way(s[:-1])
    for i in range(sn - 1):
        if s[i] == ">" and s[i + 1] == "<":
            res += way(s[:i]) * way(s[i + 2:]) * com(sn, i + 1)
    res %= md
    memo[s] = res
    return res
memo = {}

def main():
    print(way(s))

main()


### FIXED CODE ###

md = 10 ** 9 + 7
n = int(input())
s = input()
dp = [1] * n
for i in range(n - 1):
    if s[i] == "<":
        for dpi in range(1, n - i - 1):
            dp[dpi] = (dp[dpi] + dp[dpi - 1]) % md
        dp = dp[:-1]
    else:
        for dpi in range(n - i - 2, 0, -1):
            dp[dpi] = (dp[dpi] + dp[dpi + 1]) % md
        dp = dp[1:]
print(dp[0])
### BUGGY CODE ###

from collections import deque

import numpy as np
import sys
#input = sys.stdin.readline

sys.setrecursionlimit(5000)

def bfs(point, field, target):
    visited = []
    que = deque()
    que.append((point, 1))
    
    while True:
        v, depth = que.popleft()
        visited.append(v)
        for a in [(v[0]-1, v[1]), (v[0]+1, v[1]), (v[0], v[1]-1), (v[0], v[1]+1)]:
            if field[a[0]][a[1]] == 0 and a not in visited:
                if a == target:
                    return depth + 1
                else:
                    que.append((a, depth+1))
        if len(que) == 0:
            return 0

def main():
    H, W = list(map(int, input().split()))
    target = (H, W)
    field = [[-1] * (W+2)]
    number_of_whites = 0
    for _ in range(H):
        s = input()
        number_of_whites += s.count('.')
        field.append([-1] + [0 if c=='.' else -1 for c in s] + [-1])
    field += [[-1] * (W+2)]

    shortest_path = bfs((1, 1), field, target)
    if shortest_path > 0:
        print(number_of_whites - shortest_path)
    else:
        print(-1)
        
if __name__ == '__main__':
    main()

### FIXED CODE ###

H, W = list(map(int, input().split()))
M = [[-1]*(W+2)]
ans = 0
for _ in range(H):
    s = input()
    ans += s.count('.')
    M.append([-1]+[0 if c=='.' else -1 for c in s]+[-1])
M += [[-1]*(W+2)]

queue = [(1,1)]
M[1][1] = 1
dr = [(+1,0),(-1,0),(0,+1),(0,-1)]
turn = 1
while len(queue)>0:
    turn += 1
    queue_new = []
    for qx, qy in queue:
        for dx, dy in dr:
            x, y = qx+dx, qy+dy
            if M[y][x]==0:
                M[y][x] = turn
                queue_new.append((x,y))
    queue = queue_new

print(ans-M[H][W] if M[H][W]>0 else -1)
### BUGGY CODE ###

from collections import defaultdict
n = int(input())
a = list(map(int,input().split()))
d = defaultdict(int)
for ai in a:
   for i in range(1,int(ai**0.5)+1):
    if ai%i==0:
        d[i] += 1
        if i!=ai//i:
            d[ai//i] += 1

sd=sorted(d.items(),key=lambda x:x[0],reverse=True)
for k,v in sd:
    if v==n or v==n-1:
        print(k)
        break

### FIXED CODE ###

def gcd(a,b):
    while a%b!=0:
        a,b = b,a%b
    return b
n = int(input())
a = list(map(int,input().split()))
right,left = [0]*n,[0]*n
left[0],right[n-1] = a[0],a[n-1]
for i in range(1,n):
    left[i] = gcd(left[i-1],a[i])
for i in range(n-2,-1,-1):
    right[i] = gcd(right[i+1],a[i])
ans = max(left[-2],right[1])
for i in range(1,n-1):
    ans = max(ans,gcd(right[i+1],left[i-1]))
print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**9)
def maxBy(f, x, y):
    if f(x) > f(y):
        return x
    else:
        return y


table = {("", ""): ""}


def lcs(xs, ys):
    if (xs, ys) in table:
        return table[(xs, ys)]

    ret = ""
    if xs == "" or ys == "":
        ret = ""
    elif xs[-1] == ys[-1]:
        ret = lcs(xs[:-1], ys[:-1]) + xs[-1]
    else:
        ret = maxBy(len,
                    lcs(xs[:-1], ys),
                    lcs(xs, ys[:-1]))
    table[(xs, ys)] = ret
    return ret


s = input()
t = input()

c = lcs(s, t)
print(c)


### FIXED CODE ###

def lcs(x, y):
    m = len(x)
    n = len(y)

    c = [[0 for _ in range(n + 1)] for _ in range(m + 1)]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if x[i - 1] == y[j - 1]:
                c[i][j] = c[i - 1][j - 1] + 1
            else:
                c[i][j] = max(c[i - 1][j], c[i][j - 1])

    lcs_str = ''
    i, j = m, n
    while i > 0 and j > 0:
        if x[i-1] == y[j-1]:
            lcs_str += x[i-1]
            i -= 1
            j -= 1
        else:
            if c[i][j] == c[i-1][j]:
                i -= 1
            else:
                j -= 1

    return lcs_str[::-1]


s = input()
t = input()
print(lcs(s, t))
### BUGGY CODE ###

# coding: utf-8

# 標準入力 <int>
N = int(input())

# 標準入力<str>
S = input()

ans = 0

for i in range(N - 2):

  S2 = []
  for j in range(N - i - 2):
    rgb = "RGB"
    if S[i] == S[i + j + 1]:
      continue
    rgb = rgb.replace(S[i], "")
    rgb = rgb.replace(S[i + j + 1], "")
    if i + ((j + 1) * 2) < N:
      S2 = S[i + j + 2:i + (2 * j) + 2] + S[i + (2 * j) + 3:]
    else:
      S2 = S[i + j + 2:]
    #print(rgb)
    ans += S2.count(rgb)

print(ans)


### FIXED CODE ###

# coding: utf-8

# 標準入力 <int>
N = int(input())

# 標準入力<str>
S = input()

R = S.count("R")
G = S.count("G")
B = S.count("B")

cnt = 0

for i in range(N - 2):
  for j in range(i + 1, N - 1):
    k = i + ((j - i) * 2)
    if k < N:
      if S[i] != S[j] and S[j] != S[k] and S[k] != S[i]:
        cnt += 1

print(R * G * B - cnt)
### BUGGY CODE ###

from bisect import bisect_left, bisect_right

def readinput():
    n,m=list(map(int,input().split()))
    a=list(map(int,input().split()))
    b=[]
    c=[]
    for _ in range(m):
        bb,cc=list(map(int,input().split()))
        b.append(bb)
        c.append(cc)
    return n,m,a,b,c

def main(n,m,a,b,c):
    a.sort()
    for i in range(m):
        #print(a)
        bi=b[i]
        ci=c[i]
        j=bisect_left(a,ci)-1
        if j<0:
            continue
        if j>bi-1:
            save=a[bi:j+1]
            l=j-bi+1
            r=j
            a[l:r+1]=[ci]*(r-l+1)
            a[0:l]=save
        else:
            l=0
            r=j
            a[l:r+1]=[ci]*(r-l+1)

    sum=0
    for i in range(n):
        sum+=a[i]
    
    return sum

if __name__=='__main__':
    n,m,a,b,c=readinput()
    ans=main(n,m,a,b,c)
    print(ans)


### FIXED CODE ###

from bisect import bisect_left, bisect_right

def readinput():
    n,m=list(map(int,input().split()))
    a=list(map(int,input().split()))
    b=[]
    c=[]
    for _ in range(m):
        bb,cc=list(map(int,input().split()))
        b.append(bb)
        c.append(cc)
    return n,m,a,b,c

def main(n,m,a,b,c):
    a.sort()
    for i in range(m):
        #print(a)
        bi=b[i]
        ci=c[i]
        j=bisect_left(a,ci)-1
        if j<0:
            continue
        if j>bi-1:
            save=a[bi:j+1]
            l=j-bi+1
            r=j
            a[l:r+1]=[ci]*(r-l+1)
            a[0:l]=save
        else:
            l=0
            r=j
            a[l:r+1]=[ci]*(r-l+1)

    sum=0
    for i in range(n):
        sum+=a[i]
    
    return sum

def main2(n,m,a,b,c):
    all=[]
    for i in range(n):
        all.append((a[i],1))
    for i in range(m):
        all.append((c[i],b[i]))
    all.sort(reverse=True, key=lambda x:x[0])
    #print(all)
    count=n
    sum=0
    i=0
    while(count>0):
        ni=all[i][1]
        if ni<=count:
            sum+=all[i][0]*ni
            count-=ni
        else:
            sum+=all[i][0]*count
            count=0
        i+=1
        #print(sum,count)
    return sum

if __name__=='__main__':
    n,m,a,b,c=readinput()
    ans=main2(n,m,a,b,c)
    print(ans)
### BUGGY CODE ###

val = list(map(int, input().strip().split()))
n = val[0]
m = val[1]
a = []

for i in range(m):
    a.append(int(input().strip()))

pastpast_result = 0
past_result = 1
result = 0

for i in range(n):
    result = 0
    if i not in a:
        result += past_result
    if i-1 not in a:
        result += pastpast_result

    if result > 1000000007:
        result = result % 1000000007
    
    pastpast_result = past_result
    past_result = result

print(result % 1000000007)

### FIXED CODE ###

import bisect

def find_bisect(a, x):
    i = bisect.bisect_left(a, x)
    if i != len(a) and a[i] == x:
        return True
    return False

val = list(map(int, input().strip().split()))
n = val[0]
m = val[1]
a = []

for i in range(m):
    a.append(int(input().strip()))

pastpast_result = 0
past_result = 1
result = 0

for i in range(n):
    result = 0
    if not find_bisect(a, i):
        result += past_result
    if not find_bisect(a, i-1):
        result += pastpast_result

    if result > 1000000007:
        result = result % 1000000007
    
    if result == 0:
        break
    
    pastpast_result = past_result
    past_result = result

print(result % 1000000007)
### BUGGY CODE ###

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

for i in range(N):
    print(A.count(i+1))

### FIXED CODE ###

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

res = [0]*N

for i in range(N-1):
    res[A[i]-1] += 1

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

n = int(input())

def gcd(a,b):
    while b:
        a, b = b, a % b
    return a

ans = 0
if n == 1:
    ans = 1
else:
    for i in range(n):
        i = i + 1
        #ans = ans + i #(i,i,i)
        for j in range(n):
            j = j + 1
            for k in range(n):
                k = k + 1
                ij = gcd(i,j)
                ans = ans + gcd(ij,k)

print(ans)

### FIXED CODE ###

n = int(input())

def gcd(a,b):
    while b:
        a, b = b, a % b
    return a

ans = 0
if n == 1:
    ans = 1
else:
    for i in range(n):
        i = i + 1
        for j in range(n):
            j = j + 1
            for k in range(n):
                k = k + 1
                ij = gcd(i,j)
                ans = ans + gcd(ij,k)

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

import numpy as np

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

if A[0] != 0:
    print(0)
    exit()
if A.count(0) != 1:
    print(0)
    exit()

k = max(A)

R = [1]
result = 1


for i in range(k):
    R.append(A.count(i + 1))

for j in range(k):
    if R[j + 1] % 2 == 0:
        result *= ((R[j] ** 2) ** (R[j + 1] // 2))
    else:
        result *= R[j] * ((R[j] ** 2) ** (R[j + 1] // 2))
        
    result %= 998244353

    if result == 0:
        print(0)
        exit()

print(result % 998244353)


### FIXED CODE ###

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

def pow_k(x, n):
    """
    O(log n)
    """
    if n == 0:
        return 1

    K = 1
    while n > 1:
        if n % 2 != 0:
            K *= x % 998244353
        x *= x % 998244353
        n //= 2

    return K * x % 998244353


R = [0] * (k + 1)
result = 1
for i in A:
    R[i] += 1

if A[0] != 0 or R[0] != 1:
    print(0)
    exit()

for j in range(k):
    result *= pow_k(R[j], R[j + 1])

    if result == 0:
        print(0)
        exit()

print(result % 998244353)
### BUGGY CODE ###

N = int(input())
S = input()
cnt = 0
for k in range(N):
    for j in range(k):
        for i in range(j) :
            if j - i != k - j:
                if S[k] != S[j] and S[j] != S[i] and S[k] != S[i]:
                    cnt = cnt + 1
                else:
                    cnt = cnt + 0

print(cnt)


### FIXED CODE ###

n = int(input())
s = input()

r_cnt = s.count('R')
g_cnt = s.count('G') 
b_cnt = s.count('B')

ans = r_cnt * g_cnt * b_cnt
cnt = 0

for i in range(n):
    for d in range(n):
        j = i + d
        k = j + d
        if k >= n:
            break
        if s[i] != s[j] and s[j] != s[k] and s[k] != s[i]:
            cnt += 1

ans = ans - cnt
print(ans)
### BUGGY CODE ###

s = input().strip()

DIV = 10**9 + 7
new = list(range(13))
old = None

c = s[-1]
if c == '?':
    old = [int(t < 10) for t in range(13)]
else:
    c = int(c)
    old = [int(t == c) for t in range(13)]

digit = 10
for i, c in enumerate(reversed(s[:-1])):
    for j in range(13):
        new[j] = 0
    if c == '?':
        for m in range(10):
            for mod, cnt in enumerate(old):
                shifted = (mod + m * digit) % 13
                new[shifted] += cnt
    else:
        c = int(c)
        for mod, cnt in enumerate(old):
            shifted = (mod + c * digit) % 13
            new[shifted] += cnt
    for j in range(13):
        new[j] %= DIV
    new, old = old, new
    digit = (digit * 10) % 13

print(old[5])

### FIXED CODE ###

s = input().strip()

DIV = 10**9 + 7
new = list(range(13))
old = None

c = s[-1]
if c == '?':
    old = [int(t < 10) for t in range(13)]
else:
    c = int(c)
    old = [int(t == c) for t in range(13)]

digit = 10
for i, c in enumerate(reversed(s[:-1])):
    for j in range(13):
        new[j] = 0
    if c == '?':
        for m in range(10):
            for mod, cnt in enumerate(old):
                shifted = (mod + m * digit) % 13
                new[shifted] += cnt
    else:
        c = int(c)
        for mod, cnt in enumerate(old):
            shifted = (mod + c * digit) % 13
            new[shifted] += cnt
    for j in range(13):
        new[j] %= DIV
    new, old = old, new
    digit = (digit * 10) % 13

print(old[5])
### BUGGY CODE ###

mod = 10**9+7
N,K = map(int,input().split())
M = int(N**0.5)
dp = [[0]*M for _ in range(K+1)]
dp1 = [[0]*M for _ in range(K+1)]
dp2 = [[0]*M for _ in range(K+1)]

dp[0][0] = 1
dp1[0][0] = 1
dp2[0][0] = N
for m in range(1,M):
    dp[0][m] = 1
    dp1[0][m] = dp1[0][m-1]+dp[0][m]
    dp2[0][m] += dp2[0][m-1]+N//(m+1)*dp[0][m]

dp[1][0] = N
dp1[1][0] = N
dp2[1][0] = N**2
for m in range(1,M):
    dp[1][m] = N//(m+1)
    dp1[1][m] = dp1[1][m-1]+dp[1][m]
    dp2[1][m] += dp2[1][m-1]+N//(m+1)*dp[1][m]


for k in range(1,K):
    for m in range(M):
        dp[k+1][m] = dp1[k][M-1]+N//(m+1)*dp1[k-1][m]+dp2[k-1][M-1]-dp2[k-1][m]-M*dp1[k-1][M-1]
        dp[k+1][m] %= mod
        dp1[k+1][m] = dp1[k+1][m-1]+dp[k+1][m]
        dp1[k+1][m] %= mod
        dp2[k+1][m] = dp2[k+1][m-1]+N//(m+1)*dp[k+1][m]
        dp2[k+1][m] %= mod

print(dp[K][0])


### FIXED CODE ###

from bisect import bisect
mod = 10**9+7
N,K = map(int,input().split())

c = []
for i in range(1,int(N**0.5)+1):
    c.append(i)
    c.append(int(N/i))
c = list(set(c))
c.sort()

k = []
for i in c:
    if int(N/i) != int(N/(i+1)):
        k.append(i)

dp = [[0]*len(k) for _ in range(K)]
for i in range(len(k)):
    dp[0][i]=k[i]

inv = [0]*(len(k)-1)
for i in range(len(k)-1):
    inv[i] = pow(k[i+1]-k[i],mod-2,mod)

index = [0]*len(k)
for i in range(len(k)):
    m = int(N/(k[i]+1))
    index[i] = bisect(k,m)

for i in range(K-1):
    dp[i+1][0] = dp[i][-1]
    for j in range(len(k)-1):
        m = int(N/(k[j]+1))
        l = index[j]
        S = dp[i][l-1]+(dp[i][l]-dp[i][l-1])*(m-k[l-1])*inv[l-1]
        dp[i+1][j+1] = dp[i+1][j]+(k[j+1]-k[j])*S
        dp[i+1][j+1] %= mod

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

from queue import Queue

n , q = map(int, input().split())
lab = []
points = [0]*n
for i in range(n-1):
    lab.append(list(map(int, input().split())))
lpx = []
for i in range(q):
    lpx.append(list(map(int, input().split())))

for i in lpx:
    childs = Queue()
    inc = []
    parent = i[0]
    childs.put(parent)
    while childs.qsize() > 0:
        a = childs.get()
        inc.append(a)
        for k in lab:
            if k[0] == a:
                childs.put(k[1])
    setinc = set(inc)

    for j in list(setinc):
        points[j-1] += i[1]
print(' '.join(map(str, points)))

### FIXED CODE ###

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

N,Q = map(int,input().split())
aLst = [[int(x) for x in input().split()] for _ in range(N-1)]
pLst = [[int(x) for x in input().split()] for _ in range(Q)]

tmpLst = [[] for _ in range(N+1)]
for i, j in aLst:
    tmpLst[i].append(j)
    tmpLst[j].append(i)

ansLst = [0] * (N + 1)
for i,j in pLst:
    ansLst[i] += j

def dfs(v, p):
    for i in tmpLst[v]:
        if i == p:
            continue
        ansLst[i] += ansLst[v]
        dfs(i, v)


dfs(1, 0)

ans = ' '.join(map(str, ansLst[1:]))
print(ans)
### BUGGY CODE ###

from bisect import bisect_right, bisect_left

N, M, *A = map(int, open(0).read().split())
A.sort()


def calc(t):
    cnt = 0
    for ai in A:
        cnt += N - bisect_left(A, t - ai)
    if M <= cnt:
        return True
    else:
        return False


def solve():
    left, right = 0, 2 * 10**5+1
    while 1 < right - left:
        mid = (left + right) //2
        if calc(mid):
            left = mid
        else:
            right = mid
    
    ans = 0
    add_cnt = 0
    for ai in A:
        index = bisect_left(A, left - ai)
        add_cnt += N - index
        for aj in A[index:]:
            ans += ai + aj
    ans -= left * (add_cnt - M)
    print(ans)


if __name__ == '__main__':
    solve()


### FIXED CODE ###

from bisect import bisect_left

N, M, *A = map(int, open(0).read().split())
A.sort()


def calc(t):
    cnt = 0
    for ai in A:
        cnt += N - bisect_left(A, t - ai)
    if M <= cnt:
        return True
    else:
        return False


def solve():
    left, right = 0, 2 * 10 ** 5 + 1
    while 1 < right - left:
        mid = (left + right) // 2
        if calc(mid):
            left = mid
        else:
            right = mid
    
    sum_A = [0] * N
    sum_A[-1] = A[-1]
    for i in range(N - 2, -1, -1):
        sum_A[i] = sum_A[i + 1] + A[i]
    
    ans = 0
    add_cnt = 0
    for ai in A:
        index = bisect_left(A, left - ai)
        if index == N:
            continue
        add_cnt += N - index
        ans += (N - index) * ai + sum_A[index]
    ans -= left * (add_cnt - M)
    print(ans)


if __name__ == '__main__':
    solve()