Harryxun/stf_run huggingface dataset:
import math

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

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

ans = []

def ncr(n, r):
    if n<r:
        return 0
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

subg = {i+1:i+1 for i in range(n)}

nodes = {i+1:1 for i in range(n)}

res = []
r = ncr(n, 2)

def fetch(i):
    if i == subg[i]:
        return i
    j = fetch(subg[i])
    subg[i] = j
    return j

for a, b in reversed(br):
    # print(subg, nodes)

    if len(nodes.keys()) == 1:
        res.append(0)
        continue
    else:
        res.append(r)

    mi, ma = min(a,b), max(a,b)
    
    x = nodes[fetch(mi)] 
    y = nodes[fetch(ma)]

    r += ncr(x, 2) + ncr(y, 2)
    r -= ncr(x+y, 2)

    v, w = max(fetch(mi), fetch(ma)), min(fetch(mi), fetch(ma))
    nodes[w] += nodes[v]
    del nodes[v]
    subg[mi] = w
    subg[ma] = w

for i in reversed(res):
    print(i)



### FIXED CODE ###


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

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

ans = []

def nc2(n):
    if n<2:
        return 0
    return n * (n-1) // 2


class UnionFind:

    def __init__(self, size):
        self.table = [-1 for _ in range(size+1)]
        self.size = [1 for _ in range(size+1)]

    def find(self, x):
        while self.table[x] >= 0:
            x = self.table[x]
        return x

    def union(self, x, y):
        s1 = self.find(x)
        s2 = self.find(y)
        if s1 != s2:
            if self.table[s1] != self.table[s2]:
                if self.table[s1] < self.table[s2]:
                    self.table[s2] = s1
                    self.size[s1] += self.size[s2]
                    self.size[s2] = 0
                else:
                    self.table[s1] = s2
                    self.size[s2] += self.size[s1]
                    self.size[s1] = 0
            else:
                self.table[s1] += -1
                self.table[s2] = s1
                self.size[s1] += self.size[s2]
                self.size[s2] = 0

    def get_size(self, x):
        s1 = self.find(x)
        return self.size[s1]

    def check_same(self, x, y):
        return self.find(x) == self.find(y)

res = []
r = nc2(n)

uf = UnionFind(n)

for a, b in reversed(br):

    res.append(r)

    if not uf.check_same(a,b):
        r -= uf.get_size(a)*uf.get_size(b)

    uf.union(a,b)

for i in reversed(res):
    print(i)
s = input()
if s[0]!="A":
  print("WA")
  exit()
else:
  s.pop(0)
  
if "C" in s[2:len(s)-1]:
  s.replace("C","",1)
  
if s.islower():
  print("AC")
else:
  print("WA")

### FIXED CODE ###

s = list(input())
flg = "WA"
if s[0]=="A":
  if "C" in s[2:len(s)-1]:
    s.remove("A")
    s.remove("C")
    s = ''.join(s)
    if s.islower()==True:
      flg = "AC"
print(flg)
import math

N = int(input())
A = list(map(int,input()))
B = []
M = math.ceil(math.log(N,2)) 

for i in range(N):
  a = 0
  for j in range(1,M+1,1):
    a += math.floor((N-1)/(2**j))-math.floor((i)/(2**j))-math.floor((N-1-i)/(2**j))
  if a == 0:
    B.append(1)
  else:
    B.append(0)
b = 0
for i in range(N):
  b += B[i]*A[i]
if b % 2 == 1:
  print(1)
else:
  for i in range(N):
    if A[i] == 2:
      print(0)
      break
  else:
    c = 0
    for i in range(N):
      A[i] = (A[1]-1)//2
      c += B[i]*A[i]
    if c % 2 == 1:
      print(2)
    else:
      print(0)

### FIXED CODE ###

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


def g(m):
    if data[0][0] == '.':
        a = 0
    else:
        a = 1

    for i in range(1, m, 1):
        if data[0][i] == '.':
            continue
        elif data[0][i] == '#' and data[0][i - 1] == '.':
            a += 1
        else:
            continue
    return a


def h(n):
    if data[0][0] == '.':
        a = 0
    else:
        a = 1

    for i in range(1, n, 1):
        if data[i][0] == '.':
            continue
        elif data[i][0] == '#' and data[i - 1][0] == '.':
            a += 1
        else:
            continue
    return a

A = [0] + [g(i) for i in range(1,W+1)]
B = [0] + [h(i) for i in range(1,H+1)]
C = [[0]*(W+1) for i in range(H+1)]

for n in range(1,H+1):
    for m in range(1,W+1):
        if n == 1:
            C[n][m] = A[m]
        elif m == 1:
            C[n][m] = B[n]
        else:
            if data[n - 1][m - 1] == '.':
                C[n][m] = min(C[n - 1][m], C[n][m - 1])
            elif data[n - 2][m - 1] == '.':
                if data[n - 1][m - 2] == '.':
                    C[n][m] = min(C[n - 1][m] + 1, C[n][m - 1] + 1)
                else:
                    C[n][m] =  min(C[n - 1][m] + 1, C[n][m - 1])
            else:
                if data[n - 1][m - 2] == '.':
                    C[n][m] = min(C[n - 1][m], C[n][m - 1] + 1)
                else:
                    C[n][m] = min(C[n - 1][m], C[n][m - 1])


print(C[H][W])
a, b = input(), input()
print a * b, 2 * (a + b)

### FIXED CODE ###

a, b = map(int, raw_input(). split())
print a * b, 2 * (a + b)
#import math
#import numpy as np
#import torch
#import torch.nn as nn
#import matplotlib.pyplot as plt
#from decimal import Decimal

#N=int(input())
A,V = map(int,input().split())
B,W = map(int,input().split())
T=int(input())
#A = list(map(int,input().split()))
#S=str(input())

if V<=W:
    print('NO')
else:
    L=abs(A-B)
    if L%(V-W)==0:
        if L/(V-W)<=T:
            print('YES')
        else:
            print('NO')
    else:
        while T>0:
            T-=1
            L=L+V+W
            if L/(V-W)<=T:
                print('YES')
                exit()
            if V*T<L:
                ptint('NO')
                exit()

        print('NO')


### FIXED CODE ###

#import math
#import numpy as np
#import torch
#import torch.nn as nn
#import matplotlib.pyplot as plt
#from decimal import Decimal

#N=int(input())
A,V = map(int,input().split())
B,W = map(int,input().split())
T=int(input())
#A = list(map(int,input().split()))
#S=str(input())

if V<=W:
    print('NO')
else:
    L=abs(A-B)
    if L/(V-W)<=T:
        print('YES')
    else:
        print('NO')
function Main(input) {
  const step = input.trim().split('');
  const even = ['L', 'U', 'D'];
  const odd = ['R', 'U', 'D'];
  var easy = true;

  for (var i in step) {
    var cnt = i + 1
    if (cnt % 2 == 0) {
      if ( even.indexOf(step[i]) !== -1 ) easy = false;
    } else {
      if ( odd.indexOf(step[i]) !== -1 ) easy = false;
    }
  }

  console.log(easy ? 'Yes':'No')
}
Main(require('fs').readFileSync('/dev/stdin', 'utf8'));


### FIXED CODE ###

import sys
import os

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

MOD = 10 ** 9 + 7


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    S = list(iss())
    odd = 'RUD'
    even = 'LUD'
    ret = 'Yes'
    for n in range(len(S)):
        if (n + 1) % 2 == 0 and S[n] not in even or (n + 1) % 2 != 0 and S[n] not in odd:
            ret = 'No'
    else:
        print(ret)


if __name__ == '__main__':
    main()
import math
A, B = map(int,input().split())

UE_8 = (A+1)/0.08
SHITA_8 = A/0.08
UE_10 = (B+1)/0.10
SHITA_10 = B/0.10

if UE_8 < SHITA_10 or UE_10 < SHITA_8:
    print(-1)
else:
    i = math.ceil(SHITA_8)
    j = math.floor(UE_8)
    for n in range(j-i+1,start=i):
        if i < UE_10 and i >= SHITA_10:
            print(i)
        i+=1

### FIXED CODE ###

import math
A, B = map(int,input().split())

UE_8 = math.ceil((A+1)/0.08)-1
SHITA_8 = A/0.08
UE_10 = math.ceil((B+1)/0.10)-1
SHITA_10 = B/0.10

if UE_8 < math.ceil(SHITA_10) or UE_10 < math.ceil(SHITA_8):
    print(-1)
else:
    i = math.ceil(SHITA_8)
    j = math.floor(UE_8)
    for n in range(int(i),int(j+1),1):
        if i < UE_10 and i >= SHITA_10:
            print(i)
            break
        i+=1
a,b=map(int,input().split())
    if a>9 or b>9:
      print(-1)
    else:
      print(a*b)
      

### FIXED CODE ###

a,b=map(int,input().split())
if a >= 10 or b >= 10:
  print(-1)
else:
  print(a*b)
n = int(input())
A = [int(i) for i in input().split()]
input()
M = [int(i) for i in input().split()]

def solve(i, m):
    if m == 0:
        return True
    if i >= n:
        return False
    res = solve(i+1, m) or solve(i+1, m-A[i])
    return res

for m in M:
    if solve(0, m):
        print('yes')
    else:
        print('no')


### FIXED CODE ###

n = int(input())
A = [int(i) for i in input().split()]
input()
M = [int(i) for i in input().split()]

def solve(i, m):
    if m == 0:
        return True
    if i >= n or m < 0:
        return False
    res = solve(i+1, m) or solve(i+1, m-A[i])
    return res

for m in M:
    if sum(A) < m:
        print("no")
    elif solve(0, m):
        print('yes')
    else:
        print('no')
a,b = input().split()
print(a*b)

### FIXED CODE ###

a, b = (int(x)
        for x in input().split())
print(a*b)
k = int(input())
def gcd1 (a, b):
    while True:
        if (a < b):
            a, b = b, a
        c = a%b
        if (c == 0):
            return (b)
        else:
            a = b
            b = c

def gcd2 (a, b, c):
    tmp = gcd1(a, b)
    ans = gcd1(tmp, c)
    return (ans)

count = 0
for i in range(k):
    for j in range(k):
        for l in range(k):
            tmp = gcd(i + 1, j + 1, l + 1)
            count = count + tmp
print(count)


### FIXED CODE ###

k = int(input())
def gcd1 (a, b):
    while True:
        if (a < b):
            a, b = b, a
        c = a%b
        if (c == 0):
            return (b)
        else:
            a = b
            b = c

count = 0
for i in range(k):
    for j in range(k):
        tmp = gcd1(i + 1, j + 1)
        if (tmp == 1):
            count = count + k
        else:
            for l in range(k):
                tmp2 = gcd1(tmp, l + 1)
                count = count + tmp2

print(count)
n=int(input())
A=list(map(int,input().split( )))
B=list(map(int,input().split( )))
count=0
before=0
i=-1
while True:
    before=count
    tonari=B[i-2]+B[i]
    tmp=(B[i-1]-A[i-1])//tonari
    B[i-1]-=tonari*tmp
    count+=tmp
    i+=1
    i%=n
    if before==count:
        break

if A==B:
    print(count)
else:
    print(-1)

n=int(input())
A=list(map(int,input().split( )))
B=list(map(int,input().split( )))
count=0
flag=True
while flag:
    flag=False
    for i in range(-1,n-1):
        tonari=B[i-1]+B[i+1]
        tmp=B[i]//tonari#B[i]-A[i]から変更
        if tmp>0:
            B[i]-=tonari*tmp
            count+=tmp
            flag=True
if A==B:
    print(count)
else:
    print(-1)

### FIXED CODE ###

n=int(input())
A=list(map(int,input().split( )))
B=list(map(int,input().split( )))
count=0
prv_count=-1#人の見て追加

#flag=True
while count!=prv_count:
    prv_count=count
    for i in range(-1,n-1):
        tonari=B[i-1]+B[i+1]
        tmp=(B[i]-A[i])//tonari
        if tmp>0:
            B[i]-=tonari*tmp
            count+=tmp
            #flag=True
if A==B:
    print(count)
else:
    print(-1)
n, a, b = map(int, input().split(),input.split())
counter = 0
for i in range(n):
  wa = 0
  for j in range(4):
    k = i / 10**j
    m = k % 10
    wa += m
  if (a <= m)and(m <= b):
    counter += 1
print(counter)

### FIXED CODE ###

n,a,b=map(int, input().split()) 
total = 0
for i in range(1,n+1):
  m = i
  wa = 0
  while True:
    wa += m % 10
    m = m // 10
    if (m == 0):
      break
  if (wa >= a)and(wa <= b):
    total += i
print(total)
if S=='SAT':
    print(1)
elif S=='FRI':
    print(2)
elif S=='THU':
    print(3)
elif S=='WED':
    print(4)
elif S=='TUE':
    print(5)
elif S=='MON':
    print(6)
else S=='SUN':
    print(7)


### FIXED CODE ###

S = input()

if S == "SUN":
    print(7)
elif S == "MON":
    print(6)
elif S == "TUE":
    print(5)
elif S == "WED":
    print(4)
elif S == "THU":
    print(3)
elif S == "FRI":
    print(2)
else:
    print(1)
x,a,b=map(int,inpur().split())
if min(abs(x-a),abs(x-b))==abs(x-a):
  print("A")
else:
  print("B")

### FIXED CODE ###

x,a,b=map(int,input().split())
if min(abs(x-a),abs(x-b))==abs(x-a):
  print("A")
else:
  print("B")
n,k = map(int,input().split())
s = [int(input()) for i in range(n)]
s.sort()
c = s[n-k-1] - s[0]
for i in range(1,n-k+1):
    if s[i+n-k] - s[i] < c:
        c = s[i+n-k] - s[i]

print(c)

### FIXED CODE ###

n,k = map(int,input().split())
s = [int(input()) for i in range(n)]
s.sort()
c = s[k-1] - s[0]
for i in range(1,n-k+1):
    if s[i+k-1] - s[i] < c:
        c = s[i+k-1] - s[i]

print(c)
import math
N = 10**9+7
n = int(input())
a = list(map(int,input().split()))

ans = 0

a1 = max(a)
if a1 == 0:
    a1=2
ma = int(math.log2(a1))
if ma<0:
    ma=0
for i in range(ma+2):
    sum=0
    for j in range(n):
        sum+=(a[j]>>i) & 1
    ans+=sum*(n-sum)*pow(2,i,N)
    ans%=10**9+7
print(ans)


### FIXED CODE ###

import numpy as np
N = 10**9+7
n = int(input())
a = np.array(input().split(), np.int64)

ans = 0

po = 1
for i in range(61):
    bit = (a>>i) & 1
    s=np.count_nonzero(bit)
    ans+=s*(n-s)%N*po
    ans%=N
    po*=2
    po%=N
print(ans)
X, N = map(int, input().split())
ans = X
if N>0:
  P = list(map(int, input().split()))
  P.sort()
  if X in P:
    ans = 0
    x = P.index(X)
    i = 1
    a = x-1
    b = x+1
    while ans == 0:
      if X-i != P[a]:
        ans = X-i
      elif X+i != P[b]:
        ans = X+i
        a -= 1
      else:
        a -= 1
        b += 1
        i += 1
print(ans)
      
        
    

### FIXED CODE ###

X, N = map(int, input().split())
ans = X
if N>0:
  P = list(map(int, input().split()))
  P.sort()
  if X in P:
    ans = 0
    x = P.index(X)
    i = 1
    a = x-1
    b = x+1
    m = min(P[N-1]-X, X-P[0])
    for i in range(1,m+2):
      if a < 0:
        a = 0
      if b > N-1:
        b = N-1
      if X-i != P[a]:
        ans = X-i
        break
      elif X+i != P[b]:
        ans = X+i
        break
      else:
        a -= 1
        b += 1
print(ans)
if b = A:
  print("G")
elif b = G:
  print("A")
elif b = C:
  print("T")
else:
  print("C")

### FIXED CODE ###

b = input()
if b == "A":
  print("T")
elif b == "T":
  print("A")
elif b == "G":
  print("C")
else:
  print("G")
h, w = map(int, input().split())
f = [input() for _ in range(h)]
for i in range(h):
  for j in range(w):
    if f[i][w] == '#':
      print('#', end = "")
      continue
    cnt = 0
    for k in range(i-1, i+2):
      if k < 0 or h <= k:
        continue
      for l in range(j-1, j+2):
        if l < 0 or w <= l:
          continue
        if f[k][l] == '#':
          cnt += 1
    print(cnt, end = "")
  print()
  

### FIXED CODE ###

h, w = map(int, input().split())
f = [input() for _ in range(h)]
for i in range(h):
  for j in range(w):
    if f[i][j] == '#':
      print('#', end = "")
      continue
    cnt = 0
    for k in range(i-1, i+2):
      if k < 0 or h <= k:
        continue
      for l in range(j-1, j+2):
        if l < 0 or w <= l:
          continue
        if f[k][l] == '#':
          cnt += 1
    print(cnt, end = "")
  print()
a = int(input())
b = [int(i) for i in input().split()]
last = 1
for i in b:
    last*=i
    if last > 10**18:
    	last = -1
        break
    
print(last)

### FIXED CODE ###

input()
b = [int(i) for i in input().split()]

if 0 not in b:
  last = 1
  for i in b:
      last*=i
      if last > 10**18:
        last = -1
        break
    
else:
  last = 0
    
print(last)
import sys
h,w,m = map(int,input().split())
h_lst = [[0,i] for i in range(h)]
w_lst = [[0,i] for i in range(w)]
memo = []

for i in range(m):
  x,y = map(int,input().split())
  h_lst[x-1][0] += 1
  w_lst[y-1][0] += 1
  memo.append((x-1,y-1))

h_lst.sort(reverse = True)
w_lst.sort(reverse = True)
Max_h = h_lst[0][0]
Max_w = w_lst[0][0]
h_ans = [h_lst[0]]
w_ans = [w_lst[0]]
s = 1
while h_lst[s][0] == Max_h:
  h_ans.append(h_lst[s])
  s+= 1   
t=1  
while w_lst[t][0] == Max_w:
  w_ans.append(w_lst[t])
  t += 1
  

memo = set(memo)

#探索するリストは、最大を取るものの集合でなければ計算量はO(m)にはならない！             
for [y,j] in h_ans:
  if y == Max_h:
    for [z,k] in w_ans:
      if (j,k) not in memo and w_lst[0][0] == z:
        print(Max_h+w_lst[0][0])
        sys.exit()
print((Max_h+w_lst[0][0])-1)        
  



### FIXED CODE ###

import sys
h,w,m = map(int,input().split())
h_lst = [[0,i] for i in range(h)]
w_lst = [[0,i] for i in range(w)]
memo = []

for i in range(m):
  x,y = map(int,input().split())
  h_lst[x-1][0] += 1
  w_lst[y-1][0] += 1
  memo.append((x-1,y-1))

h_lst.sort(reverse = True)
w_lst.sort(reverse = True)
Max_h = h_lst[0][0]
Max_w = w_lst[0][0]
h_ans = [h_lst[0][1]]
w_ans = [w_lst[0][1]]
if h != 1:
  s = 1
  while s < h and h_lst[s][0] == Max_h:
    h_ans.append(h_lst[s][1])
    s+= 1  
if w!= 1:  
  t=1  
  while t < w and w_lst[t][0] == Max_w:
    w_ans.append(w_lst[t][1])
    t += 1
  

memo = set(memo)

#探索するリストは、最大を取るものの集合でなければ計算量はO(m)にはならない！             
for j in h_ans:
  for k in w_ans:
    if (j,k) not in memo:
      print(Max_h+Max_w)
      sys.exit()
print((Max_h+Max_w)-1)
import math
S = input()
K = int(input())
i = 0
while True:
    print('first:',S[i])
    if S[i] == '1':
        if K == 1:
            break
        else:
            K-=1
            i+=1
    else:
        d = int( (math.log(int(S[i]))) * ((2**5)*(10**15)) ) + 1
        if d<K:K-=d
        else:break
        i += 1
print(S[i])

### FIXED CODE ###

S = input()
K = int(input())
i = 0
while True:
    if S[i] == '1':
        if K == 1:
            break
        else:
            K-=1
            i+=1
    else:
        break
print(S[i])
import numpy as np

x = int(input())

t = (-1 + np.sqrt(1 + 8 * x)) /? 2
t = int(t)

print(t + 1)

### FIXED CODE ###

import numpy as np

x = int(input())

numerator = (-1 + np.sqrt(1 + 8 * x))
t = int(numerator // 2)

if numerator % 2 == 0:
    print(t)
else:
    print(t + 1)
def aizu001 ():
    xs = map(int,raw_input().split())
    a = xs[0]
    b = xs[1]
    if a > b:
        print "a > b"
    else if a < b:
        print "a < b"
    else :
        print "a == b"

### FIXED CODE ###

def aizu001 ():
    xs = map(int,raw_input().split())
    a = xs[0]
    b = xs[1]
    if a > b:
        print "a > b"
    elif a < b:
        print "a < b"
    else :
        print "a == b"

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

ans = 0
for i in range(n):
  if b[i] > a[i]:
    ans += a[i]
    b[i] -= a[i]
    if b[i] >= a[i+1]:
      ans += a[i+1]
      a[i+1] = 0
    else:
      ans += b[i]
      a[i+i] -= b[i]
  elif b[i] == a[i]:
    ans += a[i]
  else:
    ans += b[i]

print(ans)

### FIXED CODE ###

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

ans = 0
if n == 1:
  if b[0] >= a[0]:
    ans = ans + a[0]
  else:
    ans = ans + b[0]
else:
  for i in range(n):
    if b[i] > a[i]:
      ans += a[i]
      b[i] -= a[i]
      if b[i] >= a[i+1]:
        ans += a[i+1]
        a[i+1] = 0
      else:
        ans += b[i]
        a[i+1] -= b[i]
    elif b[i] == a[i]:
      ans += a[i]
    else:
      ans += b[i]

print(ans)
import heapq
N,M=map(int,input().split())
x={}
for i in range(M+1):
    x[i]=[]
for i in range(N):
    if i >=M:
        continue
    a,b=map(int,input().split())
    x[a].append(-b)
y=[]
an=0
for i in range(M+1):
    for n in x[i]:
        heapq.heappush(y,n)
    try:
        an-=heapq.heappop(y)
    except:
        pass
print(an)


### FIXED CODE ###

import heapq
N,M=map(int,input().split())
x={}
for i in range(M+1):
    x[i]=[]
for i in range(N):
    a,b=map(int,input().split())
    if a>M:
        continue
    x[a].append(-b)
y=[]
an=0
for i in range(M+1):
    for n in x[i]:
        heapq.heappush(y,n)
    try:
        an-=heapq.heappop(y)
    except:
        pass
print(an)
N = int(input())

for n in range(1,N+1):
  cnt = 0
  for x in range(1,int(n**0.5)):
    for y in range(1,int(n**0.5)):
      for z in range(1,int(n**0.5)):
        if x * x + y * y + z * z + x * y + y * z + z * x == n:
          cnt += 1
  print(cnt)

### FIXED CODE ###

l,r,d = map(int,input().split())

cnt = 0
for i in range(l,r+1):
  if i % d == 0:
    cnt += 1
    
print(cnt)
# -*- coding: utf-8 -*-

import sys
N,T=map(int, sys.stdin.readline().split())
AB=[ map(int, sys.stdin.readline().split()) for _ in range(N) ]

AB.sort()

N=2005
dp=[ None for _ in range(N) ]
dp[0]=0

for a,b in AB:
    for i in range(N-1,-1,-1):
        if dp[i] is not None and i<T:
                dp[i+a]=max(dp[i+a],dp[i]+b)

print max(dp)


### FIXED CODE ###

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

import sys
N,T=map(int, sys.stdin.readline().split())
AB=[ map(int, sys.stdin.readline().split()) for _ in range(N) ]

AB.sort()

N=6005
dp=[ None for _ in range(N) ]
dp[0]=0

for a,b in AB:
    for i in range(N-1,-1,-1):
        if dp[i] is not None and i<T:
                dp[i+a]=max(dp[i+a],dp[i]+b)

print max(dp)
import sys
import numpy as np
from math import ceil as C, floor as F
from collections import defaultdict as D
 
alp = 'abcdefghijklmnopqrstuvwxyz'
def S(): return sys.stdin.readline().rstrip().split(' ')
def Ss(): return list(S())
def I(): return _I(S())
def Is(): return list(I())
def _I(ss): return map(int, ss) if len(ss) > 1 else int(ss[0])
 
_ = I()
xs = Is()
 
sss = 0
count = D(int)
for x in xs:
  sss += x
  count[x] += 1
  
q = I()
for _ in range(q):
  b, c = I()
  sss += (c - b) * count[b]
  print(sss)
  count[c] += count[b]
  count[b] = 0

### FIXED CODE ###

import sys
import numpy as np
from math import ceil as C, floor as F
from collections import defaultdict as D
from functools import reduce as R

ALP = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
alp = 'abcdefghijklmnopqrstuvwxyz'
def _X(): return sys.stdin.readline().rstrip().split(' ')
def _S(ss): return tuple(ss) if len(ss) > 1 else ss[0]
def S(): return _S(_X())
def _Ss(ss): return list(ss) if isinstance(ss, tuple) else [ss]
def Ss(): return _Ss(S())
def _I(ss): return tuple([int(s) for s in ss]) if isinstance(ss, tuple) else int(ss)
def I(): return _I(S())
def _Is(ss): return list(ss) if isinstance(ss, tuple) else [ss]
def Is(): return _Is(I())

_ = I()
xs = Is()
 
sss = 0
count = D(int)
for x in xs:
  sss += x
  count[x] += 1
  
q = I()
for _ in range(q):
  b, c = I()
  sss += (c - b) * count[b]
  print(sss)
  count[c] += count[b]
  count[b] = 0
n, m = map(int, input().split())
data = [[int(x) for x in input().split()] for _ in range(n)]

pats = [(x,y,z) for x in [-1,1] for y in [-1,1] for z in [-1,1]] # +++,++-,...,---
score = lambda sgns, vals: sum([s * x for(s, x) in zip(sgns, vals)])  # i.e.x+y-z
result = max(sum(sorted(score(pat, row) for row in data)[-m:]) for pat in pats)
print(result)

### FIXED CODE ###

xs = map(int, input().split())
test = all(x <= 8 for x in xs)
print ("Yay!" if test else ":(")
N = int(input())

ans = ""
name = []
alphabet = {i+1:chr(ord("a") + i) for i in range(26)}
while N > 0:

    a, r = N//26, N%26
    # print(a,r)
    name.append(r)
    N = N//26

if name[0] == 0:
    name = name[1:]

for i in range(len(name)):
    name[i] = alphabet[name[i]]
print("".join(name[::-1]))


### FIXED CODE ###

N = int(input())

ans = ""
while N > 0:

    N -= 1

    q, r = N//26, N%26

    ans += chr(ord("a") + r)

    N = q

print(ans[::-1])
x = int(input())
print("ABC" if x<=1199 else "ARC )

### FIXED CODE ###

x = int(input())
print("ABC" if x<=1199 else "ARC")
N = int(input())
a = [input() for i in range(N)]
c0 = a.count("AC")
c1 = a.count("WA")
c2 = a.count("TLE")
c3 = a.count("RE")
print("AC × " + c0)
print("WA × " + c1)
print("TLE × " + c2)
print("RE × " + c3)


### FIXED CODE ###

N = int(input())
a = [input() for i in range(N)]
c0 = a.count("AC")
c1 = a.count("WA")
c2 = a.count("TLE")
c3 = a.count("RE")
print("AC x", c0)
print("WA x", c1)
print("TLE x", c2)
print("RE x", c3)