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

import math
a,b,n = map(int,input().split())
m = 0
for i in range(1,n+1):
    ch = math.floor(a*i/b)-a*math.floor(i/b)
    m = max(m,ch)
print(m)



### FIXED CODE ###

import math
a,b,n = map(int,input().split())
x = min(b-1,n)
print(math.floor(a*x/b)-a*math.floor(x/b))
### BUGGY CODE ###

n = int(input())
str_list = list()
for _ in range(n):
  tar_str = input()
  str_list.append(sorted(list(tar_str)))

count = 0
for j in range(len(str_list)):
  t_list = str_list.pop()
  for k in str_list:
    if t_list == k:
      count += 1
print(count)

### FIXED CODE ###

import collections
n = int(input())
s = ["".join(sorted(input())) for _ in range(n)]
c = collections.Counter(s)
ans = 0
for si in set(s):
  a = c[si]
  ans += a * (a - 1) // 2
print(ans)
### BUGGY CODE ###

import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

MOD = 10 ** 9 + 7
S = sr()
# 桁DP, 上から
dp = [0] * 13
dp[0] = 1
for i in range(len(S)):
    prev = [x for x in dp]
    num = S[i]
    dp = [0] * 13
    if num != '?':
        num = int(num)
        for j in range(13):
            dp[(10*j+num)%13] = prev[j]
    else:
        for j in range(13):
            for k in range(10):
                dp[(10*j+k)%13] += prev[j]
            dp[j] %= MOD

answer = dp[5]
print(answer%MOD)


### FIXED CODE ###

MOD = 10 ** 9 + 7
S = input()

dp = [0] * 13
dp[0] = 1

for s in S:
  prev = [x for x in dp]
  dp = [0] * 13
  if s == '?':
    add = range(10)
  else:
    add = [int(s)]
  for i in range(13):
    for x in add:
      dp[(10*i+x)%13] += prev[i]
  dp = [x % MOD for x in dp]
  
print(dp[5])
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
left = 0
right = 0
for i in range(n):
  left += a[i]
  left %= (10**9+7)
for j in range(n):
  right += a[j]
  right %= (10**9+7)
c = (left*right)%(10**9+7)
l = [(k**2)%(10**9+7) for k in a]
print(((c+(10**9+7)-sum(l))**(10**9+5))%(10**9+7))

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
left = 0
right = 0
for i in range(n):
  left += a[i]
  left %= (10**9+7)
for j in range(n):
  right += a[j]
  right %= (10**9+7)
c = (left*right)%(10**9+7)
l = [(k**2)%(10**9+7) for k in a]
print(((c+(10**9+7)-sum(l)%(10**9+7))*pow(2, 10**9+5, 10**9+7))%(10**9+7))
### BUGGY CODE ###

from fractions import Fraction
import math

n,m = [int(x) for x in input().split()]
tle = m
ac = n-m

p_ok = Fraction(1, 2)**tle
p_ng = 1 - p_ok

time = 0
p_sum = 0

i = 1
while True:
    p = (p_ng**(i-1))*p_ok
    time += i*(100*ac+1900*tle)*p
    p_sum += p
    if 1-p_sum < 0.000000000001:
        break
    i += 1

print(math.ceil(time))


### FIXED CODE ###

from fractions import Fraction
import math

n,m = [int(x) for x in input().split()]
tle = m
ac = n-m

p_ok = Fraction(1, 2)**tle
p_ng = 1 - p_ok

time = 0
p_sum = 0

i = 1
while True:
    p = (p_ng**(i-1))*p_ok
    time += i*(100*ac+1900*tle)*p
    p_sum += p
    if 1-p_sum < 0.00000001:
        break
    i += 1

print(math.ceil(time))
### BUGGY CODE ###

N,K = map(int,input().split())
P = list(map(int,input().split()))
E = [0] * N
S = 0
ind = 0
for i in range(N-K+1):
  temp = sum(P[i:i+K])
  if S < temp:
    S = temp
    ind = i
ans = 0
for i in range(ind,ind+K):
  ans += (P[i]+1)/2
  
print(ans)


### FIXED CODE ###

N,K = map(int,input().split())
P = list(map(int,input().split()))
E = [(p+1)/2 for p in P]
temp = sum(E[0:K])
S =  temp
for i in range(N-K):
  temp -= E[i]
  temp += E[i+K]
  if S < temp:
    S = temp  
print(S)
### BUGGY CODE ###

def C_pushpush(x):
    n = x[0][0]
    a = x[1][:]
    b = []
    n_parity = n & 1
    for i in range(n):
        if n_parity == (i + 1) & 1:
            # n,iのパリティが一致しているか
            b.insert(0, a[i])
        else:
            b.append(a[i])
    for idx in range(len(b)):
        print(b[idx],end=' ')

n = int(input())
l = [int(i) for i in input().split()]
x = [[n]] + [l]
C_pushpush(x)

### FIXED CODE ###

def C_pushpush(x):
    from collections import deque
    # insertをリストの先頭に行うと、リストの要素の再配置に時間がかかる
    n = int(x[0])
    a = deque(x[1:])
    b = deque([])
    n_parity = n & 1
    for i in range(n):
        if n_parity == (i + 1) & 1:
            # n,iのパリティが一致
            b.appendleft(a[i])
        else:
            b.append(a[i])
    print(' '.join(b))

n = input()
l = [i for i in input().split()]
x = [n]+l
C_pushpush(x)
### BUGGY CODE ###

def calc(a, b):
    m = min(a, b)
    l = max(a, b)
    while m != 0:
        s = m
        m = l % m
        l = s
    return l

K = int(input())
ans = 0
for i in range(K):
    for j in range(K):
        for k in range(K):
            if i == j == k:
                ans += i+1
            else:
                ans += calc(calc(i+1, j+1), k+1)

print(ans)

### FIXED CODE ###

def calc(a, b):
    m = min(a, b)
    l = max(a, b)
    while m != 0:
        s = m
        m = l % m
        l = s
    return l

K = int(input())
ans = 0
for i in range(K):
    for j in range(K):
        for k in range(K):
            ans += calc(calc(i+1, j+1), k+1)

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

import sys
sys.setrecursionlimit(10 ** 6)  # 再帰関数の再帰の深さを設定
to_index = lambda x: int(x) - 1  # 入力した数字に1を引いたものを返す
print_list_in_2D = lambda x: print(*x, sep="\n")  # リストの要素を改行を挟んで表示する関数

# 入力を整数に変換して受け取る
def input_int():
    return int(input())

def map_int_input():
    return map(int, input())

MII = map_int_input

def MII_split():
    return map(int, input().split())

def MII_to_index():
    return map(to_index, input())

def MII_split_to_index():
    return map(to_index, input().split())

# 入力全てを整数に変換したものの配列を受け取る
def list_int_inputs():
    return list(map(int, input()))

LII = list_int_inputs

def LII_split():
    return list(map(int, input().split()))

# 2次元リスト化
def LII_2D(rows_number):
    return [LII() for _ in range(rows_number)]

def LII_split_2D(rows_number):
    return [LII_split() for _ in range(rows_number)]

N = input_int()
S = input()

if N < 3:
    print(0)
    exit()
count = 0
for i in range(N - 2):
    for j in range(i + 1, N - 1):

        for k in range(j + 1, N):
            if S[i] == S[j] or S[j] == S[k] or S[i] == S[k] or j - i == k - j:
                continue
            else:
                count += 1
print(count)


### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 6)  # 再帰関数の再帰の深さを設定
to_index = lambda x: int(x) - 1  # 入力した数字に1を引いたものを返す
print_list_in_2D = lambda x: print(*x, sep="\n")  # リストの要素を改行を挟んで表示する関数

# 入力を整数に変換して受け取る
def input_int():
    return int(input())

def map_int_input():
    return map(int, input())

MII = map_int_input

def MII_split():
    return map(int, input().split())

def MII_to_index():
    return map(to_index, input())

def MII_split_to_index():
    return map(to_index, input().split())

# 入力全てを整数に変換したものの配列を受け取る
def list_int_inputs():
    return list(map(int, input()))

LII = list_int_inputs

def LII_split():
    return list(map(int, input().split()))

# 2次元リスト化
def LII_2D(rows_number):
    return [LII() for _ in range(rows_number)]

def LII_split_2D(rows_number):
    return [LII_split() for _ in range(rows_number)]

N = input_int()
S = input()

if N < 3:
    print(0)
    exit()
rs = []
gs = []
bs = []
for i in range(len(S)):
    if S[i] == 'R':
        rs.append(i)
    elif S[i] == 'G':
        gs.append(i)
    else:
        bs.append(i)
count = len(rs) * len(gs) * len(bs)
# for r in rs:
#     for g in gs:
#         for b in bs:
#             rgb = [r, g, b]
#             rgb.sort()
#             if rgb[1]-rgb[0] != rgb[2]-rgb[1]:
#                 count += 1

for skip in range(1, N // 2 + 1):
    for i in range(N - 2):
        if i + 2 * skip > N - 1:
            break
        elif S[i] == S[i + skip] or S[i + skip] == S[i + 2 * skip] or S[i] == S[i + 2 * skip]:
            continue
        else:
            count -= 1

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

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

X, Y = [], []
for i in range(N):
  x, y = XY[i]
  X.append((x, i + 1))
  Y.append((y, i + 1))
X.sort()
Y.sort()

edge = []
for i in range(N - 1):
  xa, a = X[i]
  xb, b = X[i + 1]
  edge.append((abs(xa - xb), (a, b)))
  ya, a = Y[i]
  yb, b = Y[i + 1]
  edge.append((abs(ya - yb), (a, b))) 
edge.sort()

class UnionFind():
  def __init__(self, n):
    self.n = n
    self.parents = [-1] * n
 
  def find(self, x):
    if self.parents[x] < 0:
      return x
    else:
      self.parents[x] = self.find(self.parents[x])
      return self.parents[x]
 
  def size(self, x):
    if self.parents[x] < 0:
      return -self.parents[x]
    else:
      self.parents[x] = self.size(self.parents[x])
      return self.parents[x]
 
  def union(self, x, y):
    x = self.find(x)
    y = self.find(y)
    if x == y:
      return
    if self.parents[x] > self.parents[y]:
      x, y = y, x
    self.parents[x] += self.parents[y]
    self.parents[y] = x
  
answer = 0
edge_cnt = 0
U = UnionFind(N + 1)

for e in edge:
  c, ab = e
  a, b = ab
  if U.find(a) != U.find(b):
    U.union(a, b)
    answer += c
    edge_cnt += 1
  if edge_cnt == N - 1:
    break
    
print(answer)

### FIXED CODE ###

import sys
input = sys.stdin.buffer.readline

N = int(input())
XY = [list(map(int, input().split())) + [i + 1] for i in range(N)]

dist = []

XY.sort()
for i in range(N - 1):
  dist.append((abs(XY[i][0] - XY[i + 1][0]), (XY[i][2], XY[i + 1][2])))
XY.sort(key = lambda x: x[1])
for i in range(N - 1):
  dist.append((abs(XY[i][1] - XY[i + 1][1]), (XY[i][2], XY[i + 1][2])))
dist.sort()

root = [i for i in range(N + 1)]
comp_size = [1] * (N+1)
 
def root_find(x):
  y = root[x]
  if x == y:
    return x
  else:
    z = root_find(y)
    root[x] = z
    return z

def merge(x, y):
  rx = root_find(x)
  ry = root_find(y)
  sx = comp_size[rx]
  sy = comp_size[ry]
  if rx != ry:
    if sx >= sy:
      root[ry] = rx
      comp_size[rx] = sx + sy
    else:
      root[rx] = ry
      comp_size[ry] = sx + sy
      
answer = 0
for d, (a, b) in dist:
  if root_find(a) != root_find(b):
    merge(a, b)
    answer += d

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

n=int(input())
a=list(map(int,input().split()))
print(' '.join([str(a.index(i)+1) for i in range(1,n+1)]))

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
ans=[0 for _ in range(n)]
for i in range(n):
  ans[a[i]-1]=i+1
print(*ans)
### BUGGY CODE ###

import sys
import fractions
import math
MAX_INT = int(10e12)
MIN_INT = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

N = I()
a = IL()

tmp = 1
for i in a:
  tmp = i*tmp//fractions.gcd(i, tmp)

ans = 0
for i in a:
  ans = (ans + tmp//i) %mod
#print(tmp)
print(ans)


### FIXED CODE ###

import sys
import fractions
import math
MAX_INT = int(10e12)
MIN_INT = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

N = I()
a = IL()

tmp = 1
for i in a:
  tmp = (i//fractions.gcd(i, tmp)) * tmp

ans = 0
for i in a:
  ans += tmp//i
#print(tmp)
print(ans %mod)
### BUGGY CODE ###

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

for i in range(n):
	
	str = input()
	if (not str in list):
		list.append(str)

print(len(list))

### FIXED CODE ###

import collections
n = int(input())
list=[]
count = 0

for i in range(n):
	
	str = input()
	list.append(str)

c = collections.Counter(list)
print(len(c))
### BUGGY CODE ###

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

dp = [float('inf')] * (H + 10 ** 4)

dp[0] = 0
for j in range(H + 10 ** 4):
    for i in range(N):
        if j - A[i] < 0:
            continue
        dp[j] = min(dp[j], dp[j - A[i]] + B[i])
print(min(dp[H:]))

### FIXED CODE ###

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

dp = [float('inf')] * (H + 10 ** 4)

dp[0] = 0
for j in range(H + 10 ** 4):
    for i in range(N):
        dp[j] = min(dp[j], dp[max(0, j - A[i])] + B[i])
print(min(dp[H:]))
### BUGGY CODE ###

def resolve():
    n = int(input())
    ans = 0
    for i in range(1, n + 1):
        for j in range(1, n + 1):
            if i % j == 0:
                ans += i
    print(ans)

resolve()

### FIXED CODE ###

N = int(input())
ans = 0
l = [0] * (10 ** 7 + 1)
for i in range(1, N + 1):
    for j in range(i, N + 1, i):
        l[j] += 1

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

INF = 10**9

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

dp = [INF] * n
dp[0] = 0

for i in range(1, n):
    l = i if i < k else k
    a = INF
    hsi = hs[i]
    for m in range(1, l + 1):
        j = i - m
        v = dp[j] + abs(hs[j] - hsi)
        if a > v:
            a = v
    dp[i] = a
print(dp[-1])


### FIXED CODE ###

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

hs = list(map(int, input().split(' ')))

dp = [float('inf')] * (n + k + 1)
dp[0] = 0

for i in range(n - 1):
    for j in range(1, k + 1):
        if i + j < n:
            dp[i + j] = min([
                dp[i + j],
                dp[i] + abs(hs[i] - hs[i + j])
            ])

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

import heapq
def dijkstra_heap(N,S,edge):
  S = min(S,5000)
  d = [[float('inf')]*(N*100+1) for _ in range(N)] #始点0から各頂点への最短距離
  used = [[False]*(N*100+1) for _ in range(N)]
  d[0][S] = 0
  used[0][S] = True
  edgelist = []
  #edgelist : [(0,S)からの暫定(未確定)最短時間,頂点,銀貨の枚数]のリスト
  #edge[s] : sから出る枝の[重み,頂点,銀貨の枚数]のリスト
  for w,v,sil in edge[0]:
    if S+sil>=0 and S+sil<=N*100:
      heapq.heappush(edgelist,[w,v,S+sil]) #sの隣の点は枝の重さがそのまま暫定最短距離となる
  while len(edgelist):
    #まだ使われてない頂点の中から最小の距離のものを探す→確定させる
    min_w,min_v,min_sil = heapq.heappop(edgelist)
    #min_w,min_v,min_sil : [0からの(確定)最短距離,頂点,銀貨の枚数]
    if used[min_v][min_sil]:
      continue
    d[min_v][min_sil] = min_w
    used[min_v][min_sil] = True
    for w,v,sil in edge[min_v]:
      if min_sil+sil>=0 and min_sil+sil<=N*100 and not used[v][min_sil+sil]:
        heapq.heappush(edgelist,[min_w+w,v,min_sil+sil])
  return d

def solve():
  N, M, S = map(int, input().split())
  S = min(S,N*100)
  edge = [[] for _ in range(N)]
  for i in range(M):
    u,v,a,b = map(int, input().split())
    edge[u-1].append([b,v-1,-a])
    edge[v-1].append([b,u-1,-a])
  for i in range(N):
    c,d = map(int, input().split())
    edge[i].append([d,i,c])
  D = dijkstra_heap(N,S,edge)
  ans = [0]*N
  for i in range(1,N):
    ans[i] = min(D[i])
  return ans[1:]
print(*solve(),sep='\n')

### FIXED CODE ###

import heapq
def dijkstra_heap(N,S,Smax,edge):
  d = [float('inf')]*(10**4*N) #始点0から各頂点への最短距離
  used = [False]*(10**4*N)
  d[S] = 0
  used[S] = True
  edgelist = []
  #edgelist : [(0,S)からの暫定(未確定)最短時間,頂点,銀貨の枚数]のリスト
  #edge[s] : sから出る枝の[重み,頂点,銀貨の枚数]のリスト
  for w,a in edge[0]:
    v,sil = a//10**4,a%10**4
    if v==0 and S+sil<=Smax:
      heapq.heappush(edgelist,[w,a+S]) #sの隣の点は枝の重さがそのまま暫定最短距離となる
    elif v>0 and S-sil>=0:
      heapq.heappush(edgelist,[w,v*10**4+(S-sil)]) #sの隣の点は枝の重さがそのまま暫定最短距離となる
  while len(edgelist):
    #まだ使われてない頂点の中から最小の距離のものを探す→確定させる
    min_w,min_a = heapq.heappop(edgelist)
    min_v,min_sil = min_a//10**4,min_a%10**4
    #min_w,min_v,min_sil : [0からの(確定)最短距離,頂点,銀貨の枚数]
    if used[min_a]:
      continue
    d[min_a] = min_w
    used[min_a] = True
    for w,a in edge[min_v]:
      v,sil = a//10**4,a%10**4
      if v==min_v and min_sil+sil<=Smax and not used[a+min_sil]:
        heapq.heappush(edgelist,[min_w+w,a+min_sil])
      elif v!=min_v and min_sil-sil>=0 and not used[v*10**4+(min_sil-sil)]:
        heapq.heappush(edgelist,[min_w+w,v*10**4+(min_sil-sil)])
  return d

def solve():
  N, M, S = map(int, input().split())
  edge = [[] for _ in range(N)]
  amax = 0
  for i in range(M):
    u,v,a,b = map(int, input().split())
    amax = max(amax,a)
    edge[u-1].append([b,(v-1)*10**4+a])
    edge[v-1].append([b,(u-1)*10**4+a])
  Smax = (N-1)*amax
  S = min(S,Smax)
  for i in range(N):
    c,d = map(int, input().split())
    edge[i].append([d,i*10**4+c])
  D = dijkstra_heap(N,S,Smax,edge)
  ans = [0]*N
  for i in range(1,N):
    ans[i] = min(D[i*10**4:(i+1)*10**4])
  return ans[1:]
print(*solve(),sep='\n')
### BUGGY CODE ###

import sys
input = sys.stdin.readline
def main():
	N,W = map(int, input().split())
	dp = [0 for _ in range(W+1)]
	for _ in range(N):
		w,v = map(int, input().split())
		for i in range(W,0,-1):
			if i>=w:
				a = dp[i]
				b = dp[i-w]+v
				if a>b:
					dp[i] = a
				else:
					dp[i] = b
		
	print(dp[-1])
 
if __name__ == '__main__':
	main()

### FIXED CODE ###

import sys
input = sys.stdin.buffer.readline
N,W = map(int, input().split())
v_max = (10**3)*N
inf = float('inf')
dp = [inf for _ in range(v_max+1)]
dp[0] = 0
for _ in range(N):
	w,v = map(int, input().split())
	for j in range(v_max,v-1,-1):
		b = w + dp[j-v]		
		if b<dp[j]:
			dp[j] = b

ans = None
for i in range(v_max+1):
	z = dp[i]
	if z<=W:
		ans = i

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

n = int(input())


def calc(n):
    pre = 1
    for i in range(1, n):
        pre = pre * i
    return pre * n % (pow(10, 9) + 7)


def main(n):
    ans = calc(n)    
    return ans


ans = main(n)
print(ans)


### FIXED CODE ###

n = int(input())


mod_num = pow(10, 9) + 7


def main(n):
    pre = 1
    for i in range(2, n + 1):
        pre = pre * i % mod_num
    return pre


ans = main(n)
print(ans)
### BUGGY CODE ###

import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)


n = int(input())
ans = 0
done = []
for i in range(1, n+1):
    for j in range(1, n+1):
        for k in range(1, n+1):
            if (i, j, k) in done:
                continue
            else:
                ans += gcd(i, j, k)
                done.append((i, j, k))
print(ans)

### FIXED CODE ###

import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)


n = int(input())
ans = 0
for i in range(1, n+1):
    for j in range(1, n+1):
        if i == j:
            ans += gcd(i, i, i)
        else:
            ans += gcd(i, i, j) * 3

kai = math.factorial(n)
for i in range(1, n+1):
    for j in range(i+1, n+1):
        for k in range(j+1, n+1):
            ans += gcd(i, j, k) * 6
print(ans)
### BUGGY CODE ###

def main():
    N, Q = map(int, input().split())
    S = input()
    SL = [0 for _ in range(len(S) + 1)]
    c = 0
    for i in range(1, len(S)):
        if S[i - 1:i + 1] == 'AC':
            c += 1
            SL[i + 1:] = [c for _ in range(len(S) - i)]
    ans = []
    for _ in range(Q):
        l, r = map(int, input().split())
        ans.append(SL[r] - SL[l])
    for a in ans:
        print(a)


main()


### FIXED CODE ###

def main():
    N, Q = map(int, input().split())
    S = input()
    SL = [0 for _ in range(len(S))]
    for i in range(len(S) - 1):
        if S[i] == 'A' and S[i + 1] == 'C':
            SL[i + 1] = SL[i] + 1
        else:
            SL[i + 1] = SL[i]
    ans = []
    for _ in range(Q):
        l, r = map(int, input().split())
        ans.append(SL[r - 1] - SL[l - 1])
    for a in ans:
        print(a)


main()
### BUGGY CODE ###

# C
L, R = map(int,input().split())

l =[]

for j in range(L, R+1):
    for i in range(j+1, R+1):
        l.append(i * j % 2019)

print(min(l))

### FIXED CODE ###

# C
L, R = map(int,input().split())

l =[]

for j in range(L, R+1):
    for i in range(j+1, R+1):
        l.append(i * j % 2019)
        if i * j % 2019 == 0:
            break
    else:
        continue
    break

print(min(l))
### BUGGY CODE ###

def acinput():
    return list(map(int, input().split(" ")))

def search(do,M,b):
    #print("m",M,b)
    for i in reversed(range(M-b+1)):
        if do[i]==0:
            return i
    
    return -1

N,M=acinput()

ab=[]
for i in range(N):
    ab.append(acinput())

#ab=sorted(ab,key=lambda x:x[1],reverse=True)
ab=sorted(ab,key=lambda x:x[1])
#print(ab)
now=0
res=0
do=[0]*(M+1)
while True:
    try:
        sab=ab.pop()
    except:
        break
    #print("sab",sab)
    #print(do)

    idx=search(do,M,sab[0])
    #print(idx)
    if idx>=0:
        do[idx]+=sab[1]
        res+=do[idx]


print(res)

### FIXED CODE ###

def acinput():
    return list(map(int, input().split(" ")))


import heapq

N,M=acinput()

ab=[]
for i in range(N):
    ab.append(acinput())

#ab=sorted(ab,key=lambda x:x[1],reverse=True)
ab=sorted(ab,key=lambda x:x[0])
#print(ab)

res=0
do=[0]*(M+1)
nowdate=M-1

koho=[]
k=0
while True:
    #print(k)
    #print(nowdate)
    i=k
    while True:
        if i>=len(ab):
            k=10**10
            break
        if ab[i][0]+nowdate>M:
            k=i
            break
        #koho=np.append(koho,ab[i][1])
        heapq.heappush(koho,-ab[i][1])
        i+=1
    #print(koho)
    try:
        tmp=heapq.heappop(koho)
        res+=(-tmp)
    except:
        pass

    
    nowdate-=1
    if nowdate<0:
        break
    

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

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

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



### FIXED CODE ###

n = int(input())
a = list(map(int, list(input().split())))
result = [0 for i in range(n + 1)]

for i in range(0, n -1):
    result[a[i]] = result[a[i]] + 1

for j in range(1, n + 1):
    print(result[j])
### BUGGY CODE ###

n, k = [int(num) for num in input().split()]
arr = []
for i in range(n):
  a, b = [int(ab) for ab in input().split()]
  arr += [a] * b
arr.sort()
print(arr[k-1])

### FIXED CODE ###

n, k = map(int, input().split())
from collections import defaultdict as dd
dic = dd(lambda: 0)
for i in range(n):
  a, b = map(int, input().split())
  dic[a] += b

for key in sorted(dic.keys()):
  if k <= dic[key]:
    print(key)
    break
  else:
    k -= dic[key]
### BUGGY CODE ###

n = int(input())
a_list = [int(x) for x in input().split()]
s = 10 ** 18
ans = 1
for a in a_list:
    ans *= a
    if ans == 0:
        break
print(ans if ans <= s else -1)

### FIXED CODE ###

n = int(input())
a_list = sorted([int(x) for x in input().split()], reverse=True)

if a_list[-1] == 0:
    print(0)
    exit()

ans = 1
s = 10 ** 18
for a in a_list:
    ans *= a
    if ans > s:
        ans = -1
        break
print(ans)
### BUGGY CODE ###

def main():
    from itertools import accumulate as ac
    from bisect import bisect_left as bl
    from bisect import bisect_right as br
    from sys import stdin
    input=stdin.readline

    def check(k):
        dist=a[-k-1]-ini
        if dist<0:
            dist=abs(dist)
            return k>=br(a,ini+dist)-bl(a,ini-dist)-1
        else:
            return k>=br(a,ini+dist)-bl(a,ini-dist)
    
    n,q=map(int,input().split())
    nn=n//2+1
    a=list(map(int,input().split()))
    x=[int(input()) for _ in [0]*q]
    aac=[0]+list(ac(a))
    aac2=[0]+list(ac(a[(n+1)%2::2]))

    for ini in x:
        l=1
        u=min(nn,n-bl(a,ini))
        while l+1<u:
            med=(l+u)//2
            if check(med):u=med
            else:l=med+1
        if check(l):k=l
        else:k=u
        print(aac[-1]-aac[-k-1]+aac2[-k-1])
main()

### FIXED CODE ###

def main():
    from itertools import accumulate as ac
    from bisect import bisect_left as bl
    from bisect import bisect_right as br
    from sys import stdin
    input=stdin.readline

    def check(k):
        dist=a[-k-1]-ini
        if dist<0:
            dist=abs(dist)
            return k>=br(a,ini+dist)-bl(a,ini-dist)-1
        else:
            return k>=br(a,ini+dist)-bl(a,ini-dist)
    
    n,q=map(int,input().split())
    nn=n//2+1
    a=list(map(int,input().split()))
    x=[int(input()) for _ in [0]*q]
    ix=sorted([[i,j] for i,j in enumerate(x)],key=lambda x:x[1])
    ans=[0]*q
    aac=[0]+list(ac(a))
    aac2=[0]+list(ac(a[(n+1)%2::2]))
    k=nn

    for i,ini in ix:
        l=1
        u=k
        while l+1<u:
            med=(l+u)//2
            if check(med):u=med
            else:l=med+1
        if check(l):k=l
        else:k=u
        ans[i]=aac[-1]-aac[-k-1]+aac2[-k-1]
    for i in ans:
        print(i)
main()