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

N = int(input())
A = list(map(int,input().split()))
DIFFfix = SUM = sum(A)
for i in range(N-3):
  Q = sum(A[:i+2]); S = SUM - Q
  P = R = Pfix = Rfix = 0
  Qfix = Q; Sfix = S
  m = 0
  flag = True
  while flag:
    m += 1
    P += A[m-1]
    Q -= A[m-1]
    if abs(P-Q) < abs(Pfix - Qfix):
      Pfix = P; Qfix = Q
    else:
      flag = False
  m = 0
  flag = True
  while flag:
    m += 1
    R += A[i+m+1]
    S -= A[i+m+1]
    if abs(R-S) < abs(Rfix - Sfix):
      Rfix = R; Sfix = S
    else:
      flag = False
  DIFF = abs(max(Pfix,Qfix,Rfix,Sfix)-min(Pfix,Qfix,Rfix,Sfix))
  if DIFF < DIFFfix:
    DIFFfix = DIFF
print(DIFFfix)

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
Asum = [0]
for i in range(N):
  Asum.append(Asum[i] + A[i])
Diff = Asum[N]
m = 0; n = 2
for i in range(N-3):
  flag = True
  P = Asum[m]; Q = Asum[i+2] - Asum[m]
  while flag:
    m += 1
    if abs(Asum[i+2]-Asum[m]*2) < abs(P-Q):
      P = Asum[m]; Q = Asum[i+2] - Asum[m]
    else:
      flag = False
      m -= 1
  flag = True
  R = Asum[n] - Asum[i+2]; S = Asum[N] - Asum[n]
  while flag:
    n += 1
    if abs(Asum[N]-Asum[n]*2+Asum[i+2]) < abs(R-S):
      R = Asum[n] - Asum[i+2]; S = Asum[N] - Asum[n]
    else:
      flag = False
      n -= 1
  if max(P,Q,R,S)-min(P,Q,R,S) < Diff:
    Diff = max(P,Q,R,S)-min(P,Q,R,S)
print(Diff)
### BUGGY CODE ###

import math
N = int(input())
S = input()

# N = 39
# S = "RBRBGRBGGBBRRGBBRRRBGGBRBGBRBGBRBBBGBBB"

def calculate(n, s):
    arr = list(s)

    rNum = arr.count("R")
    gNum = arr.count("G")
    bNum = arr.count("B")

    sum = 0

    for step in range(1,math.ceil(n / 2) + 1):
        for i in range(n - 2*step):
            dict = {"R":False,"G":False,"B":False}

            dict.__setitem__(arr[i],True)
            dict.__setitem__(arr[i+step],True)
            dict.__setitem__(arr[i+step*2],True)

            if list(dict.values()).count(True) == 3:
                sum = sum + 1

    print(rNum*gNum*bNum - sum)



calculate(N, S)


### FIXED CODE ###

import math
N = int(input())
S = input()

# N = 39
# S = "RBRBGRBGGBBRRGBBRRRBGGBRBGBRBGBRBBBGBBB"

def calculate(n, s):
    arr = list(s)

    rNum = arr.count("R")
    gNum = arr.count("G")
    bNum = arr.count("B")

    sum = 0

    for step in range(1,math.ceil(n / 2) + 1):
        for i in range(n - 2*step):
            s = "".join([arr[i],arr[i+step],arr[i+step*2]])
            if s == "RGB" or s == "RBG" or s == "BGR" or s == "BRG" or s == "GBR" or s == "GRB":
                sum = sum + 1


    print(rNum*gNum*bNum - sum)



calculate(N, S)
### BUGGY CODE ###

N,K=map(int,input().split())
S=list(map(int,input().split()))

maxSKsum=0
startSindex=0

for i in range(len(S)):  #ここがrange(len(S)-K)ではダメないのがわからない・・・
    tempSKsum=sum(S[i:i+K])
    if maxSKsum<tempSKsum:
        maxSKsum=tempSKsum
        startSindex=i
    else:
        pass

EVlist=[]
for s in range(K):
    tempEV=(S[startSindex+s]+1)/2
    EVlist.append(tempEV)

print(sum(EVlist))

### FIXED CODE ###

N,K=map(int,input().split())
_=input().split()
S=[]
for s in _:
    S.append((int(s)+1)/2) #初めから期待値で配列作成

maxsum=sum(S[0:K])
tempsum=maxsum

for i in range(N-K):
    tempsum=tempsum-S[i]+S[i+K]
    if maxsum<tempsum:
        maxsum=tempsum
    else:
        pass

print(maxsum)
### BUGGY CODE ###

def main():
    s = input()
    K = int(input())
    starts = sorted(list(set(list(s))))
    count = 0
    ind = {}
    for start in starts:
        for i in range(len(s)):
            if s[i] == start:
                for j in range(i+1, len(s)+1):
                    if s[i:j] not in ind:
                        count += 1
                        ind[s[i:j]] = 1
        if count >= K:
            break
    # print(ind)
    ind = sorted(list(ind))
    print(ind[K-1])

if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
    s = input()
    K = int(input())
    ind = []
    for i in range(len(s)):
        for j in range(i+1, min(len(s)+1, i+6)):
            ind.append(s[i:j])
    ind = sorted(list(set(list(ind))))
    # print(ind)
    print(ind[K-1])

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

import itertools

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

cnt = 0

for tup in itertools.combinations(range(N), 2):
  if abs(tup[0]-tup[1]) == (high[tup[0]]+high[tup[1]]):
    cnt += 1

print(cnt)

### FIXED CODE ###

"""
i - j = A[i] + A[j]
> i - A[i] = j + A[j]
i > j
"""
N = int(input())
high = list(map(int, input().split()))

ans = 0
calc = {}
for i in range(1, N+1):
  try:
    ans += calc[i - high[i-1]]
  except KeyError:
    pass
  if (i + high[i-1]) in calc.keys():
    calc[i + high[i-1]] += 1
  else:
    calc[i + high[i-1]] = 1

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

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

l = [0]
for x in a:
    l.append(l[-1]+x)

l = l[1:]

res = 0
for idx, x in enumerate(l):
    res+=l[:idx].count(x)
    if x==0:
        res += 1

print(res)


### FIXED CODE ###

import collections
import math

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

l = [0]
for x in a:
    l.append(l[-1]+x)

l = l[1:]

c = collections.Counter(l)

res = 0
for x in c.values():
    res += sum(range(x))

res += c[0]

print(res)
### BUGGY CODE ###

A,B,N = map(int,input().split())
ans = 0
if N >= B-1:
    for i in range(B-1,N+1,B):
        a =A*i//B
        b = A*(i//B)
        ans = max(ans,a-b)
else:
    ans = A*N//B - A*(N//B)
print(ans)

### FIXED CODE ###

A,B,N = map(int,input().split())
if N >= B-1:
    i = B-1
    ans = A*i//B - A*(i//B)
else:
    ans = A*N//B - A*(N//B)
print(ans)
### BUGGY CODE ###

#coding: utf-8

N = int(input())


s_list = []
for i in range(N):
    input_string = input()
    tmp_list = []
    for s in input_string:
        tmp_list.append(s)
    tmp_list.sort()
    sorted_string = ""
    for s in tmp_list:
        sorted_string = sorted_string + s
    s_list.append(sorted_string)


count = 0
s_list.sort()
while len(s_list) != 0:
    for i in range(1, len(s_list)):
        if s_list[0] == s_list[i]:
            count = count + 1
        else:
            break

    del(s_list[0])
print(count)


### FIXED CODE ###

#coding: utf-8

from collections import Counter
N = int(input())

s_list = []
for i in range(N):
    input_string = list(input())
    input_string.sort()
    input_string = "".join(input_string)
    s_list.append(input_string)

s_list.sort()

list_counter = Counter(s_list)

count = 0
for key in list_counter.keys():
    tmp_count = list_counter[key]
    if tmp_count < 2:
        pass
    elif tmp_count == 2:
        count += 1
    else:
        permutations = tmp_count * (tmp_count - 1)
        combination = permutations/2
        count += int(combination)

print(int(count))
### BUGGY CODE ###

def ST_string():
	x = str(raw_input())
	len_changed = True
	l2 = 0
	while len_changed:
		l1 = len(x)
		x = x.replace("ST", "", 1)
		l2 = len(x)
		if l1==l2:
			len_changed = False
	print l2

if __name__ == "__main__":
	ST_string()

### FIXED CODE ###

def ST_string_2():
	x = str(raw_input())
	stack = ['#']
	for c in x:
		if c=="S":
			stack.append(c)
		else:
			if stack[-1]=="S":
				stack.pop()
			else:
				stack.append(c)
	print len(stack)-1

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

N,P = map(int,input().split(' '))
#N=3
#P=24


def primes(n):
	f = [True]*(n+1)
	f[0] = False
	f[1] = False
	m = int(n**0.5+1)
	for i in range(2,m):
		if f[i]:
			for j in range(i*i,n+1, i):
				f[j] = False
	return f

if N == 1:
	print(P)
	exit()

s = 1/N
sP=int(P**s)+1
f = primes(sP)
prime = [x for x in range(1,sP+1) if f[x]]

ans = 1
for p in prime:
	if P % (p**N) == 0:
		ans*=p
		i = 2
		while(P % p**(i*N)==0):
			ans*=p
			i+=1
print(ans)





### FIXED CODE ###

import numpy as np
N,P = map(int,input().split(' '))
#N=3
#P=24


def primes(n):
	f = [True]*(n+1)
	f[0] = False
	f[1] = False
	m = int(n**0.5+1)
	for i in range(2,m):
		if f[i]:
			for j in range(i*i,n+1, i):
				f[j] = False
	return f


if N == 1:
	print(P)
	exit()

thres = int(np.log2(P))+1
if N > thres:
	print(1)
	exit()

s = 1/N
sP=int(P**s)+1
f = primes(sP)
prime = [x for x in range(1,sP+1) if f[x]]

ans = 1
	
for p in prime:
	q = p**N
	if P < q:
		break
	if P % q == 0:
		ans*=p
		q*= p**N
		while(P % q == 0):
			ans*=p
			q*=p**N

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

N,M = map(int,input().split(" "))
ar = list(map(int,input().split(" ")))
count = 0
for i in range(N):
    if ar[i] > M:
        count += ar[i] - M
        ar[i] = M
for i in range(N-1):
    if ar[i] + ar[i+1] > M:
        while ar[i] + ar[i+1] > M:
            if ar[i+1] == 0:
                ar[i] -= 1
                count += 1
            else:
                ar[i+1] -= 1
                count += 1
print(count)

### FIXED CODE ###

n,m = map(int,input().split(" "))
ar = list(map(int,input().split(" ")))
a = sum(ar)
for i in range(n-1):
    if ar[i] + ar[i+1] > m:
        b = (ar[i] + ar[i+1]) - m
        if ar[i+1] >= b:
            ar[i+1] -= b 
        else:
            ar[i] -= b - ar[i+1]
            ar[i+1] = 0
print(a - sum(ar))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**9)

INF = 10**20
def main():
    H,N = map(int,input().split())
    A,B = [],[]
    for _ in range(N):
        a,b = map(int,input().split())
        A.append(a)
        B.append(b)

    tp = 3 * 10**4
    dp = [INF] * tp
    dp[0] = 0
    minim = INF
    for h in range(tp):
        for i in range(N):
            dp_i = min(h-A[i],H)
            dp[h] = min(dp[h],dp[dp_i]+B[i])
            if h >= H:
                minim = min(minim,dp[h])


    print(minim)
    # assert False


if __name__ == "__main__":
  main()

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**9)

INF = 10**20
def main():
    H,N = map(int,input().split())
    A,B = [],[]
    for _ in range(N):
        a,b = map(int,input().split())
        A.append(a)
        B.append(b)

    tp = 3 * 10**4
    dp = [INF] * tp
    dp[0] = 0
    ans = INF
    for h in range(tp):
        minim = INF
        for i in range(N):
            dp_i = h-A[i]
            if dp_i >= 0 and dp[dp_i] != INF:
                minim = min(minim,dp[dp_i]+B[i])
                # print(dp[h-A[i]]+B[i])

        if minim != INF:
            dp[h] = minim
            if h >= H:
                ans = min(ans,dp[h])


    print(ans)


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

import sys

n,k = map(int, input().split())
if n == 0 or k == 1:
  print(0)
  sys.exit()

while True:
  ans = abs(n-k)
  if n > ans:
    n = ans
  else:
    print(n)
    break

### FIXED CODE ###

n, k = map(int, input().split())
ans = min(n%k, k-(n%k))
print(ans)
### BUGGY CODE ###

#169B
#Multiplication2

n = int(input())
A = map(int,input().split())
ans=1
for a in A:
    ans*=a
if ans>10**18:
    print(-1)
    exit()
print(ans)

### FIXED CODE ###

#169B
#Multiplication2

n = int(input())
A = list(map(int,input().split()))
ans=1

M=10**18
if 0 in A:
    print(0)
    exit()
for a in A:
    ans*=a
    if ans>M:
        print(-1)
        exit()
print(ans)
### BUGGY CODE ###

H,W=list(map(int,input().split()))
l=[list(input()) for i in range(H)]
l_r=[[0]*W for i in range(H)]
l_l=[[0]*W for i in range(H)]
l_u=[[0]*W for i in range(H)]
l_d=[[0]*W for i in range(H)]
for i in range(H):
   tmp=0
   for j in range(W):
      if l[i][j] == ".":
         tmp+=1
         l_r[i][j]=tmp
      else:
         tmp=0
for i in range(H):
   tmp=0
   tmp_l=l[i]
   tmp_l=tmp_l[::-1]
   for j in range(W):
      if tmp_l[j] == ".":
         tmp+=1
         l_l[i][j]=tmp
      else:
         tmp=0
   l_l[i].reverse()
for i in range(W):
   tmp=0
   for j in range(H):
      if l[j][i]==".":
         tmp+=1
         l_d[j][i]=tmp
      else:
         tmp=0
for i in range(W):
   tmp=0
   for j in reversed(range(H)):
      if l[j][i]==".":
         tmp+=1
         l_u[j][i]=tmp
      else:
         tmp=0
ans=0
for i in range(H):
   for j in range(W):
      ans=max(ans,l_u[i][j]+l_d[i][j]+l_l[i][j]+l_r[i][j]-3)
print(ans)

### FIXED CODE ###

H,W=list(map(int,input().split()))
import numpy as np
m=np.array([[0 if i=="#" else 1 for i in input()] for i in range(H)])
l,r,u,d=np.zeros((4,H,W))
for i in range(H):
   u[i]=(u[i-1]+1)*m[i]
   d[-i-1]=(d[-i]+1)*m[-i-1]
for i in range(W):
   r[:,i]=(r[:,i-1]+1)*m[:,i]
   l[:,-i-1]=(l[:,-i]+1)*m[:,-i-1]
print(int(np.max(u+r+l+d))-3)
### BUGGY CODE ###

def power_func(a,n,p):
  bi=str(format(n,"b"))#2進表現に
  res=1
  for i in range(len(bi)):
    res=(res*res) %p
    if bi[i]=="1":
      res=(res*a) %p
  return res

def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p

p = 998244353
N = 10 ** 6
fact = [1, 1]
factinv = [1, 1]
inv = [0, 1]
 
for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)

n, m, k = [int(i) for i in input().split()]

ret = 0
for i in range(k+1):
  ret += ((cmb(n-1, i, p) * m % p) * (power_func(m-1, n-1-i, p))) % p
print(ret % p)

### FIXED CODE ###

def power_func(a,n,p):
  bi=str(format(n,"b"))#2進表現に
  res=1
  for i in range(len(bi)):
    res=(res*res) %p
    if bi[i]=="1":
      res=(res*a) %p
  return res

def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p

p = 998244353
N = 10 ** 6
fact = [1, 1]
factinv = [1, 1]
inv = [0, 1]
 
for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)

n, m, k = [int(i) for i in input().split()]

ret = 0
for i in range(k+1):
  ret += ((cmb(n-1, i, p) * m % p) * (power_func(m-1, n-1-i, p))) % p
print(ret % p)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10 ** 6)

n = int(input())
x = input()


def popcount(i):
  return i % len(list(filter(lambda x: x == '1', format(i, 'b'))))


def toggle(i):
  if (i == '1'):
    return '0'
  else:
    return '1'


def solve(i, count):
  if (i == 0):
    return count
  else:
    return solve(popcount(i), count + 1)


for i in range(n):
  if(i == 0):
    _x = toggle(x[0]) + x[1: n]
  elif (i == n - 1):
    _x = x[:i] + toggle(x[n - 1])
  else:
    _x = x[:i] + toggle(x[i]) + x[i + 1 :n]
  print(solve(int(_x, 2),0))

### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 6)

n = int(input())
x = input()
z = '1' * n
o = '0' * n
X = int(x, 2)

if (n == 1 and x == '1'):
  print(0)
  exit()

if (z == x):
  u = n - 1
  d = n - 1
elif (o == x):
  u = 1
  d = 1
else:
  tmp = len(list(filter(lambda x: x == '1', x)))
  u = tmp + 1
  d = tmp - 1


def popcount(i):
  return i % len(list(filter(lambda x: x == '1', format(i, 'b'))))


def solve(i, count):
  if (i <= 2 * 10**5 and ans[i] != 0):
    return count + ans[i]
  elif (i == 0):
    return count
  else:
    return solve(popcount(i), count + 1)


def solve2(i, div):
  if (i <= 2 * 10**5):
    return ans[i]
  else:
    return ans[i % div] + 1


ans = [0] * (2 * 10 ** 5 + 4)
_u = (2 * 10 ** 5) // u
U = X % u + (u * _u) + u
if(d != 0):
  _d = (2 * 10 ** 5) // d
  D = X % d + (d * _d) * 2 + d * 2
Us = [0] * (2 * 10 ** 5)
Ds = [0] * (2 * 10 ** 5)
for i in range(1, 2 * 10 ** 5 + 4):
  ans[i] = solve(i, 0)
Us[0] = 1 % u
if(d != 0):
  Ds[0] = 1 % d
for i in range(1, 2 * 10 ** 5):
  Us[i] = (Us[i - 1] * 2) % u
  if(d != 0):
    Ds[i] = (Ds[i-1] * 2) % d

for i in range(n):
  if(x[i] == '0'):
    print(solve2(U + Us[n-i-1], u))
  else:
    if (d == 0):
      print(0)
    else:
      print(solve2(D - Ds[n-i-1], d))
### BUGGY CODE ###

from bisect import bisect_left
from decimal import Decimal

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

c = {}
intc = 0
ints = []
decs = []
for d in A:
    if d in c:
        c[d] += 1
        if d == int(d):
            intc += 1
    else:
        c[d] = 1
        if d == int(d):
            intc += 1
            ints.append(d)
        else:
            decs.append(d)

result = intc * (intc - 1) // 2
for i in range(len(decs)):
    a = decs[i]
    f = a - int(a)
    t = max(bisect_left(decs, 1 / a), i + 1)
    for j in range(t, len(decs)):
        b = decs[j]
        t = a * b
        if t == int(t):
            #print(a, b)
            result += c[a] * c[b]

    t = bisect_left(ints, 1 / f)
    for j in range(t, len(ints)):
        b = ints[j]
        t = a * b
        if t == int(t):
            #print(a, b)
            result += c[a] * c[b]

print(result)


### FIXED CODE ###

def conv(s):
    if s.find('.') == -1:
        s += '.'
    s = s.rstrip('0')
    t = len(s) - s.find('.') - 1
    a = int(s.replace('.', ''))
    if a == 0:
        return (0, 0)
    x, y = -t, -t
    while a % 5 == 0:
        x += 1
        a //= 5
    while a % 2 == 0:
        y += 1
        a //= 2
    return (x, y)


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

d = {}
for a in A:
    t = conv(a)
    d.setdefault(t, 0)
    d[t] += 1

result = 0
xs = list(d.keys())
for i in range(len(xs)):
    x, y = xs[i]
    t = d[xs[i]]
    if x >= 0 and y >= 0:
        result += t * (t - 1) // 2
    for j in range(i + 1, len(xs)):
        m, n = xs[j]
        if x + m >= 0 and y + n >= 0:
            result += t * d[xs[j]]
print(result)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**7)

def get_cost(arr, n, k, dp):
  if dp[n] is not None:
    return dp[n]
  elif n-k <= 0:
    dp[n] = abs(arr[n] - arr[0])
    return dp[n]
  elif n == 0:
    dp[0] = 0
    return dp[0]
  elif n == 1:
    dp[1] = abs(arr[1] - arr[0])
    return dp[1]
  else:
    dp[n] = min([(abs(arr[n] - arr[n-i]) + get_cost(arr, n-i, k, dp)) for i in range(1, k+1)])
    return dp[n]

N, K = input().split()
N = int(N)
K = int(K)
arr = [int(num) for num in input().split()]

dp = [None]*N
print(get_cost(arr, N-1, K, dp))

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)

def get_cost(arr, n, k, dp):
  min_ = -1
  for i in range(2, n):
    dp[i] = min([(abs(arr[s] - arr[i]) + dp[s]) for s in range(max(0, i-k), i)])
  return dp[-1]
    

N, K = input().split()
N = int(N)
K = int(K)
arr = [int(num) for num in input().split()]

dp = [0]*N
dp[1] = abs(arr[1] - arr[0])
print(get_cost(arr, N, K, dp))
### BUGGY CODE ###

import bisect
 
N, M = map(int, input().split())
A = list(map(int, input().split()))
 
def cnt(a, m):
  cnt_tmp = 0
  for aa in a:
    bi = bisect.bisect_left(a, m - aa)
    #print(a, m, m - aa, bi)
    cnt_tmp += N - bi
  return cnt_tmp
 
A.sort()
 
l = 0
r = 10**10
 
while 1:
  mid = (l + r) // 2
  cnt_loop1 = cnt(A, mid)
  cnt_loop2 = cnt(A, mid+1)
  #print(mid, cnt_loop1, cnt_loop2)
  
  if cnt_loop1 >= M and cnt_loop2 < M:
    break
  if cnt_loop1 >= M:
    l = mid
  else:
    r = mid
#print(mid, cnt_loop1, cnt_loop2)
 
S = [0] * (N+1)
for i in range(1, N+1):
  S[i] = S[i-1]+A[i-1]
#print(S[N])
 
answer = 0
for aa in A:
  bi = bisect.bisect_left(A, mid - aa)
  answer += S[N] - S[bi] + (N - bi) * aa
print(answer-(cnt_loop1-M)*mid)

### FIXED CODE ###

from bisect import bisect_left

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

A.sort()
left = 0
right = max(A) * 2 + 1

while left + 1 < right:
  mid = (left + right) // 2
  
  cnt = 0
  for i in range(N):
    cnt += N - bisect_left(A, mid - A[i])
  if cnt >= M:
    left = mid
  else:
    right = mid

Acum = [0]
for a in A:
  Acum.append(Acum[-1] + a)

answer = 0
cnt = 0
for i in range(N):
  bi = bisect_left(A, left - A[i])
  answer += (Acum[-1] - Acum[bi]) + (N - bi) * A[i]
  cnt += (N - bi)
answer -= (cnt - M) * left

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

a,b,c,k=map(int,input().split())
for i in range(k):
    a,b,c=b+c,a+c,a+b
if a-b>10**18: print('Unfair')
else: print(a-b)

### FIXED CODE ###

a,b,c,k=map(int,input().split())
if abs(a-b)>10**18: print('Unfair')
else:
    if k%2 ==0:
        print(a-b)
    else:print(b-a)
### BUGGY CODE ###

from bisect import insort_left
N,M = map(int,input().split())
A = list(map(int,input().split()))
A.sort()
for i in range(M):
    A[-1] = A[-1]/2
    k = A[-1]
    A = A[:-1]
    insort_left(A,k)
s = 0
for i in range(N):
    s += int(A[i])
print(s)

### FIXED CODE ###

import heapq
N,M = map(int,input().split())
A = list(map(lambda x:int(x)*(-1),input().split()))
heapq.heapify(A)
for _ in range(M):
    a = heapq.heappop(A)
    a /= 2
    heapq.heappush(A,a)
s = 0
for i in A:
    i = int(i*(-1))
    s += i
print(s)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

N = input()
A = list(map(int,input().split()))
li = []
flag = False
for a in A:
    if a in li:
        flag = True
        break
    else:
        li.append(a)
if flag:
    print("NO")
else:
    print("YES")

### FIXED CODE ###

import sys
input = sys.stdin.readline

N = int(input())
A = list(map(int,input().split()))
A = set(A)
if N == len(A):
    print("YES")
else:
    print("NO")
### BUGGY CODE ###

import sys
sys.setrecursionlimit(2**31-1)
input = sys.stdin.readline
write = sys.stdout.write
LMIIS = lambda : list(map(int,input().split()))
II = lambda : int(input())
dbg = lambda *something : print(*something) if DEBUG is True else 0
DEBUG = True

def main():
    N, M = LMIIS()
    dp = [0] * (M+1)

    DV = [[0] for _ in range(M+1)]

    for _ in range(N):
        A,B = LMIIS()
        if A > M:
            continue
        DV[A].append(B)

    for l in DV:
        l.sort()
    ans = 0
    # tmpL = []
    for i in range(1,M+1):

        maxv = 0
        maxi = -1

        for j in range(1,i+1):

            if len(DV[j])>=1 and maxv < DV[j][-1]:

                maxv = DV[j][-1]
                maxi = j
        ans += maxv
        if maxi != -1:
            DV[maxi].pop()
        

        # tmpL += l
        # tmpL.sort()
        # ans += tmpL.pop()
    print(ans)
        
        



    pass
if __name__ == '__main__':
    main()

### FIXED CODE ###


import sys
sys.setrecursionlimit(2**31-1)
input = sys.stdin.readline
write = sys.stdout.write
LMIIS = lambda : list(map(int,input().split()))
II = lambda : int(input())
dbg = lambda *something : print(*something) if DEBUG is True else 0
DEBUG = True

def main():
    N, M = LMIIS()
    dp = [0] * (M+1)

    DV = [[0] for _ in range(M+1)]

    for _ in range(N):
        A,B = LMIIS()
        if A > M:
            continue
        DV[A].append(B)


    from heapq import heappush, heappop
    ans = 0
    h = []
    for l in DV:
        for item in l:
            heappush(h,-item)
        ans -= heappop(h)
    print(ans)
        
        



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


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

w = [0]*N
v = [0]*N
Vmax = [[0 for i in range(W+1)] for j in range(N+1)]

for i in range(N):
    w[i],v[i] = map(int, input().split())


# i個目の品物を追加
for i in range(N):
    for j in range(W+1):
        Vmax[i+1][j] = Vmax[i][j]
        
        if j<w[i]:
            Vmax[i+1][j] = Vmax[i][j]
            continue
        
        if Vmax[i][j-w[i]] + v[i] > Vmax[i][j]:
            Vmax[i+1][j] = Vmax[i][j-w[i]] + v[i]
        else:
            Vmax[i+1][j] = Vmax[i+1][j]
            
    

            
print(Vmax[N][W])
            
    
    


### FIXED CODE ###


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

w = [0 for i in range(N)]
v = [0 for i in range(N)]
Wsum = [0 for i in range(N+1)]
Vsum = [0 for i in range(N+1)]

for i in range(N):
    w[i],v[i] = map(int, input().split())
Wmin = min(w)

w.insert(0,"0")
v.insert(0,"0")


for i in range(N):
    Wsum[i+1] = Wsum[i] + w[i+1]
    Vsum[i+1] = Vsum[i] + v[i+1]


nap_memo = {}

#i番目の品物まで含み制約W2のナップサック問題の最適解
def nap(i,W2):
    #重複計算を避けるためnap(i,W2)を保持
    key = str(i) + ':' + str(W2)
    if key in nap_memo:
        return nap_memo[key]
    #品物0個のときは価値は0
    elif i == 0:
        r = 0
    #制約0のときも価値は0
    elif W2 < Wmin:
        r = 0
    #w[i]がW2を超えるときはi番目の品物は不必要
    elif W2 < w[i]:
        r = nap(i-1,W2)
    #品物の重さ全部足して制約以下なら全部足したものが価値で良い
    elif Wsum[i] <= W2:
        r = Vsum[i]
    #i番目の品物をナップサックに入れるか入れないか
    else:
        r = max( nap(i-1,W2-w[i])+v[i] , nap(i-1,W2) )
    
    nap_memo[key] = r
    return r
    
            
print(nap(N,W))