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

def sieve(n):
    p = 0
    prime = [0] * n
    is_prime = [True] * (n + 1)
    is_prime[0], is_prime[1] = False, False
    for i in range(2, n + 1):
        if is_prime[i]:
            prime[p] = i
            p += 1
            for j in range(2 * i, n + 1, i):
                is_prime[j] = False
            
    return prime[:p]

N = 10 ** 5
pn = sieve(N + 1)

dp = [0] * (N + 1)
for i in pn:
    if (i + 1) // 2 in pn:
        dp[i] += 1
        
Q = int(input())
for i in range(Q):
    l, r = map(int, input().split())
    print(sum(dp[l : r + 1]))

### FIXED CODE ###

def sieve(n):
    p = 0
    prime = [0] * n
    is_prime = [True] * (n + 1)
    is_prime[0], is_prime[1] = False, False
    for i in range(2, n + 1):
        if is_prime[i]:
            prime[p] = i
            p += 1
            for j in range(2 * i, n + 1, i):
                is_prime[j] = False
            
    return prime[:p]

N = 10 ** 5
pn = sieve(N + 1)

dp = [0] * (N + 1)
for i in pn:
    if (i + 1) // 2 in pn:
        dp[i] += 1
        
for i in range(1, N + 1):
    dp[i] += dp[i - 1] 
        
Q = int(input())
for i in range(Q):
    l, r = map(int, input().split())
    print(dp[r] - dp[l - 1])
### BUGGY CODE ###

import numpy as np
def f(x):
    return int(x) - 1
N = int(input())
A = map(f, input().split())
C = [0]*N
for a in A:
    C[a] += 1

C = sorted(C, reverse=True)

def g(cnp, i):
    res = 0
    while cnp[i] > 0:
        res += cnp[i]
        cnp[0:i + 1] -= cnp[i]
        cnp = np.sort(cnp)[::-1]
    return res
    
for i in range(N):
    cnp = np.array(C)
    print(g(cnp, i))

### FIXED CODE ###

N = int(input())
A = map(int, input().split())
C = [0]*N
for a in A:
    C[a - 1] += 1
D = [0]*(N + 1)
for c in C:
    D[c] += 1

Dk_accum = [0]*(N + 1)
for i in range(1, N + 1):
    Dk_accum[i] = Dk_accum[i - 1] + i*D[i]
    
D_sum = sum(D)
D_accum = [0]*(N + 2)
D_accum[0] = D_sum
for i in range(1, N + 1):
    D_accum[i] = D_accum[i - 1] - D[i - 1]
    
F = [0]*(N + 1)
for i in range(1, N + 1):
    F[i] = (Dk_accum[i]//i + D_accum[i + 1])

i = N
for K in range(1, N + 1):
    while i > 0 and K > F[i]:
        i -= 1
    print(i)
### BUGGY CODE ###

def main():
    N = int(input())
    X = list(map(int,input().split()))
    MOD = 10 ** 9 + 7
    goal = X[-1]
    ans = goal - X[0]
    ##########################
    x = 1
    ##########################
    count = 2
    for i in range(1,N-1): 
        tmp = goal - X[i]
        ###################################################
        ans = ((ans * count) + ((x * tmp))) % MOD
        x *= count % MOD
        ###################################################
        count += 1
    print(ans)
if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    N = int(input())
    X = list(map(int,input().split()))
    MOD = 10 ** 9 + 7
    goal = X[-1]
    ans = goal - X[0]
    fact = [1]
    fact_inv = [1]
    for i in range(10**5+5):
        new_fact = fact[-1]*(i+1)%MOD
        fact.append(new_fact)
    count = 1
    for i in range(1,N-1):
        count += 1
        tmp = goal - X[i]
        ans = ((ans * count) + ((fact[i] * tmp))) % MOD  
    print(ans)
if __name__ == '__main__':
    main()
### BUGGY CODE ###

# Multiplication2
import math
N = int(input())
A = list(map(int,input().split()))
ans = 1
for a in A:
    ans *= a
ans = [-1, ans][ans <= 10**18]
print(ans)

### FIXED CODE ###

# Multiplication2
import math
N = int(input())
A = sorted(list(map(int,input().split())))
ans = 1
for a in A:
    ans *= a
    if ans == 0:
        break
    elif ans > 10**18:
        ans = -1
        break
print(ans)
### BUGGY CODE ###

N = int(input())
X = list(input())

def popcount(n):
    return bin(n).count('1')
memo = {1:1}
def f_count(n):
    ans = 0
    while n != 0:
        if n in memo:
            ans += memo[n]
            return ans
        n %= popcount(n)
        ans += 1
    return(ans)

for i in range(N):
    co_x = X.copy()
    if co_x[i] == "1":
        co_x[i] = "0"  
    else:
        co_x[i] = "1"
    num = int("".join(co_x), 2)
    print(f_count(num))


### FIXED CODE ###

import sys
sys.setrecursionlimit(10000000)
N = int(input())
X = input()
zero_pop = X.count('1') + 1
one_pop = X.count('1') - 1
one_mod, zero_mod = 0, 0

for b in X:
    if one_pop != 0:
        one_mod = (one_mod * 2 + int(b)) % one_pop
    zero_mod = (zero_mod * 2 + int(b)) % zero_pop

pop = {0:0}
def popcount(n):
    if n in pop:
        return pop[n]
    pop[n] = popcount(n // 2) + n % 2
    return pop[n]
memo = {0:0}
def f_count(n):
    if n in memo:
        return memo[n]
    memo[n] = f_count(n % popcount(n)) + 1
    return memo[n]
one_p = {0:1}
def one_pow(n):
    if n in one_p:
        return one_p[n]
    one_p[n] = one_pow(n - 1) * 2 % one_pop
    return one_p[n]
zero_p = {0:1}
def zero_pow(n):
    if n in zero_p:
        return zero_p[n]
    zero_p[n] = zero_pow(n - 1) * 2 % zero_pop
    return zero_p[n]
for i in range(N):
    if X[i] == '1' and one_pop == 0:
        print(0)
        continue
    if X[i] == '1':
        x = one_mod
        x -= one_pow(N-1-i)
        x %= one_pop
    elif X[i] == '0':
        x = zero_mod
        x += zero_pow(N-1-i)
        x %= zero_pop
    
    print(f_count(x) + 1)
### BUGGY CODE ###

n, m = map(int, input().split())

g = [[] for _ in range(n)]
indeg = [0 for _ in range(n)]

for _ in range(m):
    x, y = map(int, input().split())
    g[x-1].append(y-1)
    indeg[y-1] += 1

dp = [-1 for _ in range(n)]
q = []

for i in range(n):
    if indeg[i] == 0:
        q.append(i)
        dp[i] = 0

while q:
    v = q.pop()
    for w in g[v]:
        dp[w] = max(dp[w], dp[v]+1)
        q.append(w)

print(max(dp))


### FIXED CODE ###

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

n, m = map(int, input().split())

g = [[] for _ in range(n)]
indeg = [0 for _ in range(n)]

for _ in range(m):
    x, y = map(int, input().split())
    g[x-1].append(y-1)
    indeg[y-1] += 1

dp = [-1 for _ in range(n)]


def LP(v):
    if dp[v] != -1:
        return dp[v]
    ans = 0
    for w in g[v]:
        ans = max(ans, LP(w)+1)
    dp[v] = ans
    return dp[v]


for i in range(n):
    LP(i)

print(max(dp))
### BUGGY CODE ###

h, n = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(n)]
A = [x[1] for x in AB]

DP = [float("inf") for _ in range(h+1)]
DP[0] = 0

for i in range(h):
    for damage, cost in AB:
        next_index = min(i+damage, h)
        DP[next_index] = min(DP[next_index], DP[i]+cost)

print(DP[-1])

### FIXED CODE ###

h, n = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(n)]
A = [x[1] for x in AB]

DP = [float("inf") for _ in range(h+1)]
DP[0] = 0

for i in range(h):
    for damage, cost in AB:
        next_index = min(i+damage, h)
        DP[next_index] = min(DP[next_index], DP[i]+cost)

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

N=int(input())
x=list(map(int,input().split()))
x.sort(reverse=True)
t=[2**i for i in range(len(str(bin(max(x)))[2:])+1)[::-1]]
count=0
for i in range(len(x)):
    if x[i] != 0:
        j=0
        while t[j] > x[i] and j < len(t):
            if t[j]-x[i] in x:
                if t[j]-x[i] != 0 and x.index(t[j]-x[i]) != i:
                    x[x.index(t[j]-x[i])] = 0
                    x[i]=0
                    count+=1
                    break
            j+=1
print(x.count(0)//2)

### FIXED CODE ###

import collections
N=int(input())
x=list(map(int,input().split()))
c=collections.Counter(x)
t=[2**i for i in range(len(str(bin(max(x)*2))[2:])+1)[::-1]]
count=0
start=0
x.sort()
for i in range(len(x))[::-1]:
    for j in range(start,len(t)):
        if t[j] > 2*x[i]:
            start = j
        if t[j] < x[i]:
            break
        if t[j]-x[i] in c.keys():
            if t[j]-x[i] == x[i]:
                if c[x[i]] >= 2:
                    c[x[i]] -= 2
                    count +=1
            else:
                if c[t[j]-x[i]]>0 and c[x[i]]>0:
                    c[t[j]-x[i]] -= 1
                    c[x[i]] -= 1
                    count+=1
print(count)
### BUGGY CODE ###

def gcd(x, y):
  while y:
    x, y = y, x % y
  return x

N = int(input())
A = list(map(int, input().split()))
M = []
for i in range(N):
  AA = A[:i] + A[i + 1:]
  g = 0
  for j in range(len(AA)):
    g = gcd(g, AA[j])
  M.append(g)
print(max(M))

### FIXED CODE ###

def gcd(x, y):
  while y:
    x, y = y, x % y
  return x

N = int(input())
A = list(map(int, input().split()))
L = [0] * N
R = [0] * N
M = [0] * N
L[0] = 0
for i in range(N - 1):
  L[i + 1] = gcd(L[i], A[i])
R[N-1] = 0
for j in range(N - 1):
  R[N - j - 2] = gcd(R[N - j - 1], A[N - j - 1])
for i in range(N):
  M[i] = gcd(L[i], R[i])
print(max(M))
### 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
  
N, M, K = map(int, input().split())

result = 0
mod = 998244353

for k in range(K + 1):
    c = cmb(N - 1, k) % mod
    m = M % mod
    n = (M - 1) ** (N - k - 1) % mod
    result = (result + c * m * n) % mod

print(result)

### FIXED CODE ###

N, M, K = map(int, input().split())

result = 0
p = 998244353
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用


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


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)

for k in range(K + 1):
    c = cmb(N - 1, k, p)
    m = M % p
    n = pow(M - 1, N - k - 1, p)
    result = (result + c * m * n) % p

print(result)
### BUGGY CODE ###

H, W, K = map(int, input().split())
HW = [list(map(int, list(input()))) for _ in range(H)]

def blocks(hw):
    score = 0
    blank = -1
    flg = True
    delcnt = 0
    while flg:
        flg = False
        for h in range(H):
            cnt = 1
            old = hw[h][:]
            for w in range(1, W):
                if hw[h][w-1]==hw[h][w]:
                    cnt+=1
                    flg = True
                else:
                    if cnt>=K:
                        score += 2**delcnt*cnt*hw[h][w-1]
                        for k in range(1, cnt+1):
                            hw[h][w-k] = blank
                            blank -= 1
                    cnt = 1
            if cnt>=K:
                score += 2**delcnt*cnt*hw[h][W-1]
                for k in range(1, cnt+1):
                    hw[h][W-k] = blank
                    blank -= 1
        fall_flg = True
        while fall_flg:
            fall_flg = False
            for h in range(H-1, 0, -1):
                for w in range(W):
                    if hw[h-1][w]>0 and hw[h][w]<=0:
                        hw[h][w] = hw[h-1][w]
                        hw[h-1][w] = blank
                        blank -= 1
                        fall_flg = True
        delcnt += 1
    return score
import copy
ans = []
for h in range(1, H):
    for w in range(W):
        hw = copy.deepcopy(HW)
        for i in range(H-h, 0, -1):
            hw[i][w] = hw[i-1][w]
        hw[0][w] = 0
        ans.append(blocks(hw))
print(max(ans))

### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**5)
H, W, K = map(int, input().split())
HW = [list(map(int, list(str(input().strip())))) for _ in range(H)]

def blocks(hw):
    score = 0
    ret = 1
    delcnt = 0
    while ret:
        ret = check(delcnt, hw)
        score += ret
        delcnt += 1
    return score

def check(delcnt, hw):
    s = 0
    blank = -1
    for h in range(H):
        cnt = 1
        old = hw[h][:]
        for w in range(1, W):
            if hw[h][w-1]==hw[h][w]:
                cnt+=1
                flg = True
            else:
                if cnt>=K:
                    s += cnt*hw[h][w-1]
                    for k in range(1, cnt+1):
                        hw[h][w-k] = blank
                        blank -= 1
                cnt = 1
        if cnt>=K:
            s += cnt*hw[h][W-1]
            for k in range(1, cnt+1):
                hw[h][W-k] = blank
                blank -= 1
    for w in range(W):
        cnt = 1
        for h in range(H-1, -1, -1):
            item = hw[h][w]
            hw[h][w] = blank
            blank -= 1
            if item>0:
                hw[H-cnt][w] = item
                cnt += 1
    return 2**delcnt*s

import copy
ans = []
if K>=4:
    print(0)
else:
    for h in range(1, H):
        for w in range(W):
            hw = copy.deepcopy(HW)
            for i in range(H-h, 0, -1):
                hw[i][w] = hw[i-1][w]
            hw[0][w] = 0
            ans.append(blocks(hw))
print(max(ans))
### BUGGY CODE ###

N, D, A = map(int, input().split())
monster = []
for k in range(N):
  monster.append(list(map(int, input().split())))
monster.sort(key = lambda x: x[0])
ans = 0
for k in range(N):
  if monster[k][1] > 0:
    nowx = monster[k][0]
    damage = ((monster[k][1]-0.1)//A)*A + A
    ans += int((monster[k][1]-0.1)//A + 1)
    for j in range(k, N):
      if monster[j][0] <= nowx + 2*D:
        monster[j][1] -= damage
        continue
      else:
        break

print(ans)


### FIXED CODE ###

N, D, A = map(int, input().split())
monster = []
for k in range(N):
  monster.append(list(map(int, input().split())))
monster.sort(key = lambda x: x[0])
for k in range(N):
  monster[k][1] = int((monster[k][1]-0.1)//A + 1)
ans = 0
"""
k = 0
while k < len(monster):
  if monster[k][1] > 0:
    nowx = monster[k][0]
    damage = monster[k][1]
    ans += monster[k][1]
    j = 0 + k
    nextk = N
    while(j +1 < len(monster)):
      j += 1
      if monster[j][0] <= nowx + 2*D:
        monster[j][1] -= damage
        if monster[j][1] > 0:
          nextk = min(j, nextk)
          continue
      else:
        nextk = min(nextk, j)
        break
    k = nextk
"""
final = monster[-1][0]
ruiseki = 0
minuslist = []
j = 0
for k in range(N):
  while (j < len(minuslist)):
    if monster[k][0] >= minuslist[j][0]:
      ruiseki -= minuslist[j][1]
      j += 1
    else:
      break
  if ruiseki < monster[k][1]:
    ans += monster[k][1] - ruiseki
    if monster[k][0] + 2*D +1 <= final:
      minuslist.append([monster[k][0]+2*D+1, monster[k][1] - ruiseki])
    ruiseki = monster[k][1]


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

def main():
    import math
    a, b, n = map(int, input().split())
    ans = 0

    for x in range(n, 0, -1):
        fx = math.floor(a * x / b) - math.floor(x / b) * a
        #print(fx)
        if ans < fx:
            ans = fx
        if ans > fx + 10 ** 3:
            #exit()
            pass
    print(ans)

if __name__ == "__main__":
    main()

### FIXED CODE ###


def main():
    import math
    a, b, n = map(int, input().split())
    if n >= b:
        ans = math.floor(a * (b-1)/b)
    else:
        ans = math.floor(a * n / b)
    
    print(ans)
    




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

import sys
import bisect

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

N = ir()
A = []
for _ in range(N):
    a = ir()
    i = bisect.bisect_left(A, a)
    if i == 0:
        A.insert(0, a)
    else:
        A[i-1] = a

print(len(A))
# 14

### FIXED CODE ###

import sys
import bisect

stdin = sys.stdin
 
ri = lambda: int(rs())
rl = lambda: list(map(int, stdin.readline().split()))
rs = lambda: stdin.readline().rstrip()  # ignore trailing spaces

N = ri()
INF = 10 ** 18
A = [10 ** 10 - ri() for _ in range(N)]
dp = [INF] * (N+1)
for a in A:
    i = bisect.bisect_right(dp, a)
    dp[i] = a

print(bisect.bisect_left(dp, INF))
#39 答え見る
### BUGGY CODE ###



from fractions import gcd
from functools import reduce # reduceの使い方覚える、ついでにaccumulateも

def divider(numbers):
  return reduce(gcd, numbers)

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

result = []
for i in range(n):
  numbers = A[:]
  numbers.pop(i)
  result.append(divider(numbers))
print(max(result))

### FIXED CODE ###

# 参考1: https://atcoder.jp/contests/abc125/submissions/8965716
# 参考2: https://qiita.com/hkrutknouch/items/e71488de4a0c8e83ee97

from fractions import gcd
from itertools import accumulate

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

left = list(accumulate(A, gcd))
right = list(accumulate(A[::-1], gcd))[::-1]

ans = 0
for i in range(n):
  if i == 0:
    tmp = right[1]
  elif i == n - 1:
    tmp = left[-2]
  else:
    tmp = gcd(left[i-1], right[i+1])
  ans = max(ans, tmp)

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

N,M= map(int,input().split())
A = list(map(int,input().split()))
A.sort()
BClis = [list(map(int, input().split())) for i in range(M)]
m = 0 
for i in range(M):
  A.sort()
  for j in range(BClis[i][0]):
    if  A[j] < BClis[i][1]:
      A[j] = BClis[i][1]
print(sum(A))

### FIXED CODE ###

N, M = map(int, input().split())
a = list(map(int, input().split()))
bc = [tuple(map(int, input().split())) for _ in range(M)]
bc.sort(key=lambda x: -x[1])
rest = N
for b, c in bc:
  a += [c] * min(rest, b)
  rest -= min(rest, b)
a.sort(reverse=True)
print(sum(a[:N]))
### BUGGY CODE ###

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees#, log2
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10**9 + 7

H, N = MAP()
A, B = [0]*N, [0]*N
for i in range(N):
	A[i], B[i] = MAP()

dp = [[INF]*(H+1) for _ in range(N+1)]
dp[0][0] = 0


for i in range(N):
	for j in range(H+1):
		if j < A[i]:
			dp[i+1][j] = min(dp[i][j], B[i])
		if j>= A[i]:
			dp[i+1][j] = min(dp[i][j], dp[i][j-A[i]]+B[i], min([dp[i+1][j-A[i]*x] + B[i]*x for x in range(1, j//A[i] + 1)]))
			

#for i in range(N+1):
#	print(dp[i])

print(dp[N][H])



### FIXED CODE ###

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees#, log2
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10**9 + 7

def main():
	H, N = MAP()
	A, B = [0]*N, [0]*N
	for i in range(N):
		A[i], B[i] = MAP()

	dp = [[INF]*(H+1) for _ in range(N+1)]
	dp[0][0] = 0


	for i in range(N):
		for j in range(H+1):
			if j < A[i]:
				dp[i+1][j] = min(dp[i][j], B[i])
			if j>= A[i]:
				dp[i+1][j] = min(dp[i][j], dp[i+1][j-A[i]]+B[i])
			

	#for i in range(N+1):
	#	print(dp[i])

	print(dp[N][H])

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

import copy
n = int(input())
a = list(map(int,[input() for i in range(n)]))
a_copy = copy.copy(a)

for i in range(n):
  a=copy.copy(a_copy)
  a.remove(a[i])
  print(max(a))

### FIXED CODE ###

N = int(input())
A = []
for i in range(N):
    A.append(int(input()))
max_A = max(A)
max_num = 0
for i in range(N):
    if A[i] == max_A:
        # 最大値が複数ある場合の計算削減
        max_num += 1
        if max_num > 1:
            print(max_A)
        else:
            print(max(A[:i] + A[i + 1:]))
    else:
        print(max_A)
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
C = list(map(int,input().split()))
ans = 0
for i in range(N):
    count_A = len([0 for j in range(N) if A[j] < B[i]])
    count_C = len([0 for j in range(N) if C[j] > B[i]])
    ans += count_A*count_C
print(ans)

### FIXED CODE ###

import bisect

N = int(input())
A = sorted(list(map(int,input().split())))
B = list(map(int,input().split()))
C = sorted(list(map(int,input().split())))
ans = 0
for x in B:
    ai = bisect.bisect_left(A,x)
    ci = bisect.bisect_right(C,x)
    ans += (ai*(N-ci))
print(ans)
### BUGGY CODE ###

def func(n):
    ans = 0
    while n > 0:
        cnt = 0
        for i in range(65):
            if (n & (1<<i)) != 0:
                cnt += 1
        ans += 1
        n %= cnt
    return ans

def main():
    n = int(input())
    s = input()
    ans = [0]*n
    cnt = 0
    for c in s:
        if c == "1":
            cnt += 1
    ad = cnt + 1
    df = cnt - 1
    start_ad = 0
    start_df = 0
    for i in range(n):
        if ad > 0:
            if s[n-1-i] == "1":
                start_ad += pow(2, i, ad)
                start_ad %= ad
        if df > 0:
            if s[n-1-i] == "1":
                start_df += pow(2, i, df)
                start_df %= df
    for i in range(n):
        if s[i] == "0":
            ans[i] = 1
            tmp = (start_ad + pow(2, n-1-i, ad)) % ad
            ans[i] += func(tmp)
        else:
            if cnt == 1:
                ans[i] = 0
            else:
                ans[i] = 1
                tmp = (start_df - pow(2, n-1-i, df)) % df
                ans[i] += func(tmp)
    for v in ans:
        print(v)

if __name__ == "__main__":
    main()

### FIXED CODE ###

def func(n):
    ans = 0
    while n > 0:
        cnt = 0
        for i in range(33):
            if (n & (1<<i)) != 0:
                cnt += 1
        ans += 1
        n %= cnt
    return ans

def main():
    n = int(input())
    s = input()
    ans = [0]*n
    cnt = 0
    for c in s:
        if c == "1":
            cnt += 1
    ad = cnt + 1
    df = cnt - 1
    start_ad = 0
    start_df = 0
    for i in range(n):
        if ad > 0:
            if s[n-1-i] == "1":
                start_ad += pow(2, i, ad)
                start_ad %= ad
        if df > 0:
            if s[n-1-i] == "1":
                start_df += pow(2, i, df)
                start_df %= df
    for i in range(n):
        if s[i] == "0":
            ans[i] = 1
            tmp = (start_ad + pow(2, n-1-i, ad)) % ad
            ans[i] += func(tmp)
        else:
            if cnt == 1:
                ans[i] = 0
            else:
                ans[i] = 1
                tmp = (start_df - pow(2, n-1-i, df)) % df
                ans[i] += func(tmp)
    for v in ans:
        print(v)

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

import sys
input = sys.stdin.readline
from operator import itemgetter

N, M = map(int,input().split())
work_list = [list(map(int, input().split())) for i in range(N)]

#sort by hosyu
work_list.sort(key=itemgetter(1), reverse=True)
sum = 0
workdays = [0] * (M+1)

for day, reward in work_list:
    latest = M - day
    while -1 < latest:
        if workdays[latest] == 0:
            sum += reward
            workdays[latest] = 1
            break
        else:
            latest -= 1

print(sum)


### FIXED CODE ###

import sys
input = sys.stdin.readline
from heapq import heappop, heappush

N, M = map(int,input().split())
work_list = [[] for j in range(M+1)]
for i in range(N):
    temp = list(map(int,input().split()))
    if temp[0] > M:
        continue
    work_list[temp[0]].append(temp[1])

sum = 0
works = []

for i in work_list:
    for j in i:
        heappush(works, -1*j)
    if len(works) == 0:
        continue
    sum -= (heappop(works))

print(sum)