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

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time,random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)


def main():
    a,b = LI()
    g = fractions.gcd(a,b)
    s = set([1])
    while g % 2 == 0:
        s.add(2)
        g //= 2
    t = 3
    while g > t:
        while g % t == 0:
            s.add(t)
            g //= t
        t += 2
    s.add(g)

    return len(s)


print(main())





### FIXED CODE ###

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time,random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)


def main():
    a,b = LI()
    g = fractions.gcd(a,b)
    s = set([1])
    while g % 2 == 0:
        s.add(2)
        g //= 2
    t = 3
    ss = int(g**0.5) + 1
    while g > t and t < ss:
        while g % t == 0:
            s.add(t)
            g //= t
        t += 2
    s.add(g)

    return len(s)


print(main())
### BUGGY CODE ###

# -*- coding: utf-8 -*-

def solve():
    N, M = map(int, input().split())
    *S, = map(int, input().split())
    *T, = map(int, input().split())
    dp = [[[0]*3 for _ in range(M+1)] for _ in range(2)]
    k,l = 0,1
    for j, s in enumerate(S, start=1):
        k,l = l,k
        for i, t in enumerate(T, start=1):
            dp[k][i] = [sum(dp[l][i]), sum(dp[k][i-1][1:]), sum(dp[l][i-1]) + 1 if t == s else 0]
    res = (sum(dp[N%2][-1]) + 1)%(10**9+7)

    return str(res)

if __name__ == '__main__':
    print(solve())


### FIXED CODE ###

# -*- coding: utf-8 -*-
def solve():
    N, M = map(int, input().split())
    S = map(int, input().split())
    *T, = map(int, input().split())
    dp = [1]*(M+1)
    for s in S:
        is_s = s.__eq__
        dp_ = dp[:]
        acc = 0
        for i, t in enumerate(T):
            if is_s(t):
                acc += dp_[i]
            dp[i+1] = dp_[i+1] + acc
    res = (dp[-1])%(10**9+7)
    return str(res)

if __name__ == '__main__':
    print(solve())
### BUGGY CODE ###

import numpy as np
import heapq
import sys
sys.setrecursionlimit(10**6)

H,W = map(int,input().split())
INF = 10**18
q = []

d = [[INF]*W for _ in range(H)] # '#'からの距離

for i in range(H):
  txt = input()
  for j,c in enumerate(txt):
    if c == '#':
      d[i][j] = 0
      heapq.heappush(q,(0,i,j))

      
ans = 0
while q:
  dv,x,y = heapq.heappop(q)
  for dx,dy in [(0,1),(0,-1),(1,0),(-1,0)]:
    xx = x+dx
    yy = y+dy
    if xx == -1 or xx == H:
      continue
    if yy == -1 or yy == W:
      continue
    if d[xx][yy] == INF:
      d[xx][yy] = dv+1
      ans = dv+1
      heapq.heappush(q,(dv+1,xx,yy))

print(ans)


### FIXED CODE ###

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

H,W = map(int,input().split())
INF = 10**18
q = []

visited = [[True]*(W+2)]
visited += [[True] + [x == '#' for x in input().rstrip()] + [True] for _ in range(H)]
visited.append([True]*(W+2))
  
for i in range(1,H+1):
  for j in range(1,W+1):
    if visited[i][j]:
      q.append((i,j))

moves = [(0,1),(0,-1),(1,0),(-1,0)]

ans = -1
while q:
  qq = []
  ans += 1
  for x,y in q:
    if not visited[x-1][y]:
      visited[x-1][y] = True
      qq.append((x-1,y))
    if not visited[x+1][y]:
      visited[x+1][y] = True
      qq.append((x+1,y))
    if not visited[x][y-1]:
      visited[x][y-1] = True
      qq.append((x,y-1))
    if not visited[x][y+1]:
      visited[x][y+1] = True
      qq.append((x,y+1))
  q = qq
  
print(ans)
### BUGGY CODE ###

n = int(input())
*A, = map(int, input().split())
a, b, c = A.count(1), A.count(2), A.count(3)
DP = [[[0.0 for k in range(n+1)] for j in range(n+1)] for i in range(n+1)]
for k in range(n+1):
    for j in range(n-k+1):
        for i in range(n-k-j+1):
            if i+j+k == 0:
                continue
            DP[i][j][k] = n
            if i > 0:
                DP[i][j][k] += DP[i-1][j][k]*i
            if j > 0:
                DP[i][j][k] += DP[i+1][j-1][k]*j
            if k > 0:
                DP[i][j][k] += DP[i][j+1][k-1]*k
            DP[i][j][k] /= (i+j+k)
print(DP[a][b][c])


### FIXED CODE ###

n = int(input())
*A, = map(int, input().split())
a, b, c = A.count(1), A.count(2), A.count(3)
DP = [[[0.0 for k in range(n+1)] for j in range(n+1)] for i in range(n+1)]
for k in range(c+1):
    for j in range(b+c-k+1):
        for i in range(n-j-k+1):
            if i+j+k == 0:
                continue
            tmp = n
            if i > 0:
                tmp += DP[i-1][j][k]*i
            if j > 0:
                tmp += DP[i+1][j-1][k]*j
            if k > 0:
                tmp += DP[i][j+1][k-1]*k
            DP[i][j][k] = tmp/(i+j+k)
print(DP[a][b][c])
### BUGGY CODE ###

from scipy.sparse.csgraph import floyd_warshall
from collections import defaultdict

N, X, Y = map(int, input().split())


nei_graph = [[0] * N for _ in range(N)]


for a in range(N):
    if a == N - 1:
        break

    nei_graph[a][a + 1] = 1
    nei_graph[a + 1][a] = 1


nei_graph[X - 1][Y - 1] = 1
nei_graph[Y - 1][X - 1] = 1

nei_graph = floyd_warshall(nei_graph)

dic = defaultdict(int)
for i in range(N):
    for j in range(i + 1, N):
        w = nei_graph[i][j]

        dic[w] += 1

for i in range(1, N):
    print(dic[i])


### FIXED CODE ###

N, X, Y = map(int, input().split())


dic = {}

X = X - 1
Y = Y - 1

for i in range(N):
    for j in range(i + 1, N):
        if i <= X and Y <= j:
            v = X - i + 1 + j - Y
        elif (i <= X) and (X <= j and j <= Y):
            v = min(j - i, X - i + 1 + Y - j)
        elif (X <= i and i <= Y) and Y <= j:
            v = min(j - i, i - X + 1 + j - Y)
        elif (X <= i and i <= Y) and (X <= j and j <= Y):
            v = min(j - i, i - X + 1 + Y - j)
        else:
            v = j - i

        if v in dic:
            dic[v] += 1
        else:
            dic[v] = 1


for i in range(1, N):
    if i in dic:
        print(dic[i])
    else:
        print(0)
### BUGGY CODE ###

def len_LCS(X,Y):
    Z = X
    if len(X) > len(Y): Z,Y = Y,X
    D = {}
    def len_LCS_core(Z,Y):
        if Z in D: return D[Z]
        if Z in Y:
            D[Z] = len(Z)
            return D[Z]
        D[Z] = 0
        if len(Z) < 2: return 0
        for i in range(len(Z)):
            D[Z] = max(D[Z], len_LCS_core(Z[:i]+Z[i+1:],Y))
        return D[Z]
    return len_LCS_core(Z,Y)
        
if __name__=='__main__':
    n = int(input())
    for _ in range(n):
        X = input()
        Y = input()
        print(len_LCS(X,Y))

### FIXED CODE ###

def len_LCS(X,Y):
    lcs_row = [0 for _ in range(len(X)+1)]
    for yc in Y:
        lcs_row_p = lcs_row[:]
        # lcs_row_p: [i] [i+1]
        # lcs_row  : [i] [i+1]
        for (i,xc) in enumerate(X):
            if xc == yc:
                lcs_row[i+1] = lcs_row_p[i] + 1
            elif lcs_row[i] > lcs_row_p[i+1]:
                lcs_row[i+1] = lcs_row[i]
    return lcs_row[-1]
        
if __name__=='__main__':
    n = int(input())
    for _ in range(n):
        X = input()
        Y = input()
        print(len_LCS(X,Y))
### BUGGY CODE ###

import numpy as np
(n,k),p = [list(map(int, s.split())) for s in open(0)]
p = np.array(p)

p_isordered = p[1:]>p[:-1]
p_cumsum = p_isordered.cumsum()

ans = n - k + 1
no_change = False
if p_cumsum[k-2]==k-1:
    no_change = True

for i in range(n-k):
    dec = False
    q = p[i:i+k+1]
    if (q.argmin()==0 and q.argmax()==k):
        ans -= 1
        dec = True
    
    if p_cumsum[i]+k-1 == p_cumsum[i+k-1]:
        if no_change and not dec:
            ans -= 1
        no_change = True

print(ans)

### FIXED CODE ###

import numpy as np
import heapq

(n,k),p = [list(map(int, s.split())) for s in open(0)]

p_np = np.array(p)
p_cumsum = (p_np[1:]>p_np[:-1]).cumsum()

c = [False] * n

_min = p[:k].copy()
_max = [-x for x in p[:k]]
heapq.heapify(_min)
heapq.heapify(_max)

ans = n - k + 1
no_change = False
if p_cumsum[k-2]==k-1:
    no_change = True

for i in range(n-k):
    decrease = False
    
    heapq.heappush(_min, p[i+k])
    heapq.heappush(_max, -p[i+k])
    
    while c[_min[0]]:
        heapq.heappop(_min)
    while c[-_max[0]]:
        heapq.heappop(_max)
    
    if (_min[0]==p[i] and -_max[0]==p[i+k]):
        ans -= 1
        decrease = True
    
    c[p[i]] = True
    
    if p_cumsum[i]+k-1 == p_cumsum[i+k-1]:
        if no_change and not decrease:
            ans -= 1
        no_change = True

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

# E - Flatten

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

modulus = 10 ** 9 + 7
MAX = 10 ** 6

primefact = [0 for i in range(MAX + 1)]

def sieve():
    # cf. https://www.geeksforgeeks.org/lcm-of-n-numbers-modulo-m/
    for i in range(2, MAX + 1):
        if primefact[i] == 0:
            for j in range(i, MAX + 1, i):
                if primefact[j] == 0:
                    primefact[j] = i

def factorize(x):
    if primefact[2] == 0:
        sieve()

    vec = {}
    while x >= 2:
        d = primefact[x]
        if d not in vec:
            vec[d] = 0
        vec[d] += 1
        x //= d
    return vec

def lcm(x, y):
    vec = {i: x[i] for i in x}
    for i in y:
        vec[i] = max(x[i] if i in x else 0, y[i])
    return vec

def div(x, y):
    vec = {i: x[i] for i in x}
    for i in y:
        vec[i] -= y[i]
    return vec

def value(x):
    p = 1
    for i in x:
        p = (p * (i ** x[i])) % modulus
    return p

fact = [factorize(x) for x in a]

l = {}
for f in fact:
    l = lcm(l, f)

s = sum(value(div(l, f)) for f in fact) % modulus
print(s)


### FIXED CODE ###

# E - Flatten

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

modulus = 10 ** 9 + 7
binmod = (bin(modulus - 2))[2:]  # modulus - 2 in binary

MAX = 10 ** 6

primefact = [0 for i in range(MAX + 1)]

def sieve():
    # cf. https://www.geeksforgeeks.org/lcm-of-n-numbers-modulo-m/
    for i in range(2, MAX + 1):
        if primefact[i] == 0:
            for j in range(i, MAX + 1, i):
                if primefact[j] == 0:
                    primefact[j] = i

def factorize(x):
    if primefact[2] == 0:
        sieve()

    vec = {}
    while x >= 2:
        d = primefact[x]
        if d not in vec:
            vec[d] = 0
        vec[d] += 1
        x //= d
    return vec

def value(x):
    p = 1
    for i in x:
        p = (p * (i ** x[i])) % modulus
    return p

def inverse(x):
    p = 1
    for b in binmod:
        p = p * p % modulus
        if b == '1':
            p = p * x % modulus
    return p

def div(n, d):
    return n * inverse(d) % modulus

fact = [factorize(x) for x in a]

fset = set()
for f in fact:
    fset.update(f.keys())

l = {k: 0 for k in fset}
for f in fact:
    for k in f:
        l[k] = max(l[k], f[k])
lcm = value(l)

s = sum(div(lcm, x) for x in a) % modulus
print(s)
### BUGGY CODE ###

import itertools
n,k=map(int,input().split())
l=[]
for i in range(n):
    l.append(list(map(int,input().split())))
c=itertools.combinations(range(n),k)
ans=1e25
for i in c:
    ax=-1e11
    ix=1e11
    ay=-1e11
    iy=1e11
    for j in i:
        ax=max(ax,l[j][0])
        ix=min(ix,l[j][0])
        ay=max(ay,l[j][1])
        iy=min(iy,l[j][1])
    ans=min(ans,(ax-ix)*(ay-iy))
print(ans)


### FIXED CODE ###

import itertools
n,k=map(int,input().split())
l=[]
for i in range(n):
    l.append(list(map(int,input().split())))
c=itertools.combinations(range(n),2)
d=itertools.combinations(range(n),2)
ans=10**25
for i0 in range(n):
    for i1 in range(i0,n):
        for j0 in range(n):
            for j1 in range(j0,n):
                i=[i0,i1]
                j=[j0,j1]
                #print(i,j)
                lx=min(l[i[0]][0],l[i[1]][0])
                rx=max(l[i[0]][0],l[i[1]][0])
                dy=min(l[j[0]][1],l[j[1]][1])
                uy=max(l[j[0]][1],l[j[1]][1])
                tk=0
                for p in l:
                    if lx<=p[0]<=rx and dy<=p[1]<=uy:
                        tk+=1
                if tk>=k:
                    ans=min(ans,(uy-dy)*(rx-lx))
print(ans)
### BUGGY CODE ###

from fractions import gcd

N,M=map(int,input().split())
List=list(map(lambda x:int(x)/2,input().split()))

LCM=1
for i in List:
    LCM*=i/gcd(LCM,i)

for i in List:
    if LCM/i%2==0:
        print("0")
        exit()

print(int(M//(LCM*2)+M%(LCM*2)//LCM))

### FIXED CODE ###

from fractions import gcd
import sys
input = sys.stdin.readline

N,M=map(int,input().split())
List=list(map(lambda x:int(x)//2,map(int, set(input().split()))))

def main():
    LCM=1

    for i in List:
        LCM*=i//gcd(LCM,i)

    for i in List:
        if LCM//i%2==0:
            print(0)
            exit()

    print(int(M//(LCM*2)+M%(LCM*2)//LCM))


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

n, m = map(int, input().split())
d = []
for i in range(m):
    a, b = map(int, input().split())
    d.append(list(range(a, b+1)))

b = d[0]
for i in d:
    src_set = set(b)
    tag_set = set(i)
    matched_list = list(src_set & tag_set)

print(len(matched_list))

### FIXED CODE ###

n,m=map(int,input().split())
max_ = 0
min_ = n+1
for i in range(m):
  a,b=map(int, input().split())
  max_ = max(max_, a)
  min_ = min(min_, b)
#print(max_, min_)
if(min_ < max_):print(0)
else:print(min_-max_+1)
### BUGGY CODE ###

a,b,c,k=map(int, input().split())
ans=0
for i in range(k):
    if a>0:
        ans+=1
        a-=1
    elif b>0:
        b-=1
    elif c>0:
        ans-=1
        c-=1
print(ans)

### FIXED CODE ###

a,b,c,k=map(int, input().split())
ans=0
if a>=k:
    print(k)
    exit()
if b>=k-a:
    print(a)
    exit()
else:
    print(a-(k-b-a))
    exit()
### BUGGY CODE ###

from collections import deque
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

N, M = map(int, input().split())
e_from = [set([]) for _ in range(N+1)]
e_to = [set([]) for _ in range(N+1)]
for _ in range(N + M - 1):
    a, b = map(int, input().split())
    e_from[a].add(b)
    e_to[b].add(a)


rank = [-1] * (N + 1)  # 親のノード番号
seen = set([])  # 既に確定したノード

# まず根を探す
for i in range(1, N+1):
    if len(e_to[i]) == 0:
        root = i
        break

# BFS
seen.add(root)
rank[root] = 0
node = deque([root])
while node:
    s = node.popleft()
    for t in e_from[s]:
        if len(e_to[t] - seen) == 0:
            rank[t] = s
            seen.add(t)
            node.append(t)

print(*rank[1:], sep="\n")


### FIXED CODE ###

from collections import deque
import numpy as np
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

N, M = map(int, input().split())
e_from = [[] for _ in range(N+1)]
e_to = [[] for _ in range(N+1)]
for _ in range(N + M - 1):
    a, b = map(int, input().split())
    e_from[a].append(b)
    e_to[b].append(a)


add = np.zeros(N+1, dtype=int)
rank = [-1]*(N+1)

# まず根を探す
for i in range(1, N+1):
    add[i] = len(e_to[i])
    if len(e_to[i]) == 0:
        root = i

# BFS
rank[root] = 0
node = deque([root])
while node:
    s = node.popleft()
    add[e_from[s]] -= 1
    for t in e_from[s]:
        if add[t] == 0:
            rank[t] = s
            node.append(t)

print(*rank[1:], sep="\n")
### BUGGY CODE ###

import copy
S=list(input())
while len(S)>0:
    if S[0:7]==['d','r','e','a','m','e','r'] and (len(S)==7 or S[7]!='a'):
        for _ in range(7):
            S.pop(0)
    elif S[0:5]==['d','r','e','a','m']:
        for _ in range(5):
            S.pop(0)
    elif S[0:6]==['e','r','a','s','e','r']:
        for _ in range(6):
            S.pop(0)
    elif S[0:5]==['e','r','a','s','e']:
        for _ in range(5):
            S.pop(0)
    else:
        print('NO')
        exit()
print('YES')


### FIXED CODE ###

S=list(input())
i=0
while i!=len(S):
    if i+6<=len(S) and S[i:i + 6] == ['e', 'r', 'a', 's', 'e', 'r']:
        i += 6
    elif i+5<=len(S) and S[i:i+5]==['e','r','a','s','e']:
        i+=5
    elif i+7<=len(S) and S[i:i+7]==['d','r','e','a','m','e','r'] and (len(S[i:])==7 or (S[i+7]!='a')):
        i+=7
    elif i+5<=len(S) and S[i:i+5]==['d','r','e','a','m']:
        i+=5
    else:
        print('NO')
        exit()
print('YES')
### BUGGY CODE ###

N = 60
MOD = 10**9 + 7
n = int(input())
l = [[] for _ in range(n)]
c1 = [0 for _ in range(N)]
c0 = [0 for _ in range(N)]

a = list(map(int,input().split()))
for i in range(n):
    for j in range(N):
        if a[i] & (1 << j) != 0:
            c1[j] += 1
            l[i].append(True)
        else:
            c0[j] += 1
            l[i].append(False)

ans = 0
for i in range(n-1):
    for j in range(N):
        if l[i][j]:
            c1[j] -=1
        else:
            c0[j] -=1
    for j in range(N):
        if l[i][j]:
            ans += (1<<j) * c0[j]
        else:
            ans += (1<<j) * c1[j]

print(ans % MOD)

### FIXED CODE ###

N = 60
MOD = 10**9 + 7
n = int(input())
# c1 = [0 for _ in range(N)]
c1 = [0 for _ in range(N)]

a = list(map(int,input().split()))
for i in range(n):
    for j in range(N):
        if a[i] & (1 << j) != 0:
            c1[j] += 1
        # else:
        #     c1[j] += 1

ans = 0
for i in range(n-1):
    for j in range(N):
        if a[i] & (1 << j) != 0:
            c1[j] -=1
        # else:
        #     c0[j] -=1
    for j in range(N):
        if a[i] & (1 << j) != 0:
            ans += (1<<j) * (n-i-1-c1[j])
        else:
            ans += (1<<j) * c1[j]
            #ans += (1<<j) * c1[j]

print(ans % MOD)
### BUGGY CODE ###

N,K=map(int,input().split())
A=list(map(int,input().split()))
A.sort()
#A[num]が必要な数か判定
def condition(num):
    if N-1>num:
        test=A[:num]+A[num+1:]
    else:
        test=A[:num]
    if A[num]>=K:
        return True
    else:
        dp=[False for i in range(0,K)]
        for i in range(K-A[num],K):
            dp[i]=True

        for i in range(1,N):
            for j in range(0,K-test[i-1]):
                if dp[j+test[i-1]]:
                    dp[j]=True
        return dp[0]

#必要な数のうち最小のもの
if N==1:
    if A[0]>=K:
        print(0)
    else:
        print(1)
else:
    start=0
    end=N-1
    while end-start>1:
        t=(end+start)//2
        if condition(t):
            end=t
        else:
            start=t

    if condition(start):
        print(start)
    elif condition(end):
        print(end)
    else:
        print(N)

### FIXED CODE ###

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

l=N
for i in range(0,N):
    if A[i]>=K:
        l=i
        break
A=A[:l]
N=l
#A[num]が必要な数か判定
def condition(num):
    if N-1>num:
        test=A[:num]+A[num+1:]
    else:
        test=A[:num]
    if A[num]>=K:
        return True
    else:
        check=0
        for i in range(K-A[num],K):
            check+=pow(2,i)

        for i in range(1,N):
            check=check|(check>>test[i-1])

        return check%2==1
        

#必要な数のうち最小のもの
if N==0:
    print(0)
elif N==1:
    if A[0]>=K:
        print(0)
    else:
        print(1)
else:
    start=0
    end=N-1
    while end-start>1:
        t=(end+start)//2
        if condition(t):
            end=t
        else:
            start=t

    if condition(start):
        print(start)
    elif condition(end):
        print(end)
    else:
        print(N)
### BUGGY CODE ###

import heapq
N,M=list(map(int,input().split()))
A=list(map(int,input().split()))
A=[-A[i] for i in range(N)]
heapq.heapify(A)
for i in range(M):
    a=A[0]
    heapq.heappop(A)
    heapq.heappush(A,-(a//-2))
    heapq.heapify(A)
print(-sum(A))

### FIXED CODE ###

import heapq
N,M=list(map(int,input().split()))
A=list(map(int,input().split()))
A=[-A[i] for i in range(N)]
heapq.heapify(A)
for i in range(M):
    a=A[0]
    heapq.heappop(A)
    heapq.heappush(A,-(a//-2))
print(-sum(A))
### BUGGY CODE ###

N, Q = map(int, input().split())
S = input()

for i in range(Q):
    left, right = map(int, input().split())
    print(len(S[left-1:right].split("AC"))-1)


### FIXED CODE ###

import collections

N, Q = map(int, input().split())
S = input()

new_S = S.replace("AC", "12")


count_one_list = [0] * len(S)
for i in range(len(S)-1):
    if new_S[i] == '1' and i == 0:
        count_one_list[i+1] += 1
    elif new_S[i] == '1':
        count_one_list[i+1] = count_one_list[i] + 1
    else:
        count_one_list[i+1] = count_one_list[i]
# count_one_list = [new_S[:i].count('1') for i in range(len(S))]
# print(count_one_list)

for i in range(Q):
    left, right = map(int, input().split())
    count_one = count_one_list[right-1] - count_one_list[left-1]
    print(count_one)
### BUGGY CODE ###

import sys
inputs = sys.stdin.readline
N, Q= map(int,inputs().split())
V = [list(map(int,inputs().split())) for p in [0]*N]
M = [int(inputs()) for p in [0]*Q]
V.sort(key = lambda x:(x[2]))

for m in M:
	for v in V:
		if v[0] - v[2] <=m and m <= v[1] - v[2] -1:
			print(v[2])
			break
	else:
		print(-1)

### FIXED CODE ###

import sys
from operator import itemgetter
def main():
	inputs = sys.stdin.readline
	N, Q= map(int,inputs().split())
	E = [None]*2*N
	for n in range(N):
		a,b,c = map(int,inputs().split())
		E[2*n] = (a - c, 1, c)
		E[2*n + 1] = (b - c, -1, c)
	E.sort(key=itemgetter(0))
	tuple(tuple(E))
	mini = 1000000001
	kouho = {1000000001}
	my_add = kouho.add
	my_discard = kouho.discard
	q = 0
	d = int(inputs())
	flag = False
	cont = False
	for e in E:
		while e[0] > d:
			if cont == True:
				print(mini-(mini//1000000001)*1000000002)
			else:
				mini = min(kouho)
				print(mini-(mini//1000000001)*1000000002)
			cont = True
			q = q + 1
			if q > Q-1:
				flag = True
				break
			d = int(inputs())
		if flag == True:
			break
		if e[1] == 1:
			my_add(e[2])
			if mini > e[2]:
				mini = e[2]
		elif e[1] == -1:
			my_discard(e[2])
			if mini == e[2]:
				cont = False
	for t in [None]*(Q-q):
		print(-1)
main()
### BUGGY CODE ###

N,H = map(int,input().split())
Ma = 1
B = []
for i in range(N):
    a,b = map(int,input().split())
    B.append(b)
    if a > Ma:
        Ma = a
C = 0
while H > 0:
    if B == []:
        C += int(-(-H//Ma))
        H = 0
    else:
        Mb = max(B)
        if Ma >= Mb:
            C += int(-(-H//Ma))
            H = 0
        else:
            C += 1
            H -= Mb
            B.remove(Mb)
print(C)

### FIXED CODE ###

N,H = map(int,input().split())
Ma = 1
B = []
for i in range(N):
    a,b = map(int,input().split())
    B.append(b)
    if a > Ma:
        Ma = a
B.sort()
B.reverse()
i = 0
Mb = B[0]
while Mb > Ma and H > 0:
  i += 1
  H -= Mb
  if i == N:
    Mb = 0
  else:
    Mb = B[i]
if H <= 0:
  print(i)
else:
  print(i+int(-(-H//Ma)))