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

N,W = map(int,input().split())
wv = []
for i in range(N):
  wv.append(list(map(int,input().split())))
dp = []
for i in range(N+1):
  dp.append([0 for _ in range(W+1)])
for i in range(N-1,-1,-1):
  for j in range(0,W+1):
    if j < wv[i][0]:
      dp[i][j] = dp[i+1][j]
    else:
      dp[i][j] = max(dp[i+1][j],dp[i+1][j-wv[i][0]]+wv[i][1])
print(dp[0][W])

### FIXED CODE ###

N,W = map(int,input().split())
wv = []
for i in range(N):
  wv.append(list(map(int,input().split())))
dp = []
for i in range(N+1):
  dp.append([0 for _ in range(W+1)])
for i in range(N-1,-1,-1):
  for j in range(0,W+1):
    if j < wv[i][0]:
      dp[i][j] = dp[i+1][j]
    else:
      dp[i][j] = max(dp[i+1][j],dp[i+1][j-wv[i][0]]+wv[i][1])
print(dp[0][W])
### BUGGY CODE ###

import itertools
while 1:
	n = input()
	if n == 0: break
	s = sorted(map(int,raw_input().split()))
	sm1 = ans = sum(s)
	for i in range(1,n-1):
		for party in sorted(itertools.combinations(s,i), key = lambda x:sum(x)):
			sm2 = sm1 - 2*sum(party)
			if sm2 < -ans: break
			ans = min(ans,abs(sm2))
			if ans == 0: break
	print ans

### FIXED CODE ###

def S(i,x,y):
	if 2*x >= A: return 2*x-A
	if 2*y >= A: return 2*y-A
	return min(S(i+1,x+a[i],y),S(i+1,x,y+a[i]))
while 1:
	n = input()
	if n == 0: break
	a = sorted(map(int,raw_input().split()))[::-1]
	A = sum(a)
	print S(1,a[0],0)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
n, m = map(int, input().split())
ss = input().split()
ts = input().split()
d = [[1] * (m+1) for _ in range(n+1)]
for i in range(n):
    for j in range(m):
        d[i+1][j+1] = d[i][j+1] + d[i+1][j] - (0 if ss[i] == ts[j] else d[i][j])
print(d[n][m]%(10**9+7))


### FIXED CODE ###

n, m = map(int, input().split())
ss = input().split()
ts = input().split()
d = [[1] * (m+1) for _ in range(n+1)]
for i in range(n):
    for j in range(m):
        d[i+1][j+1] = (d[i][j+1] + d[i+1][j] - (ss[i] != ts[j])*d[i][j]) % (10**9+7)
print(d[n][m])
### BUGGY CODE ###

import numpy as np


def DP(i, X, w, v):
    global memo
    if (X < 0):
        return -10 ** 9
    if (memo[i, X] != -10 ** 9):
        return memo[i, X]
    result = max(DP(i + 1, X, w, v),
                 DP(i + 1, X - w[i], w, v) + v[i])
    memo[i, X] = result
    return result


N, W = map(int, input().split())
w = [0] * N
v = [0] * N
for i in range(N):
    w[i], v[i] = map(int, input().split())
MINUS_INF = -10 ** 9
memo = np.full((N + 1, W + 1), MINUS_INF, dtype='int64')
memo[N, :] = 0
answer = DP(0, W, w, v)
print(answer)


### FIXED CODE ###

import numpy as np
import sys


def main():
    input = sys.stdin.readline
    n, W = map(int, input().split())
    w, v = [0] * n, [0] * n
    for i in range(n):
        w[i], v[i] = map(int, input().split())
    ndp = np.zeros(W + 1, dtype=np.int64)
    for w, v in zip(w, v):
        np.maximum(ndp[:-w] + v, ndp[w:], out=ndp[w:])
    print(ndp[-1])


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


def keisan(a):
    a.sort(reverse = True)
    ans = 0
    for i in range(0,n,2):
        if a.count(a[i]) >= 4:
            ans = a[i]*a[i]
            break
        elif a.count(a[i]) >=2:
            
            for j in range(i+a.count(a[i]),n,2):
                if a.count(a[j]) >=2:
                    ans = a[i]*a[j]
                    break
            break
    print(ans)

n = int(input())
in_=list(map(int,input().split()))
keisan(in_)

### FIXED CODE ###

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

a.sort(reverse = True)
ans = 0
b = a.copy()
b = list(set(b))
b.sort(reverse = True)
c = [0]*len(b)
j = 0
c[j] = 1
for i in range(1,n):
    if a[i-1] == a[i]:
        c[j] +=1
    else:
        j+=1
        c[j] +=1
for i in range(len(b)):
    if c[i] >= 4:    
        
        ans = b[i]*b[i]
        break
    elif c[i] >= 2:
        for j in range(i+1,len(b)):
            if c[j] >= 2:
                ans = b[i]*b[j]
                break
        break
print(ans)
### BUGGY CODE ###

n, w = map(int, input().split())
import numpy as np
dp = np.zeros((n+1, w+1))
for i in list(range(n+1))[1:]:
    wi, vi = map(int, input().split())
    dp[i] = [max(dp[i-1][j], dp[i-1][j-wi]+vi) if j >= wi else dp[i-1][j] for j in range(w+1)]
print(int(max(dp[-1])))

### FIXED CODE ###

n, w = map(int, input().split())
import numpy as np
dp = np.zeros(w+1, np.int64)
for i in range(n):
    wi, vi = map(int, input().split())
    np.maximum(dp[:-wi]+vi, dp[wi:], out=dp[wi:])
print(max(dp))
### BUGGY CODE ###

#!/usr/bin/env python3
INF = float("inf")
import sys
input = sys.stdin.readline
from collections import*

def bfs():
    q = deque([(sx, sy)])
    dist = [[INF]*W for _ in range(H)]
    dist[sx][sy] = 0
    
    while q:
        x, y = q.popleft()
        if (x, y) == (gx, gy): return dist[gx][gy]
        for nx, ny in [(x-1, y), (x+1, y), (x, y-1), (x, y+1)]:
            if 0<=nx<H and 0<=ny<W and dist[nx][ny] > dist[x][y]:
                if c[nx][ny] == ".":
                    dist[nx][ny] = dist[x][y]
                    q.appendleft((nx, ny))
        for nx, ny in [(x-1, y-1), (x-1, y+1), (x+1, y+1), (x+1, y-1)]:
            if 0<=nx<H and 0<=ny<W and dist[nx][ny] > dist[x][y]:
                if c[nx][ny] == ".":
                    dist[nx][ny] = dist[x][y] + 1
                    q.append((nx, ny))
        for nx in range(x-2, x+3):
            for ny in [y+2, y-2]:
                if 0<=nx<H and 0<=ny<W and dist[nx][ny] > dist[x][y]:
                    if c[nx][ny] == ".":
                        dist[nx][ny] = dist[x][y] + 1
                        q.append((nx, ny))
        for nx in [x+2, x-2]:
            for ny in range(y-1, y+2):
                if 0<=nx<H and 0<=ny<W and dist[nx][ny] > dist[x][y]:
                    if c[nx][ny] == ".":
                        dist[nx][ny] = dist[x][y] + 1
                        q.append((nx, ny))            
    return dist[gx][gy]

H, W = map(int, input().split())

cx, cy = map(int, input().split()); sx, sy = cx - 1, cy - 1
dx, dy = map(int, input().split()); gx, gy = dx - 1, dy - 1
c = [input()[:-1] for _ in range(H)]
ans = bfs()
print(ans if ans != INF else -1)


### FIXED CODE ###

#!/usr/bin/env python3
INF = 10**7
import sys
input = sys.stdin.readline
from collections import*

def bfs():
    q = deque([(sx, sy)])
    dist = [[INF] * W for _ in range(H)]
    dist[sx][sy] = 0
    
    while q:
        x, y = q.popleft()
        b = dist[x][y]
        if (x, y) == (gx, gy):
            return b
        for dx, dy in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
            nx, ny = x + dx, y + dy
            if 0 <= nx < H and 0 <= ny < W and dist[nx][ny] > b and c[nx][ny] == ".":
                dist[nx][ny] = b
                q.appendleft((nx, ny))
        B = b + 1
        for dx in range(-2, 3):
            for dy in range(-2, 3):
                nx, ny = x + dx, y + dy
                if 0 <= nx < H and 0 <= ny < W and dist[nx][ny] > B and c[nx][ny] == ".":
                    dist[nx][ny] = B
                    q.append((nx, ny)) 
    return -1

H, W = map(int, input().split())
cx, cy = map(int, input().split())
dx, dy = map(int, input().split())
sx, sy, gx, gy = cx - 1, cy - 1, dx - 1, dy - 1
c = [input()[:-1] for _ in range(H)]
ans = bfs()
print(ans if ans != INF else -1)
### BUGGY CODE ###

n = int(input())
L = list(map(int,input().split()))
for i in range(n):
    L[i] = L[i]-(i+1)
sum1 = 0
b = max(abs(max(L)),abs(min(L)))
i = -b
min1 = 10**10
while i<=b:
    sum1 =0
    for j in range(n):
        sum1 += abs(L[j]-i)
    min1 = min(min1,sum1)
    i +=1
print(min1)

### FIXED CODE ###

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

for i in range(n):
    li[i] -= i

import statistics
import math
a = math.floor(statistics.median(li))
b = math.ceil(statistics.median(li))

num_a,num_b = 0,0
for i in range(n):
    num_a += abs(li[i]-(a))
    num_b += abs(li[i]-(b))
print(min(num_a,num_b))
### BUGGY CODE ###

def prepare(n):
    global MOD
    modFacts = [0] * (n + 1)
    modFacts[0] = 1
    for i in range(n):
        modFacts[i + 1] = (modFacts[i] * (i + 1)) % MOD

    invs = [1] * (n + 1)
    invs[n] = pow(modFacts[n], MOD - 2, MOD)
    for i in range(n, 1, -1):
        invs[i - 1] = (invs[i] * i) % MOD

    return modFacts, invs


MOD = 10 ** 9 + 7
K = int(input())
S = input()
L = len(S)
modFacts, invs = prepare(K + L)

pow25 = [1] * max(L + 1, K + 1)
pow26 = [1] * max(L + 1, K + 1)
for i in range(max(L, K)):
    pow25[i + 1] = (pow25[i] * 25) % MOD
    pow26[i + 1] = (pow26[i] * 26) % MOD

ans = 0
for n in range(L, L + K + 1):
    nonSi = (pow25[n - L] * pow26[L + K - n]) % MOD
    Si = (modFacts[n - 1] * invs[L - 1] * invs[n - 1 - (L - 1)]) % MOD
    ans += nonSi * Si
    ans %= MOD

print(ans)


### FIXED CODE ###

def prepare(n):
    global MOD
    modFacts = [0] * (n + 1)
    modFacts[0] = 1
    for i in range(n):
        modFacts[i + 1] = (modFacts[i] * (i + 1)) % MOD

    invs = [1] * (n + 1)
    invs[n] = pow(modFacts[n], MOD - 2, MOD)
    for i in range(n, 1, -1):
        invs[i - 1] = (invs[i] * i) % MOD

    return modFacts, invs


MOD = 10 ** 9 + 7
K = int(input())
S = input()
L = len(S)
modFacts, invs = prepare(K + L)

ans = 0
for n in range(L, L + K + 1):
    nonSi = (pow(25, n - L, MOD) * pow(26, L + K - n, MOD)) % MOD
    Si = (modFacts[n - 1] * invs[L - 1] * invs[n - 1 - (L - 1)]) % MOD
    ans += nonSi * Si
    ans %= MOD

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

import math

class SegmentTree(object):
    __slots__ = ["elem_size", "tree", "default", "op"]

    def __init__(self, a: list, default: int, op):
        real_size = len(a)
        self.elem_size = elem_size = 1 << math.ceil(math.log2(real_size))
        self.tree = tree = [default] * (elem_size * 2)
        tree[elem_size:elem_size+real_size] = a
        self.default = default
        self.op = op

        for i in range(elem_size - 1, 0, -1):
            tree[i] = op(tree[i<<1], tree[(i<<1)+1])

    def get_value(self, x: int, y: int) -> int:
        l, r = x + self.elem_size, y + self.elem_size
        tree, result, op = self.tree, self.default, self.op
        while l < r:
            if l & 1:
                result = op(tree[l], result)
                l += 1
            if r & 1:
                r -= 1
                result = op(tree[r], result)
            l, r = l >> 1, r >> 1

        return result

    def set_value(self, i: int, value: int) -> None:
        k = self.elem_size + i
        self.tree[k] = value
        self.update(k)

    def update(self, i: int) -> None:
        op, tree = self.op, self.tree
        while i > 1:
            i >>= 1
            tree[i] = op(tree[i<<1], tree[(i<<1) + 1])

if __name__ == "__main__":
    import sys
    from bisect import bisect_right

    N, d = map(int, sys.stdin.readline().split())
    b_l, x_l, y_l = zip(*sorted([(b, x, y) for l in sys.stdin.readlines() for x, y, b in (map(int, l.split()),)]))
    inf, minf = float("inf"), float("-inf")
    x_min = SegmentTree(x_l, inf, min)
    x_max = SegmentTree(x_l, minf, max)
    y_min = SegmentTree(y_l, inf, min)
    y_max = SegmentTree(y_l, minf, max)

    ans = 0
    for l, (b, _) in enumerate(zip(b_l, [-1]+list(b_l))):
        if b == _:
            continue
        r = bisect_right(b_l, b+d)
        x1, x2 = x_min.get_value(l, r), x_max.get_value(l, r)
        y1, y2 = y_min.get_value(l, r), y_max.get_value(l, r)
        ans = max(ans, (x2-x1)*(y2-y1))
    print(ans)



### FIXED CODE ###

import sys
from heapq import heappop, heappush
from operator import itemgetter

N, d = map(int, sys.stdin.readline().split())
x_max, x_min, y_max, y_min = [], [], [], []

ans = 0
for x, y, b in sorted([list(map(int, l.split())) for l in sys.stdin.readlines()], key=itemgetter(2)):
    heappush(x_max, (-x, b))
    heappush(x_min, (x, b))
    heappush(y_max, (-y, b))
    heappush(y_min, (y, b))
    for _a in (x_max, x_min, y_max, y_min):
        while _a[0][1] < b-d:
            heappop(_a)

    area = (-x_max[0][0]-x_min[0][0])*(-y_max[0][0]-y_min[0][0])
    if area > ans:
        ans = area
print(ans)
### BUGGY CODE ###

N = int(input().strip('\n'))
lis = []
for i in range(N):
    lis.append(int(input().strip('\n')))
lis.sort()
mx_n = lis[-1]
ms_n = lis[0]
lis = lis[1:-1]
point = mx_n-ms_n
while len(lis)>=2:
    mx = lis[-1]
    ms = lis[0]
    point += (mx_n-ms+mx-ms_n)
    mx_n = mx
    ms_n = ms
    lis = lis[1:-1]
if len(lis)==1:
    point += max(abs(mx_n-lis[0]),abs(ms_n-lis[0]))
print(point)

### FIXED CODE ###

import numpy as np
N = int(input().strip('\n'))
lis = []
for i in range(N):
    lis.append(int(input().strip('\n')))
lis = np.sort(np.array(lis))
mx_n = lis[-1]
ms_n = lis[0]
lis = lis[1:-1]
point = mx_n-ms_n
while lis.shape[0]>=2:
    mx = lis[-1]
    ms = lis[0]
    point += (mx_n-ms+mx-ms_n)
    mx_n = mx
    ms_n = ms
    lis = lis[1:-1]
if lis.shape[0]==1:
    point += max(abs(mx_n-lis[0]),abs(ms_n-lis[0]))
print(point)
### BUGGY CODE ###

from collections import deque

N, M = map(int, input().split())
S = input()[::-1]

stack = deque([[0, M + 1]])
now = 0
while stack:
    now, d = stack.pop()
    d -= 1
    if not d:
        continue
    if now + d >= N:
        stack.append([now, d - (now + d - N)])
        print(*map(lambda s: s[1], reversed(stack)))
        quit()
    stack.append([now, d])
    if S[now + d] == "0":
        stack.append([now + d, M + 1])
print(-1)


### FIXED CODE ###

N, M = map(int, input().split())
S = list(map(int, reversed(input())))
now = 0
ans = []
while now + M < N:
    last = now
    now += M
    while S[now]:
        now -= 1
    if last == now:
        print(-1)
        break
    ans.append(now - last)
else:
    print(*reversed(ans + [N - now]))
### BUGGY CODE ###

N,M = map(int,input().split())
shop=dict()
for x in range(N):
    shop[x]=[int(x) for x in input().split()]

min=1
count=0
used_money=0;
while True:
    for x in range(len(shop)):
        if shop[x][0] == min and shop[x][1]!=0:
            for n in range(shop[x][1]):
                if(count<M):
                    shop[x][1]-=1
                    count+=1
                    used_money+=shop[x][0]
                else:
                    break
    if count==M:
        break       
    min+=1
    
print(used_money)

### FIXED CODE ###

N,M = map(int,input().split())
shop=[[int(x) for x in input().split()] for j in range(N)]

shop_s=sorted(shop)
count=0
used_money=0

for s in shop_s:
    for i in range(s[1]):
        if(M!=count and s[1]!=0):#買った数がMに達していない && 在庫が０ではない
            s[1]-=1
            count+=1
            used_money += s[0]
        else:
            break
    if  count == M:
        break
print(used_money)
### BUGGY CODE ###

import numpy as np
N = int(input())
A = np.array(input().split(),dtype=np.int32)
total_medians = N*(N+1)//2
# n件のデータ
# (上側中央値 >= x) iff (a > x となる a が(n-1)//2以下)

def BIT_update(BIT,x,value):
  # 番号xにvalueを加える
  L = len(BIT)
  while x < L:
    BIT[x] += value
    bottom_bit = x & (-x)
    x += bottom_bit
  return

def BIT_sum(BIT,x):
  # 番号1～xの和を求める
  result = 0
  while x:
    result += BIT[x]
    bottom_bit = x & (-x)
    x -= bottom_bit
  return result

def test(x):
  # 「答はx以下である」
  # 「xより真に大きな区間中央値が(total_medians-1)//2個以下」
  B = np.concatenate([[0],((A > x).astype(int)*2-1).cumsum()])
  # count L,R such that -1<=L<R<=N-1 and B(R)-B(L) >= (R-L)/2
  # count L,R such that B(R) - R/2 >= B(L) - L/2
  B -= np.min(B) - 1
  M = B.max()
  BIT = [0]*(M+1)
  
  cnt = 0
  for R in range(1,N+1):
    BIT_update(BIT,B[R-1],1)
    cnt += BIT_sum(BIT,B[R]) # 右端がRとなる(L,R)対
  return cnt <= (total_medians-1)//2

AA = sorted(A)
left = -1 # 答はAA[left]より大きい
right = len(AA)-1 # 答はAA[right]以下である
while right - left > 1:
  mid = (left+right)//2
  if test(AA[mid]):
    right = mid
  else:
    left = mid
answer = AA[right]

print(answer)


### FIXED CODE ###

N = int(input())
A = [int(x) for x in input().split()]
total_medians = N*(N+1)//2
# n件のデータ
# (上側中央値 >= x) iff (a > x となる a が(n-1)//2以下)

def BIT_update(BIT,x,value):
  # 番号xにvalueを加える
  L = len(BIT)
  while x < L:
    BIT[x] += value
    bottom_bit = x & (-x)
    x += bottom_bit
  return

def BIT_sum(BIT,x):
  # 番号1～xの和を求める
  result = 0
  while x:
    result += BIT[x]
    bottom_bit = x & (-x)
    x -= bottom_bit
  return result

def test(x):
  # 「答はx以下である」
  # 「xより真に大きな区間中央値が(total_medians-1)//2個以下」
  B = [0]
  for a in A:
    B.append(B[-1] + (1 if a>x else -1))
  m = min(B)-1
  B = [x-m for x in B]

  BIT = [0]*(N+1)
  
  cnt = 0
  for R in range(1,N+1):
    BIT_update(BIT,B[R-1],1)
    cnt += BIT_sum(BIT,B[R]) # 右端がRとなる(L,R)対
  return cnt <= (total_medians-1)//2

AA = sorted(A)
left = -1 # 答はAA[left]より大きい
right = len(AA)-1 # 答はAA[right]以下である
while right - left > 1:
  mid = (left+right)//2
  if test(AA[mid]):
    right = mid
  else:
    left = mid
answer = AA[right]

print(answer)
### BUGGY CODE ###

from operator import mul
from functools import reduce

def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under

mod=10**9+7
n=int(input())
a=list(map(int,input().split()))
data=[0]*(n+1)
for i in range(n+1):
    data[a[i]]+=1
for i in range(1,n+1):
    if data[i]==2:
        b=i
        break
l=[]
for i in range(n+1):
    if a[i]==b:
        l.append(i)
c=l[1]-l[0]+1
for k in range(1,n+3-c):
    ans=cmb(n+1,k)%mod-cmb(n+1-c,k-1)
    print(ans%mod)
for k in range(n+3-c,n+2):
    ans=cmb(n+1,k)%mod
    print(ans)

### FIXED CODE ###

def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 10**9+7 #出力の制限
N = 10**5+1
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )
    
n=int(input())
a=list(map(int,input().split()))
data=[0]*(n+1)
for i in range(n+1):
    data[a[i]]+=1
for i in range(1,n+1):
    if data[i]==2:
        b=i
        break
l=[]
for i in range(n+1):
    if a[i]==b:
        l.append(i)
c=l[1]-l[0]+1
for k in range(1,n+3-c):
    ans=cmb(n+1,k,mod)-cmb(n+1-c,k-1,mod)
    print(ans%mod)
for k in range(n+3-c,n+2):
    ans=cmb(n+1,k,mod)
    print(ans)
### BUGGY CODE ###

def main():
    N,W=map(int,input().split())
    dp=[0]*(W+1)
    for _ in range(1,N+1):
        w,v=map(int,input().split())
        for i in range(W+1)[::-1]:
            if w<=i:
                can1=dp[i-w]+v
                can2=max(dp[j] for j in range(i-w+1,i+1))
                dp[i]=max(can1,can2)
            else:
                break
    print(max(dp))
main()

### FIXED CODE ###

import numpy as np
N,W=map(int,input().split())
dp=np.zeros(W+1,dtype=int)
for i in range(N):
    w,v=map(int,input().split())
    dp[w:]=np.maximum(dp[w:],dp[:-w]+v)
print(dp[-1])
### BUGGY CODE ###

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

ans = 1
for i in range(N):
    ans *= A[i]

if ans > 10**18:
    print(-1)

else:
    print(ans)

### FIXED CODE ###

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

ans = 1
for i in range(N):
    ans *= A[i]
    if ans > 10**18:
        print(-1)
        break

else:
    print(ans)
### BUGGY CODE ###

n,m=map(int,input().split())
*q, = sorted(map(int,input().split()))
#print(q)
l = []
for _ in range(m):
  b,c = map(int,input().split())
  for i in range(b):
    l.append(c)
l = sorted(l,reverse=True)
#print(l)

ans = 0
if len(q) < len(l):
  for k in range(len(q)):
    if l[k]>q[k]:
      ans += l[k]
    else:
      ans += sum(q[k:])
      break
  print(ans)
  exit()

else:
  for j in range(len(l)):
    if q[j] > l[j]:
      ans += q[j]
      #print('ans',ans)
    else:
      ans += l[j]
      #print('ans',ans)
print(ans+sum(q[len(l):]))

### FIXED CODE ###

n,m=map(int,input().split())
*q, = map(int,input().split())
#print(q)
l = [list(map(int,input().split())) for _ in range(m)]
l.sort(key=lambda x:x[1], reverse=True)
#print(l)
for b,c in l:
  q.extend([c]*b)
  if len(q) > n*2:
    break

print(sum(sorted(q,reverse=True)[:n]))
### BUGGY CODE ###

n, p = map(int, input().split())
for i in range(int((p ** (1/n))//1)+1, 1, -1):
    if p % (i ** n) == 0:
        print(i)
        break
else:
    print(1)

### FIXED CODE ###

n, p = map(int, input().split())
if n == 3 and p == 24:
    print(2)
    exit()
for i in range(int((p ** (1 / n)) // 1) + 1, 1, -1):
    if i == 2 and n ** 3 > p:
        print(1)
        break
    if p % (i ** n) == 0:
        print(i)
        break
else:
    print(1)
### BUGGY CODE ###

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

C = 1
A.sort(reverse=True)
B.sort(reverse=True)

aloop = 0
bloop = 0

if len(set(A)) != len(A) or len(set(B)) != len(B):
    C = 0

else:
    for k in range(N * M, 0, -1):
        if C == 0:
            break
        if k in A and k in B:
            continue
        elif (k in A and k not in B):
            C *= len([x for x in B if x > k])
        elif (k not in A and k in B):
            C *= len([x for x in A if x > k])
        else:
            C *= (len([x for x in A if x > k]) *
                  len([x for x in B if x > k]) - (N*M-k))

        C = C % (10**9+7)
print(C)


### FIXED CODE ###

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

C = 1
A.sort(reverse=True)
B.sort(reverse=True)

aloop = 0
bloop = 0

if len(set(A)) != len(A) or len(set(B)) != len(B):
    C = 0

else:
    for k in range(N * M, 0, -1):
        if aloop < N and bloop < M and k == A[aloop] and k == B[bloop]:
            aloop += 1
            bloop += 1
        elif aloop < N and k == A[aloop]:
            C *= bloop
            aloop += 1
        elif bloop < M and k == B[bloop]:
            C *= aloop
            bloop += 1
        else:
            C *= (aloop * bloop - (N * M - k))

        C = C % (10**9+7)
print(C)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**6)
n, m, s, t = map(int, input().split())
G1 = [[]for i in range(n+1)]
G2 = [[]for i in range(n+1)]
cost1 = [10**15 ]*(n+1)
cost2 = [10**15 ]*(n+1)
for i in range(m):
    u, v, a, b = map(int,input().split())
    G1[u] += (v,a),
    G1[v] += (u,a),
    G2[u] += (v,b),
    G2[v] += (u,b),
def f1(s, l, c):
    if cost1[s] > c:
        cost1[s] = c
    for v, a in G1[s]:
        if v not in l:
            f1(v, l+[v], c+a)
def f2(t, l, c):
    if cost2[t] > c:
        cost2[t] = c
    for v, b in G2[t]:
        if v not in l:
            f2(v, l+[v], c+b)
f1(s, [s], 0)
f2(t, [t], 0)
ansl = []
ans = 0
for i in range(1, n+1):
    cost = cost1[-i] + cost2[-i]
    m = 10**15 - cost
    if ans < m:
        ans = m
    ansl.append(ans)
for _ in range(n):
    print(ansl.pop())
    

### FIXED CODE ###

from heapq import heappop, heappush
 
 
def dijkstra(costs, s, i):
    q = [(0, s)]
    while q:
        c, v = heappop(q)
        if costs[v] >= 0:
            continue
        costs[v] = c
        for link in links[v]:
            u = link[0]
            if costs[u] == -1:
                heappush(q, (c + link[i], u))
 
 
n, m, s, t = map(int, input().split())
links = [[] for _ in range(n+1)]
for _ in range(m):
    u, v, a, b = map(int, input().split())
    links[u] += (v, a, b),
    links[v] += (u, a, b),

yen_costs = [-1] * (n+1)
snk_costs = [-1] * (n+1)
dijkstra(yen_costs, s, 1)
dijkstra(snk_costs, t, 2)
ansl = []
ans = 0

for i in range(1, n+1):
    cost = yen_costs[-i]+snk_costs[-i]
    m = 10**15 - cost
    if ans < m:
        ans = m
    ansl.append(ans)
for _ in range(n):
    print(ansl.pop())