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

import math
import heapq
xs,ys,xe,ye = map(int,input().split())
cs = [(xs,ys,0), (xe,ye,0)]
N = int(input())
for i in range(N):
    cs.append(tuple(map(int,input().split())))

def dist(x1,y1,x2,y2):
    dx,dy = x2-x1,y2-y1
    return math.sqrt(dx**2 + dy**2)

def calc_cost(i,j):
    if i == j: return float('inf')
    x1,y1,r1 = cs[i]
    x2,y2,r2 = cs[j]
    cost = max(0, dist(x1,y1,x2,y2) - r1 - r2)
    return cost

INF = float('inf')
direct = calc_cost(0,1)
hq = []
for i in range(1,N+2):
    c = calc_cost(0,i)
    if c > direct: continue
    hq.append((c,i))
heapq.heapify(hq)
visited = [1] + [0] * (N+1)
cost = [0] + [INF] * (N+1)
while hq:
    c,v = heapq.heappop(hq)
    if v == 1:
        print(c)
        exit()
    cost[v] = c
    visited[v] = 1
    for to in range(1,N+2):
        if to == v or visited[to]: continue
        newcost = calc_cost(v, to)
        if cost[to] <= cost[v] + newcost: continue
        if direct < cost[v] + newcost: continue
        heapq.heappush(hq, (cost[v] + newcost, to))


### FIXED CODE ###

import math,heapq,sys
input = sys.stdin.readline
xs,ys,xe,ye = map(int,input().split())
cs = [(xs,ys,0), (xe,ye,0)]
N = int(input())
for i in range(N):
    cs.append(tuple(map(int,input().split())))

def calc_cost(i,j):
    if i == j: return float('inf')
    x1,y1,r1 = cs[i]
    x2,y2,r2 = cs[j]
    cost = max(0, math.hypot(x1-x2,y1-y2) - r1 - r2)
    return cost

INF = float('inf')
direct = calc_cost(0,1)
hq = []
for i in range(1,N+2):
    c = calc_cost(0,i)
    if c > direct: continue
    hq.append((c,i))
heapq.heapify(hq)
not_visited = set(range(1,N+2))
cost = [0] + [INF] * (N+1)
while hq:
    c,v = heapq.heappop(hq)
    if v not in not_visited: continue
    if v == 1:
        print(c)
        exit()
    cost[v] = c
    not_visited.remove(v)
    for to in not_visited:
        newcost = calc_cost(v, to)
        if cost[to] <= cost[v] + newcost: continue
        if direct < cost[v] + newcost: continue
        heapq.heappush(hq, (cost[v] + newcost, to))
### BUGGY CODE ###

N, K = map(int, input().split(" "))
routs = {}
tereporter = list(map(int, input().split()))
for i in range(N):
  routs[i + 1] = tereporter[i]
present_location = 1
n = 0
for i in range(K):
  n += 1
  present_location = routs[present_location]
  if present_location == 1:
    if n == 0 or K % n == 0:
      break
    for i in range(K % n):
      present_location = routs[present_location]
    break

print(present_location)

### FIXED CODE ###

N, K = map(int, input().split(" "))
routs = {}
location = [0 for i in range(N + 1)]
tereporter = list(map(int, input().split()))
for i in range(N):
  routs[i] = tereporter[i] - 1
present_location = 0
n = 0
for i in range(K):
  n += 1
  present_location = routs[present_location]
  if location[present_location] == 0:
    location[present_location] = n
  else:
    loop = n - location[present_location]
    if (K - location[present_location]) % loop == 0:
      break
    else:
      for i in range((K - location[present_location]) % loop):
        present_location = routs[present_location]
      break
print(present_location + 1)
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
b = []
for i in a:
    b.append(i)
    b.reverse()
print(' '.join(map(str,b)))

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
b = []
c = []
for i in range(n):
    if  i % 2 == 1:
        b.append(a[i])
    else:
        c.append(a[i])
if n % 2 == 0:
    b.reverse()
    ans = b + c
else:
    c.reverse()
    ans = c + b
print(' '.join(map(str,ans)))
### BUGGY CODE ###

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

c = [ab[i][1] for i in range(M) if ab[i][0] == 1]
d = set()
for i in range(M) :
    if ab[i][0] in c :
        d.add(ab[i][1])

if N in d :
    print("POSSIBLE")
else :
    print("IMPOSSIBLE")


### FIXED CODE ###

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

c = {ab[i][1] for i in range(M) if ab[i][0] == 1}
d = {ab[i][0] for i in range(M) if ab[i][1] == N}

if c & d :
    print("POSSIBLE")
else :
    print("IMPOSSIBLE")
### BUGGY CODE ###

h,w = map(int,input().split())
a = [list(map(int,input().split())) for _ in range(h)]
b = [list(map(int,input().split())) for _ in range(h)]

for i in range(h):
    for j in range(w):
        a[i][j] = abs(a[i][j] - b[i][j])

dp = [[0] * 9600 for _ in range(w*h)]
for i in range(h):
    for j in range(w):
        min_ = max(0, 3200 - min(i+j, 160-i-j)*80)
        max_ = min(9599, 3200 + min(i+j, 160-i-j)*80)
        a_tmp = a[i][j]
        if(i==0)&(j==0):
            dp[i*w+j][3200+a_tmp] += 1
            dp[i*w+j][3200-a_tmp] += 1
        elif(i==0):
            for k in range(min_, max_+1):
                if(k+a_tmp < 9600):
                    dp[i*w+j][k+a_tmp] += dp[i*w+j-1][k]
                if(k-a_tmp >= 0):
                    dp[i*w+j][k-a_tmp] += dp[i*w+j-1][k]
        elif(j==0):
            for k in range(min_, max_+1):
                if(k+a_tmp < 9600):
                    dp[i*w+j][k+a_tmp] += dp[i*w+j-w][k]
                if(k+a_tmp >= 0):
                    dp[i*w+j][k-a_tmp] += dp[i*w+j-w][k]
        else:
            for k in range(min_, max_+1):
                if(k+a_tmp < 9600):
                    dp[i*w+j][k+a_tmp] += dp[i*w+j-1][k]
                    dp[i*w+j][k+a_tmp] += dp[i*w+j-w][k]
                if(k+a_tmp >= 0):
                    dp[i*w+j][k-a_tmp] += dp[i*w+j-1][k]
                    dp[i*w+j][k-a_tmp] += dp[i*w+j-w][k]

ans = 3200
for i in range(3100, 3300):
    if(dp[-1][i] > 0):
        ans = min(ans, abs(i-3200))

print(ans)

### FIXED CODE ###

h,w = map(int,input().split())
a = [list(map(int,input().split())) for _ in range(h)]
b = [list(map(int,input().split())) for _ in range(h)]

for i in range(h):
    for j in range(w):
        a[i][j] = abs(a[i][j] - b[i][j])

base = 2**12800 - 1
dp = [[0] * (w+1) for _ in range(h+1)]
dp[1][1] = (2**6400 >> a[0][0])|(2**6400 << a[0][0])&base
for i in range(1,h+1):
    for j in range(1,w+1):
        if(i==1)&(j==1):
            dp[1][1] = (2**6400 >> a[0][0])|(2**6400 << a[0][0])&base
            continue

        dp[i][j] = ((dp[i-1][j] >> a[i-1][j-1])|(dp[i-1][j] << a[i-1][j-1])|
                    (dp[i][j-1] >> a[i-1][j-1])|(dp[i][j-1] << a[i-1][j-1]))&base

ans = 6400
ans_bit = dp[-1][-1]
for i in range(6300,6500):
    if((ans_bit >> i)&1 == 1):
        ans = min(ans, abs(6400-i))

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

from collections import deque

class Edge:
	def __init__(self, t, w):
		self.to = t
		self.ew = w

class Graph:
	def __init__(self, N):
		self.nw = [-1] * N
		self.al = [[] for i in range(N)]

	def add_edge(self, fr, to, weight):
		self.al[fr].append(Edge(to, weight))
		self.al[to].append(Edge(fr, -weight))

	def dfs(self, s, used):
		self.nw[s] = 0
		q = deque([s])
		while q:
			h = q.popleft()
			if h in used:
				continue
			used.add(h)
			for e in self.al[h]:
				if e.to in used and self.nw[h] + e.ew != self.nw[e.to]:
					return False
				self.nw[e.to] = self.nw[h] + e.ew
				q.appendleft(e.to)
		return True


def main():
	N, M = map(int, input().split())
	graph = Graph(N)
	for i in range(M):
		l, r, d = map(int, input().split())
		graph.add_edge(l - 1, r - 1, d)

	used = set()
	for i in range(N):
		if i in used or graph.dfs(i, used):
			continue
		print("No")
		break
	else:
		print("Yes")


if __name__ == "__main__":
	main()


### FIXED CODE ###

import sys
sys.setrecursionlimit(100000)
N, M = map(int, input().split())
union = list(range(N + 1))
dist = [0] * (N + 1)
rec = [0] * (N + 1)

def ascend(anc):
	count = 0
	while anc != union[anc]:
		rec[count] = anc
		anc = union[anc]
		count += 1
	rec[count] = anc
	for i in range(count - 1, -1, -1):
		dist[rec[i]] += dist[rec[i + 1]]
		union[rec[i]] = anc
	return anc

def connect(l, r, d):
	l_anc = ascend(l)
	r_anc = ascend(r)
	if l_anc != r_anc:
		union[l_anc] = r_anc
		dist[l_anc] = dist[r] + d - dist[l]

def is_union(l, r):
	return ascend(l) == ascend(r)

def check(l, r, d):
	return dist[r] + d == dist[l]

for i in range(M):
	l, r, d = map(int, input().split())
	if is_union(l, r):
		if not check(l, r, d):
			print("No")
			break
	else:
		connect(l, r, d)
else:
	print("Yes")
### BUGGY CODE ###


N = int(input())

lis = []

A1 = int(input())

lis.append([A1])


for i in range(N-1):

    A = int(input())

    flag = True

    for l in lis:

        if l[-1] < A:
            l.append(A)
            flag = False
            break

    if flag:
        lis.append([A])

#print (lis)
print (len(lis))


### FIXED CODE ###

import bisect

N = int(input())

A = []

for i in range(N):

    a = int(input())
    A.append(a)

A.reverse()

seq = [float("-inf")]

for i in A:

    ind = bisect.bisect_right(seq,i)

    if ind == len(seq):
        seq.append(i)
    else:
        seq[ind] = i

print (len(seq)-1)
### BUGGY CODE ###

N=int(input())
A=list(map(int,input().split()))
for i in range(N):
    X=0
    for j in range(1,N+1):
        Y=A.count(j)
        if j!=A[i]:
            X+=Y*(Y-1)//2
        else:
            X+=(Y-1)*(Y-2)//2
    print(X)



### FIXED CODE ###

import collections
N=int(input())
A=list(map(int,input().split()))
c=collections.Counter(A)
s=0
def f(n):
    return n*(n-1)//2
for i in c:
    c[i]=(f(c[i]),(f(c[i]-1)))
    s+=c[i][0]
for j in A:
    print(s-c[j][0]+c[j][1])
### BUGGY CODE ###

N = int(input())

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

sum = 0
for i in range(N):
    print(A.count(i+1))
    sum += A.count(i+1)
    if sum == N:
        break

### FIXED CODE ###

import collections

N = int(input())

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

c = collections.Counter(A)

for i in range(N):
    print(c[i+1])
### BUGGY CODE ###

N, Q = list(map(int, input().split()))
S = input()
li = [list(map(int, input().split())) for i in range(Q)]

for num in range(Q):
    st = S[li[num][0] - 1:li[num][1]]
    if not "AC" in st:
        print(0)
    else:
        count = 0
        for i in range(len(st)-1):
            if st[i] == "A":
                if st[i+1] == "C":
                    count += 1
        print(count)

### FIXED CODE ###

N, Q = map(int, input().split())
S = input()
t = [0] * (N + 1)
for i in range(N):
	t[i + 1] = t[i] + (1 if S[i : i + 2] == 'AC' else 0)
for i in range(Q):
	l, r = map(int, input().split())
	print(t[r-1] - t[l-1])
### BUGGY CODE ###

n,t = map(int,input().split())
ab = [[int(i) for i in input().split()] for j in range(n)]

dp = [[0 for i in range(t)] for j in range(n+1)]
ab.sort()

ans = 0

for i in range(n):
    for j in range(t):
        #for k in range(2):
        #dp[i+1][j] = max(dp[i][j],dp[i-1][j])
        dp[i+1][j] = dp[i][j]
        #print(j,ab[i][0])
        if j >= ab[i][0]:
        #if dp[i][j] < dp[i][j-ab[i][0]] + ab[i][1]:
        #    dp[i+1][j] = dp[i][j-ab[i][0]] + ab[i][1]
            dp[i+1][j] = max(dp[i][j],dp[i][j-ab[i][0]] + ab[i][1])
        #print(dp)
    #print(h,dp)

#print(ab)
#print(dp)


max_num = [0]*n

for i in reversed(range(n)):
    #print(i)
    if i == 0:
        break
    if max_num[i] < ab[i][1]:
        max_num[i-1] = ab[i][1]
    else:
        max_num[i-1] = max_num[i]

#print(max_num)
#print(ab[2272:2336])
#exit()

ans = 0
for i in range(n-1):
    #print(i)
    if ans < dp[i+1][t-1]+max_num[i]:
        ans = dp[i+1][t-1]+max_num[i]
        #print(i,ans,max_num[i],max_num[i+1],max_num[i-1])
    #ans = max(ans,)
    #print(max(ab[i:][1]))
    #print()
        
print(ans)
#print())

### FIXED CODE ###

n,t = map(int,input().split())
ab = [[int(i) for i in input().split()] for j in range(n)]

dp = [[0 for i in range(t)] for j in range(n+1)]
ab.sort()

ans = 0

for i in range(n):
    for j in range(t):
        #for k in range(2):
        #dp[i+1][j] = max(dp[i][j],dp[i-1][j])
        dp[i+1][j] = dp[i][j]
        #print(j,ab[i][0])
        if j >= ab[i][0]:
        #if dp[i][j] < dp[i][j-ab[i][0]] + ab[i][1]:
        #    dp[i+1][j] = dp[i][j-ab[i][0]] + ab[i][1]
            dp[i+1][j] = max(dp[i][j],dp[i][j-ab[i][0]] + ab[i][1])
        #print(dp)
    #print(h,dp)

#print(ab)
#print(dp)


max_num = [0]*n

for i in reversed(range(n)):
    #print(i)
    if i == 0:
        break
    if max_num[i] < ab[i][1]:
        max_num[i-1] = ab[i][1]
    else:
        max_num[i-1] = max_num[i]

#print(max_num)
#print(ab[2272:2336])
#exit()

ans = 0
for i in range(n-1):
    #print(i)
    if ans < dp[i+1][t-1]+max_num[i]:
        ans = dp[i+1][t-1]+max_num[i]
        #print(i,ans,max_num[i],max_num[i+1],max_num[i-1])
    #ans = max(ans,)
    #print(max(ab[i:][1]))
    #print()
        
print(ans)
#print())
### BUGGY CODE ###

N, M = map(int, input().split())
from  bisect import bisect_right
inf = float("inf")
A = sorted(list(map(int, input().split()))) + [inf]
BC = sorted([tuple(map(int, input().split())) for _ in range(M)], key=lambda x: -x[1])
for b, c in BC:
    idx = bisect_right(A, c)
    if idx == 0:
        break
    if idx >= b:
        tmp = A[b:idx]
        new = [c]*b
        A = tmp + new + A[idx:]
    elif idx < b:
        tmp = A[idx:]
        new = [c]*idx
        A = new + tmp

print(sum(A[:-1]))

### FIXED CODE ###

N, M = map(int, input().split())
A = list(map(int, input().split()))
P = [(A[i], 1) for i in range(N)]
for j in range(M):
    B, C = map(int, input().split())
    P.append((C, B))
P.sort(reverse=True)
ans, cnt = 0, N
for v, c in P:
    use = min(c, cnt)
    ans += use*v
    cnt -= use
print(ans)
### BUGGY CODE ###

N = int(input())
An = input().split()
c = 0
for i in range(N):
    An[i] = int(An[i])
for i in range(N):
    for k in range(i+1,N):
        if An[i] + An[k] == k - i :
            c = c + 1
print(c)
        

### FIXED CODE ###

from collections import Counter
N = int(input())
An = list(map(int,input().split()))
c = 0
Bn = []
Cn = []
for k in range(N):    
    Bn.append(An[k]+k)
    Cn.append(k-An[k])
Cj = Counter(Cn)
for i in Bn:
    c+=Cj[i]
print(c)
### BUGGY CODE ###

from collections import Counter

S,r = input(),0
dp = list(range(len(S)+1))
dp[-1],dp[-2] = 0,int(S[-1])

for i in range(3,len(S)+2):
	dp[-i] = (dp[-i+1] + 10**(i-2)*int(S[-i+1])) % 2019

c = Counter(dp)
for x in c.values():
	r += x*(x-1)//2
print(r)

### FIXED CODE ###

from collections import Counter

def modpow(a, n, m):
	r = 1
	while n > 0:
		if n & 1:
			r = r*a%m
		a = a*a%m
		n >>= 1
	return r

S,r = input(),0
dp = list(range(len(S)+1))
dp[-1],dp[-2] = 0,int(S[-1])

for i in range(3,len(S)+2):
	dp[-i] = (dp[-i+1] + modpow(10,i-2,2019)*int(S[-i+1])) % 2019

for x in Counter(dp).values():
	r += x*(x-1)//2
print(r)
### BUGGY CODE ###

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

count=0
for i in range(K+1):
  if i>S:
    break
  for j in range(K+1):
    if j>S:
      break
    for k in range(K+1):
      if k>S:
        break
      if i+j+k==S:
        count+=1
print(count)


### FIXED CODE ###

K,S=map(int,input().split())
r=K+1
count=0
for x in range(r):
  if x>S:
    break
  for y in range(r):
    if y>S:
      break
    z=S-x-y
    if 0<=z and z<=K:
      count+=1
print(count)
### BUGGY CODE ###

from itertools import combinations

N = int(input())
V = list(map(int,input().split()))
C = list(map(int,input().split()))

num = list(range(N))
pmax = 0

for i in range(N):
    combi = list(combinations(num,i))
    for j in range(len(combi)):
        v_value = 0
        c_value = 0
        for k in range(len(combi[j])):
            v_value = v_value + V[combi[j][k]]
            c_value = c_value + C[combi[j][k]]
            pmax = max(pmax,v_value-c_value)
 
print(pmax)


### FIXED CODE ###

N = int(input())
V = list(map(int, input().split()))
C = list(map(int, input().split()))

ans = 0

for i in range(N):
    a = V[i] - C[i]
    if a > 0:
        ans += a

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

n=int(input())
a=list(map(int,input().split(" ")))
deta=[]
error=False
    
for i in range(n):
    if len(deta)==0:
        pass
    elif error:
        break
    elif a[i] in deta:
        error=True
    deta.append(a[i])
if error:
    print("NO")
else:
    print("YES")

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split(" ")))
deta = set()
error = False

for i in range(n):
    if n == 0:
        pass
    elif error:
        break
    elif a[i] in deta:
        error = True
        break
    deta.add(a[i])
if error:
    print("NO")
else:
    print("YES")
### BUGGY CODE ###

steps, limit = map(int, input().split())
heights = [int(height) for height in input().split()]
costs = [0] * steps
def search(step, num):
    candidates = []
    for i in range(1,num+1):
        how_many = costs[step-i] + abs(heights[step-i] - heights[step])
        candidates.append(how_many)
    costs[step] = min(candidates)
for i in range(1,steps):
    if i < limit:
        search(i, i)
    else:
        search(i, limit)
print(costs[steps-1])

### FIXED CODE ###

import numpy as np
steps, limit = map(int, input().split())
heights = [int(height) for height in input().split()]
heights = np.array(heights, np.int)
costs = np.array([0] * steps, np.int)
def search(step, num):
    costs[step] = min(costs[step-num:step] + abs(heights[step-num:step] - heights[step]))
for i in range(1,steps):
    if i < limit:
        search(i, i)
    else:
        search(i, limit)
print(costs[steps-1])
### BUGGY CODE ###

n, w = map(int, input().split())
shina = tuple(tuple(map(int, input().split())) for _ in range(n))

dp = [[0 for i in range(w+1)] for j in range(n+1)]

for i in range(n):
    wi = shina[i][0]
    vi = shina[i][1]
    for sum_w in range(w+1):
        if sum_w - wi >= 0:
            dp[i+1][sum_w] = max(dp[i+1][sum_w], dp[i][sum_w - wi] + vi)

        dp[i+1][sum_w] = max(dp[i+1][sum_w], dp[i][sum_w])

print(dp[-1][-1])

### FIXED CODE ###

import numpy as np
n, w = map(int, input().split())
wv_list = [[int(i) for i in input().split()] for i in range(n)]

dp = np.zeros(w+1)
for wv in wv_list:
    w = wv[0]
    v = wv[1]
    dp[w:] = np.maximum(dp[:-w]+v, dp[w:])

print(int(np.max(dp)))
### BUGGY CODE ###

def main():
    from collections import deque
    S=input()
    Q=int(input())
    A=[input().split() for _ in range(Q)]
    d=deque(S)
    for x in A:
        if x[0]=="1":
            d.reverse()
        else:
            if x[1]=="1":
                d.appendleft(x[2])
            else:
                d.append(x[2])

    print("".join(d))    

if __name__ == '__main__':
    main()



### FIXED CODE ###

def main():
    from collections import deque
    import sys
    def input():
        return sys.stdin.readline()[:-1]
    S=input()
    Q=int(input())
    A=[input().split() for _ in range(Q)]
    d=deque(S)
    
    d_left=d.appendleft
    d_right=d.append
    j=["1","2"]
    k=0
    j_re=j.reverse
    for x in A:
        if x[0]=="1":
            j_re()
            k+=1
        else:
            if x[1]==j[0]:
                d_left(x[2])
            else:
                d_right(x[2])
    if k%2==1:
        d.reverse()
    print("".join(d))    

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

import math


def list_divisor(n):
    divisor1 = {1}
    for i in range(2, int(math.sqrt(n)) + 1):
        if n % i == 0:
            divisor1.add(i)

    divisor2 = {n}
    for i in divisor1:
        divisor2.add(n // i)

    return divisor1 | divisor2


def main():
    n = int(input().rstrip())

    sub_only = len(list_divisor(n - 1)) - 1

    div_included = 0
    for d in (list_divisor(n) - {1}):
        n1 = n // d
        while n1 % d == 0:
            n1 = n1 // d

        if n1 == 1:
            div_included += 1
            continue

        if d in list_divisor(n1 - 1):
            div_included += 1

    print(sub_only + div_included)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import math


def list_divisor(n):
    divisor1 = {1}
    for i in range(2, int(math.sqrt(n)) + 1):
        if n % i == 0:
            divisor1.add(i)

    divisor2 = {n}
    for i in divisor1:
        divisor2.add(n // i)

    return divisor1 | divisor2


def main():
    n = int(input().rstrip())

    sub_only = len(list_divisor(n - 1)) - 1

    div_included = 0
    for d in (list_divisor(n) - {1}):
        n1 = n // d
        while n1 % d == 0:
            n1 = n1 // d

        if n1 == 1:
            div_included += 1
            continue

        if d in list_divisor(n1 - 1):
            div_included += 1

    print(sub_only + div_included)


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

import math
n, h = map(int, input().split())
s = []
for i in range(n):#h:高さ
    s.append([int(m) for m in input().split()])#a,b
t = []
for i in range(n):
    t.append(["a", i + 1, s[i][0]])
    t.append(["b", i + 1, s[i][1]])
t.sort(key=lambda x:(x[2]),reverse=True)

count = 0
p = 0
while h > 0 and p == 0:
    if t[0][0] == "b":
        h -= t[0][2]
        t = t[1:]
        count += 1
    else:
        count += math.ceil(h / t[0][2])
        p = 1
print(count)


### FIXED CODE ###

import math
n, h = map(int, input().split())
s = []
for i in range(n):#h:高さ
    s.append([int(m) for m in input().split()])#a,b
t = []
for i in range(n):
    t.append(["a", i + 1, s[i][0]])
    t.append(["b", i + 1, s[i][1]])
t.sort(key=lambda x:(x[2]),reverse=True)

count = 0
p = 0
for i in range(n + 1):
    if t[i][0] == "b":
        h -= t[i][2]
        count += 1
        if h <= 0:
            break
    else:
        count += math.ceil(h / t[i][2])
        break
print(count)
### BUGGY CODE ###

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

dp = [0]*(W+1)
L = []
for i in range(N):
    tb,ta = map(int,input().split())
    L.append([ta,tb])

for i in range(N):
    for w in range(W,-1,-1):
        if w-L[i][1]>=0 :dp[w] = max(dp[w],dp[w-L[i][1]]+L[i][0])
print(dp[-1])

### FIXED CODE ###

n,k = map(int,input().split())
w=[]
v=[]
dp =[[0 for i in range(k+1)] for j in range(n+1)]

for i in range(n):
    a,b = map(int,input().split())
    w.append(a)
    v.append(b)
for i in range(n):
    for sum_w in range(k+1):
        if sum_w - w[i] >=0:
            dp[i+1][sum_w]=max(dp[i][sum_w],dp[i][sum_w - w[i]] + v[i])
        else:
            dp[i+1][sum_w]=dp[i][sum_w]

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

# -*- coding: utf-8 -*-
"""
Created on Sun Jun 24 18:23:54 2018
ITP22C
@author: maezawa
"""

from collections import deque

n, q = list(map(int, input().split()))
a = [deque() for _ in range(n)]

for i in range(q):
    c = list(map(int, input().split()))
    if c[0] == 0:
        if a[c[1]]:
            if a[c[1]][-1] < c[2]:
                a[c[1]].append(c[2])
            else:
                for j in reversed(range(len(a[c[1]])-1)):
                    if a[c[1]][j] < c[2]:
                        a[c[1]].insert(j+1, c[2])
                        break
                else:
                    a[c[1]].appendleft(c[2])
        
        else:
            a[c[1]].append(c[2])
    elif c[0] == 1:
        if a[c[1]]:
            print(a[c[1]][-1])
    else:
        if a[c[1]]:
            a[c[1]].pop()




### FIXED CODE ###

import heapq

n, q = list(map(int, input().split()))
a = [[] for _ in range(n)]

for i in range(q):
    c = list(map(int, input().split()))
    if c[0] == 0:
        heapq.heappush(a[c[1]],-c[2])
    elif c[0] == 1:
        if a[c[1]]:
            print(-a[c[1]][0])
    else:
        if a[c[1]]:
            heapq.heappop(a[c[1]])