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

import bisect

N=int(input())

line=[]

for _ in range(N):
    A=int(input())
    index=bisect.bisect_left(line,A)
    if index==0:
        line.insert(index,A)
    else:
        line.pop(index-1)
        bisect.insort_right(line,A)
    
    #print(line)

print(len(line))

### FIXED CODE ###

import bisect
import collections

N=int(input())

line=collections.deque()

for _ in range(N):
    A=int(input())
    index=bisect.bisect_left(line,A)
    if index==0:
        line.appendleft(A)
    else:
        line[index-1]=A
    #print(line)
    
    #print(line)

print(len(line))
### BUGGY CODE ###

s=input()
count=0

for i in range(len(s)-3):
  for j in range(i+4,len(s)+1):
    #print(i,j)
    n= int(s[i:j])
    if n % 2019 == 0:
      #print("!")
      count=count+1
      
print(count)

### FIXED CODE ###

s=input()
s_rev=s[::-1]

mod_count=[0]*2019
mod_count[0]=1
d=1
num=0

for char in s_rev:
  num=num+int(char)*d
  num=num%2019
  d=d*10
  d=d%2019
  #print(type(num),type(mod_count))
  mod_count[num]=mod_count[num]+1

ans=0
for cnt in mod_count:
  ans=ans+cnt*(cnt-1)/2
  
print(int(ans))
### BUGGY CODE ###

import sys
input = sys.stdin.readline

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)]
can_make = [[None for _ in range(W)] for _ in range(H)]
for i in range(H):
    for j in range(W):
        x = A[i][j] - B[i][j]
        if i == j == 0:
            can_make[i][j] = set([abs(x)])
            continue
        st = set()
        if i > 0:
            for y in can_make[i-1][j]:
                if abs(y + x) <= 6400:
                    st.add(abs(y + x))
                st.add(abs(y - x))
        if j > 0:
            for y in can_make[i][j-1]:
                if abs(y + x) <= 6400:
                    st.add(abs(y + x))
                st.add(abs(y - x))
        can_make[i][j] = st
print(min(can_make[-1][-1], key=lambda x: abs(x)))



### 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)]
C = [[abs(A[i][j] - B[i][j]) for j in range(W)] for i in range(H)]

M = (H+W)*80
dp = [[0] * W for _ in range(H)]
dp[0][0] |= 1 << (M-C[0][0])
for i in range(H):
    for j in range(W):
        if i == j == 0:
            continue
        bit = 0
        if i > 0:
            bit |= dp[i-1][j]
        if j > 0:
            bit |= dp[i][j-1]
        dp[i][j] = (bit >> C[i][j]) | (bit << C[i][j])
ans = M
for i in range(M+1):
    if (dp[-1][-1] >> i) & 1:
        ans = min(ans, abs(M-i))
print(ans)
### BUGGY CODE ###

N = int(input())
S = input()
ans = 0

for pin in range(0,1000):
  counter = 0
  for index in range(0, N):
    if str(pin).zfill(3)[counter] == S[index]:
      counter += 1
    if counter == 3:
      ans += 1
      break
    
print(ans)

### FIXED CODE ###

N = int(input())
S = input()
ans = 0

for pin in range(0,1000):
  counter = 0
  for index in range(0, N):
    if str(pin).zfill(3)[counter] == S[index]:
      counter += 1
    if counter == 3:
      ans += 1
      break
    
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

def chmax(a, b):
  if a<b:
    a = b
  return a

weight = [0]*110
value = [0]*110
dp = [[0]*100010 for i in range(110)]
    
N, W = map(int, input().split())
for i in range(N):
  weight[i], value[i] = map(int, input().split())

# dp roop
for i in range(N):
  sum_w = 0
  while sum_w <= W:
    if (sum_w - weight[i]) >= 0:
      dp[i+1][sum_w] = chmax(dp[i+1][sum_w],
                             dp[i][sum_w - weight[i]] + value[i])
    dp[i+1][sum_w] = chmax(dp[i+1][sum_w], dp[i][sum_w])
    sum_w += 1
print(dp[N][W])    

### FIXED CODE ###

import sys
input = sys.stdin.readline

weight = [0]*110
value = [0]*110
dp = [[0]*100010 for i in range(110)]

N, W = map(int, input().split())
for i in range(N):
  weight[i], value[i] = map(int, input().split())

# dp roop
for i in range(N):
  sum_w = 0
  while sum_w <= W:
    if sum_w >= weight[i]:
      dp[i+1][sum_w] = max(dp[i][sum_w - weight[i]] + value[i], dp[i][sum_w])
    else:
      dp[i+1][sum_w] = dp[i][sum_w]
    sum_w += 1
print(dp[N][W])
### BUGGY 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], reverse=True)
for b, c in bc:
  a += [c] * b
a.sort(reverse=True)
print(sum(a[:N]))

### 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 ###

A, B, N = map(int, input().split())

max_r = 0
for i in range(B):
  if i <= N:
    max_r = max(max_r, i/B)

res = int(max_r * A)
print(res)

### FIXED CODE ###

A, B, N = map(int, input().split())

max_d = min(B - 1, N)
max_r = max_d / B

res = int(max_r * A)
print(res)
### BUGGY CODE ###

N = int(input())
L = [n for n in map(int,input().split())]
res = 1 #一つ目はどれよりも”大きい”
k = 0
for i in range(1,N):
    if min(L[0:i+1]) == L[i]:
        res += 1
print(res)

### FIXED CODE ###

N = int(input())
L = [_ for _ in map(int,input().split())]
res = 0
for x in L:
  if x <= N:
    res += 1
    N = x #最小上書き。次にresが増えるのは後々の要素で最小より小さいのが出てきたとき。
print(res)
#みんなもtabulationミスってREには気をつけようね
### BUGGY CODE ###

from collections import deque
import sys

sys.setrecursionlimit(2000000000)
 
n = int(input())
nodes = []
done = [0 for _ in range(n)]
par = {}
for _ in range(n):
    x, y = map(int,input().split())
    nodes.append((x,y))
    par[(x,y)]=(x,y)
nodesx = sorted(nodes)
nodesy = sorted(nodes,key=lambda z:z[1])
s = []
 
for i in range(n-1):
    xcost =nodesx[i+1][0]-nodesx[i][0]
    ycost =nodesy[i+1][1]-nodesy[i][1]
    s.append((xcost,(nodesx[i+1],nodesx[i])))
    s.append((ycost,(nodesy[i+1],nodesy[i])))
s.sort()
def root(node,par):
    if node == par[node]:
        return node
    else:
        par[node] =root(par[node],par)
        return par[node]
def unite(node1,node2,par):
    par[root(node1,par)] = root(node2,par)
ans = 0
count =0
for cost,(node1,node2) in s:
    if count == n-1:
        break
    root1 =root(node1,par)
    root2 =root(node2,par)
    if root1 != root2:
        unite(node1,node2,par)
        ans +=cost
        count += 1
print(ans)


### FIXED CODE ###

from collections import deque
import sys
 
sys.setrecursionlimit(2000000000)
 
n = int(input())
nodes = []
done = [0 for _ in range(n)]
par = {}
for _ in range(n):
    x, y = map(int,input().split())
    nodes.append((x,y))
    par[(x,y)]=(x,y)
nodesx = sorted(nodes)
nodesy = sorted(nodes,key=lambda z:z[1])
s = []
m = len(set(nodes))
for i in range(n-1):
    xcost =nodesx[i+1][0]-nodesx[i][0]
    ycost =nodesy[i+1][1]-nodesy[i][1]
    s.append((xcost,(nodesx[i+1],nodesx[i])))
    s.append((ycost,(nodesy[i+1],nodesy[i])))
s.sort()
s = deque(s)
def root(node,par):
    if node == par[node]:
        return node
    else:
        par[node] =root(par[node],par)
        return par[node]
def unite(node1,node2,par):
    par[root(node1,par)] = root(node2,par)
ans = 0
count =0
while count < m-1 :
    cost,(node1,node2) = s.popleft()
    root1 =root(node1,par)
    root2 =root(node2,par)
    if root1 != root2:
        unite(node1,node2,par)
        ans +=cost
        count += 1
print(ans)
### BUGGY CODE ###

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


ans = 0
sum_a = 0
for i in range(len(a)):
  sum_a += a[i]
  sum_b = 0
  if sum_a > k:
    break
  if sum_a == k:
    temp = i+1
    if temp > ans:
      ans = temp
    break
  for j in range(len(b)):
    sum_b += b[j]
    if (sum_a + sum_b) > k:
      temp = i+1+j
      if temp > ans:
        ans = temp
      break
    if (sum_a + sum_b) == k:
      temp = i+1+j+1
      if temp > ans:
        ans = temp
      break
      
sum_b = 0
for i in range(len(b)):
  sum_b += b[i]
  sum_a = 0
  if sum_b > k:
    break
  if sum_b == k:
    temp = i+1
    if temp > ans:
      ans = temp
    break
  for j in range(len(a)):
    sum_a += a[j]
    if (sum_b + sum_a) > k:
      temp = i+1+j
      if temp > ans:
        ans = temp
      break
    if (sum_b + sum_a) == k:
      temp = i+1+j+1
      if temp > ans:
        ans = temp
      break
      
print(ans)

### FIXED CODE ###

N, M, K = map(int, input().split())
A = list(map(int,input().split()))
B = list(map(int, input().split()))
a = [0]
b = [0]

ans = 0
j = M

for i in range(N):
  a.append(a[i] + A[i])

for i in range(M):
  b.append(b[i] + B[i])

for i in range(N+1):
  if a[i] > K:
    break
  while a[i] + b[j] > K:
    j -= 1
  ans = max(ans, i+j)

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

import numpy as np
from scipy.sparse.csgraph import shortest_path #dijkstra
from scipy.sparse import csr_matrix
# from scipy.special import comb,perm #permはnPk

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

d = [1 for _ in range(M)]
arr = np.array([list(map(int,input().split())) for _ in range(M)])
arr = arr.T - 1
graph = csr_matrix((d, (arr[0], arr[1])), shape=(N, N)) # 頂点i,jはゼロスタートである必要ある

#返り値は各頂点間の距離の値を含んだ隣接行列(float64型のnp.array)
dist,pred = shortest_path(graph,method='J', directed=False,indices=0,return_predecessors=True,unweighted=True)

pred = pred + 1
print("Yes")
print(*pred[1:],sep="\n")

### FIXED CODE ###

# from math import factorial,sqrt,ceil #,gcd
# from itertools import permutations,combinations,combinations_with_replacement
# from collections import deque,Counter
# import re
# from bisect import bisect_left
# from heapq import heappush,heappop
# from numba import njit,jit
# from functools import lru_cache # 簡単メモ化 @lru_cache(maxsize=1000)
# from fractions import gcd

# from decimal import Decimal, getcontext
# # getcontext().prec = 1000
# # eps = Decimal(10) ** (-100)

# import numpy as np
from networkx import Graph
from networkx.algorithms.traversal.breadth_first_search import bfs_predecessors
G = Graph()
# from scipy.sparse.csgraph import shortest_path, dijkstra, floyd_warshall, bellman_ford, johnson
# from scipy.sparse import csr_matrix
# from scipy.special import comb,perm #permはnPk

# slist = "abcdefghijklmnopqrstuvwxyz"
N,M = map(int,input().split())
rows = [list(map(int,input().split())) for _ in range(M)]

G.add_edges_from(rows)

# shortestPath = shortest_path(G,target=1)
preds = bfs_predecessors(G,source=1)
# shortestPath = single_target_shortest_path(G,target=1)
# shortestPathLength,shortestPath = single_source_dijkstra(G,source=1)

preds = dict(preds)
if len(preds)+1 != N:
    print("No")
    exit()

print("Yes")
for i in range(2,N+1):
    print(preds[i])
### BUGGY CODE ###

mod = 10**9+7
s = list(reversed(list(input())))
n = len(s)
dp = [[0,0,0,0,0,0,0,0,0,0,0,0,0]for _ in range(n+1)]
dp[0][0] = 1
for i in range(n):
    if s[i] == '?':
        for k in range(10):
            x = k*pow(10,i,13) % 13
            for j in range(13):
                dp[i+1][(j+x) % 13] += dp[i][j] % mod
    else:
        x = int(s[i])*pow(10,i,13) % 13
        for j in range(13):
            dp[i+1][(j+x) % 13] += dp[i][j] % mod
print(dp[n][5] % mod)



### FIXED CODE ###

mod = 10**9+7
s = list(reversed(list(input())))
n = len(s)
dp = [[0,0,0,0,0,0,0,0,0,0,0,0,0]for _ in range(n+1)]
dp[0][0] = 1
for i in range(n):
    if s[i] == '?':
        for k in range(10):
            x = k*pow(10,i,13) % 13
            for j in range(13):
                dp[i+1][(j+x) % 13] += dp[i][j] % mod
    else:
        x = int(s[i])*pow(10,i,13) % 13
        for j in range(13):
            dp[i+1][(j+x) % 13] += dp[i][j] % mod
print(dp[n][5] % mod)
### BUGGY CODE ###

n = int(input())
s = input()
ans = 0
for i in range(n-3):
    i_ = s[i]
    for j in range(i+1, n-1):
        if s[j] == i_: continue
        else:
            k = 2 * j - i
            j_ = s[j]
            s_ = s[j+1:]
            ans += len(s_) - s_.count(i_) - s_.count(j_)
            if k >= n: continue
            if s[k] != i_ and s[k] != j_: ans -= 1
print(ans)

### FIXED CODE ###

n = int(input())
s = input()
ans = s.count("R") * s.count("G") * s.count("B")
cnt = 0
for i in range(n):
    i_ = s[i]
    for j in range(i+1, n):
        if s[j] == i_: continue
        k = 2 * j - i
        j_ = s[j]
        if k >= n or s[k] == i_ or s[k] == j_: continue
        cnt += 1
print(ans - cnt)
### BUGGY CODE ###

N,M=map(int,input().split())
H=list(map(int,input().split()))
A=[]
B=[]
for _ in range(M):
  a,b=map(int,input().split())
  A.append(a)
  B.append(b)
ans=0
for i in range(1,N+1):
  f=True
  for j in range(M):
    if A[j]==i:
      if H[i-1]<=H[B[j]-1]:
        f=False
    if B[j]==i:
      if H[i-1]<=H[A[j]-1]:
        f=False
  if f:
    ans+=1
print(ans)

### FIXED CODE ###

N,M=map(int,input().split())
H=list(map(int,input().split()))
A=[]
B=[]
for _ in range(M):
  a,b=map(int,input().split())
  A.append(a)
  B.append(b)
ans=0
f=[True]*N
for j in range(M):
  if H[A[j]-1]<=H[B[j]-1]:
    f[A[j]-1]=False
  if H[B[j]-1]<=H[A[j]-1]:
    f[B[j]-1]=False
for i in f:
  if i:ans+=1
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
def main():
  xs,ys,xt,yt=map(int,input().split())
  n=int(input())
  xyr=[[xs,ys,0],[xt,yt,0]]
  xyr+=[list(map(int,input().split())) for _ in range(n)]
  g=[[]for _ in range(n+2)]
  for i in range(n+1):
    for j in range(i+1,n+2):
      x,y,r=xyr[i]
      x1,y1,r1=xyr[j]
      d=max(0,((x-x1)**2+(y-y1)**2)**0.5-r-r1)
      g[i].append([d,j])
      g[j].append([d,i])
  xry=[]
  from heapq import heappop,heappush
  todo=[[0,0]]
  ka=set(())
  seen=[-1]*(n+2)
  seen[0]=0
  while todo:
    d,v=heappop(todo)
    if v in ka:continue
    if v==1:
      print(d)
      exit()
    ka.add(v)
    for nd,nv in g[v]:
      if seen[nv]==-1 or seen[nv]>d+nd:
        heappush(todo,[d+nd,nv])
        seen[nv]=d+nd
if __name__=='__main__':
  main()


### FIXED CODE ###

from heapq import heappop,heappush
from math import sqrt
def distf(xyr,i,j):
  x,y,r=xyr[i]
  x1,y1,r1=xyr[j]
  d=max(0,sqrt((x-x1)**2+(y-y1)**2)-r-r1)
  return d

def main():
  xs,ys,xt,yt=map(int,input().split())
  n=int(input())
  xyr=[list(map(int,input().split())) for _ in range(n)]
  xyr.append([xs,ys,0])
  xyr.append([xt,yt,0])
  inf=float('inf')
  dist=[[inf]*(n+2) for _ in range(n+2)]
  for i in range(n+2):
    dist[i][i]=0
  for i in range(n+1):
    for j in range(i+1,n+2):
      dist[i][j]=distf(xyr,i,j)
      dist[j][i]=dist[i][j]
  seen=[inf]*(n+2)
  seen[n]=0
  mi=set(range(n+2))
  while mi:
    d,v=inf,-1
    for j in mi:
      if d>seen[j]:
        d=seen[j]
        v=j
    mi.remove(v)
    for nv in mi:
      nd=dist[v][nv]
      if seen[nv]>seen[v]+nd:
        seen[nv]=seen[v]+nd
  print(seen[n+1])
if __name__=='__main__':
  main()
### BUGGY CODE ###

from heapq import heappush,heappop
n,q=map(int,input().split())
e=[]
for i in range(n):
  s,t,x=map(int,input().split())
  e.append((s-x,1,x))
  e.append((t-x,-1,x))
for i in range(q):
  d=int(input())
  e.append((d,2,0))
e.sort()
s=set()
a=[]
for time_,type_,x_ in e:
  if type_==1:
    s.add(x_)
    heappush(a,x_)
  elif type_==-1:
    s.remove(x_)
  else:
    while a and a[0] not in s:
      heappop(a)
    if a:
      print(a[0])
    else:
      print(-1)

### FIXED CODE ###

import sys
from heapq import heappush,heappop
input=sys.stdin.readline
n,q=map(int,input().split())
e=[]
for i in range(n):
  s,t,x=map(int,input().split())
  e.append((s-x,1,x))
  e.append((t-x,-1,x))
for i in range(q):
  d=int(input())
  e.append((d,2,0))
e.sort()
s=set()
a=[]
for time_,type_,x_ in e:
  if type_==1:
    s.add(x_)
    heappush(a,x_)
  elif type_==-1:
    s.remove(x_)
  else:
    while a and a[0] not in s:
      heappop(a)
    if a:
      print(a[0])
    else:
      print(-1)
### BUGGY CODE ###

k = int(input())
ans = 0
count = 1

if k%2 == 0 or k %5 == 0 :
    print(-1)
else :
    s = 7
    while ans == 0 :
        if s%k == 0 :
            ans = count
        else :
            s += 7*(10**count) % k
            count += 1
    print(ans)


        

### FIXED CODE ###

k = int(input())

if k%2 == 0 or k%5 == 0 :
    print(-1)
    exit()

a = 0
for i in range(k):
    a=(a*10+7)%k
    if a == 0 :
        print(i+1)
        exit()
### BUGGY CODE ###

import sys
input = sys.stdin.readline

N = int(input())
print(0, flush=True)
prev = input()
if prev == 'Vacant':
    exit()
left = 0
right = N - 1

while right - left > 1:
    mid = (left + right) // 2
    print(mid, flush=True)
    s = input()
    if s == 'Vacant':
        exit()
    if prev == s:
        if (mid - left) % 2 == 0:
            left = mid
        else:
            right = mid
    else:
        if (mid - left) % 2 == 1:
            left = mid
        else:
            right = mid
        prev = s

print(right, flush=True)
s = input()
exit()


### FIXED CODE ###

import sys
input = sys.stdin.readline

N = int(input())
left = 0
right = N
print(left, flush=True)
left_seat = input()
if left_seat == 'Vacant':
    exit()


while right - left > 1:
    mid = (left + right) // 2
    print(mid, flush=True)
    mid_seat = input()
    if mid_seat == 'Vacant':
        exit()
    if mid_seat == left_seat:
        if (mid - left) % 2 == 0:
            left = mid
        else:
            right = mid
    else:
        if (mid - left) % 2 == 1:
            left = mid
            left_seat = mid_seat
        else:
            right = mid
### BUGGY CODE ###

import networkx as nx
room, route_count = map(int,input().split())
G = nx.Graph()
G.add_nodes_from(range(1,room+1))
G.add_edges_from([list(map(int,input().split())) for _ in range(route_count)])
if all([nx.has_path(G,source=i, target=1) for i in range(1, room+1)]):
  print('Yes')
  shortest_path_dict = nx.single_target_shortest_path(G, target=1)
  for i in range(2,room+1):
    print(shortest_path_dict[i][1])
else:
  print('No')

### FIXED CODE ###

import networkx as nx
room, route_count = map(int,input().split())
route = [list(map(int,input().split())) for _ in range(route_count)]

G = nx.Graph()
G.add_nodes_from(range(1,room+1))
G.add_edges_from(route)
pre = nx.predecessor(G, 1)

print('Yes')
for i in range(2,room+1):
  print(pre[i][0])
### BUGGY CODE ###

import math
from collections import deque
import itertools

[H, W] = map(int, input().rstrip().split(" "))
S = []


for h in range(H):
    Ss = input().rstrip()
    S.append(Ss)

dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]

max_cost = 0

for h in range(H):
    for w in range(W):
        if S[h][w] == "#":
            continue
        que = deque()
        history = [ [-1 for w in range(W)] for h in range(H)]
        que.append([h, w])
        history[h][w] = 0
        current_max_cost = 0
        while len(que) != 0:
            [x, y] = que.pop()
            for i in range(4):
                newx = x + dx[i]
                newy = y + dy[i]
                if 0 <= newx and newx < H and 0 <= newy and newy < W and S[newx][newy] != "#" and (history[newx][newy] > history[x][y] + 1 or history[newx][newy] == -1):
                    history[newx][newy] = history[x][y] + 1
                    que.append([newx, newy])
        current_max_cost = max(list(itertools.chain.from_iterable(history)))
        if max_cost < current_max_cost:
            max_cost = current_max_cost

print(max_cost)


### FIXED CODE ###

import math
from collections import deque
import itertools

[H, W] = map(int, input().rstrip().split(" "))
S = []


for h in range(H):
    Ss = input().rstrip()
    S.append(Ss)

dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]

max_cost = 0

for h in range(H):
    for w in range(W):
        if S[h][w] == "#":
            continue
        que = deque()
        history = [ [float('inf') for w in range(W)] for h in range(H)]
        que.append([h, w])
        history[h][w] = 0
        current_max_cost = 0
        while len(que) != 0:
            [x, y] = que.popleft()
            for i in range(4):
                newx = x + dx[i]
                newy = y + dy[i]
                if 0 <= newx and newx < H and 0 <= newy and newy < W and S[newx][newy] != "#" and history[newx][newy] == float('inf'):
                    history[newx][newy] = history[x][y] + 1
                    if current_max_cost < history[newx][newy]:
                        current_max_cost = history[newx][newy]
                    que.append([newx, newy])
        if max_cost < current_max_cost:
            max_cost = current_max_cost

print(max_cost)
### BUGGY CODE ###

import sys

input = sys.stdin.readline
n,m = map(int, input().split())
A = list(map(int,input().split()))

for i in range(m):
    A.sort()
    b,c = map(int, input().split())
    if A[0] < c:
        if A[b-1] > c:
            for i in range(n):
                if A[i] < c:
                    A[i] = c
                else:
                    break
        else:
            A[:b] = [c for i in range(b)]


print(sum(A))

### FIXED CODE ###

import sys
import heapq

input = sys.stdin.readline
n,m = map(int, input().split())
A = list(map(int,input().split()))
d = [list(map(int,input().split())) for _ in range(m)]

d.sort(key=lambda x:-x[1])
total = sum(A)
heapq.heapify(A)

for i in range(m):
    for j in range(d[i][0]):
        tmp = heapq.heappushpop(A, d[i][1])
        if tmp < d[i][1]:
                total += (d[i][1] - tmp)
        else:
            break

print(total)
### BUGGY CODE ###

from sys import exit

N, u, v = map(int, input().split())

if u == v:
    print(0)
    exit()

edges = [[] for _ in range(N + 1)]
for _ in range(N - 1):
    A, B = map(int, input().split())
    edges[A].append(B)
    edges[B].append(A)


def calc_destination(start, edges):
    destination = [-1] * (N + 1)
    destination[start] = 0
    q = [start]
    while len(q) != 0:
        current = q.pop(0)
        for n in edges[current]:
            if destination[n] != -1:
                continue
            destination[n] = destination[current] + 1
            q.append(n)
    return destination


tak = calc_destination(u, edges)
aok = calc_destination(v, edges)

result = 0
for i in range(1, N + 1):
    aoki = aok[i]
    if tak[i] >= aoki:
        continue
    if aoki > result:
        result = aoki
print(result - 1)


### FIXED CODE ###

def calc_destination(start, edges, N):
    destination = [-1] * (N + 1)
    destination[start] = 0
    q = [start]
    while len(q) != 0:
        current = q.pop()
        for n in edges[current]:
            if destination[n] != -1:
                continue
            destination[n] = destination[current] + 1
            q.append(n)
    return destination

def main():
    N, u, v = map(int, input().split())

    if u == v:
        print(0)
        return

    edges = [[] for _ in range(N + 1)]
    for _ in range(N - 1):
        A, B = map(int, input().split())
        edges[A].append(B)
        edges[B].append(A)

    tak = calc_destination(u, edges, N)
    aok = calc_destination(v, edges, N)

    result = 0
    for i in range(1, N + 1):
        aoki = aok[i]
        if tak[i] >= aoki:
            continue
        if aoki > result:
            result = aoki
    print(result - 1)

main()
### BUGGY CODE ###

def main():
  import sys
  input = sys.stdin.readline
  num,capacity=map(int,input().split())
  DP=[-1]*(capacity+1)
  DP[0]=0
  for _ in range(num):
    weight,value=map(int,input().split())
    left=capacity-weight
    DP[weight:]=[max(DP[i]+value,DP[i+weight]) for i in range(left,-1,-1)][::-1]
  print(max(DP))
      
if __name__=="__main__":
  main()

### FIXED CODE ###

n,w=map(int,input().split())
goods=[list(map(int,input().split())) for _ in range(n)]
DP=[[0]*(w+1) for _ in range(n+1)]
for i in list(range(n))[::-1]:
  wi,vi=goods[i][0],goods[i][1]
  for j in range(w+1):
    if j<wi:
      DP[i][j]=DP[i+1][j]
    else:
      DP[i][j]=max(DP[i+1][j],DP[i+1][j-wi]+vi)
print(DP[0][w])