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


lim = 2*10**5   #必要そうな階乗の限界を入力

#階乗#
fact = [1] * (lim+1)
for n in range(1, lim+1):
	fact[n] = n * fact[n-1] % mod

#階乗の逆元#
fact_inv = [1]*(lim+1)
fact_inv[lim] = pow(fact[lim], mod-2, mod)
for n in range(lim, 0, -1):
	fact_inv[n-1] = n*fact_inv[n]%mod

def C(n, r):
	return (fact[n]*fact_inv[r]%mod)*fact_inv[n-r]%mod


H, W, A, B = MAP()

ans = 0
for n in range(B, W):
	way = C(H-A-1+n, n)*C(W-n-1+A-1, A-1)%mod
	ans = (ans+way)%mod

print(ans)


### FIXED CODE ###

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

lim = 2*10**6
fact = [1]*(lim+1)
for n in range(1, lim+1):
	fact[n] = n*fact[n-1]%mod

fact_inv = [1]*(lim+1)
fact_inv[lim] = pow(fact[lim], mod-2, mod)
for n in range(lim, 0, -1):
	fact_inv[n-1] = n*fact_inv[n]%mod

def C(n, r):
	return (fact[n]*fact_inv[r]%mod)*fact_inv[n-r]%mod

H, W, A, B = MAP()

ans = 0
for n in range(B, W):
	way = C(H-A-1+n, n)*C(W-n-1+A-1, A-1)%mod
	ans = (ans+way)%mod

print(ans)
import math

n,x = map(int,input().split())
t   = list(map(int,input().split()))

max = abs(t[0]-x)
for i in range(1,len(t)):
    t[i] = abs(t[i]-x)
    max = math.gcd(t[i],max)

print(max)




### FIXED CODE ###

import math

def gcd(a, b):
	while b:
		a, b = b, a % b
	return a

n,x = map(int,input().split())
t   = list(map(int,input().split()))

ans = abs(t[0]-x)
for i in range(1,len(t)):
    t[i] = abs(t[i]-x)
    ans = gcd(ans,t[i])

print(ans)
N, K = map(int, input().split())
a = [int(i) for i in input().split()]
m = -1
for i in a:
  if i>m:
    m = i
s = bin(m)[1:]
length = len(s)+1
ls = [[0,length-i-1] for i in range(len(s)+1)]

for i in a:
  s = bin(i)[2:]
  while len(s)<length:
    s = '0'+s
  for j in range(len(s)):
    if s[j]=='1':
      ls[j][0] += 1
dic = {}
for i in range(len(ls)):
  x, n = ls[i]
  s = (2**n)*(N-x)-(2**n)*x
  ls[i] = (s,n)
  dic[n]=s
s = bin(K)[1:]
length = len(s)
dp = [0]*(length+1)
dp[0] = sum(a)
for i in range(1,length+1):
  if 2**(i-1)>K:
    print(dp[i-1])
    break
  if dic[i-1]>0:
    dp[i] = dp[i-1]+dic[i-1]
  else:
    dp[i] = dp[i-1]
else:
  print(dp[-1])

### FIXED CODE ###

N, K = map(int, input().split())
a = [int(i) for i in input().split()]
m = -1
for i in a:
  if i>m:
    m = i
m = max(K,m)
s = bin(m)[2:]
length = len(s)
ls = [[0,length-i-1] for i in range(length)]

for i in a:
  s = bin(i)[2:]
  while len(s)<length:
    s = '0'+s
  for j in range(length):
    if s[j]=='1':
      ls[j][0] += 1
dic = {}
for i in range(length):
  x, n = ls[i]
  s = (2**n)*(N-x)-(2**n)*x
  dic[n]=s
s = bin(K+1)[2:]
ils = [len(s)-i-1 for i in range(len(s)) if s[i]=='1']
xls = []
for i in range(len(ils)):
  m = ''
  for j in range(ils[i]):
    if dic[j]>0:
      m+='1'
    else:
      m+='0'
  m += '0'
  while len(m)<len(s):
    m += s[len(s)-len(m)-1]
  m = m[::-1]
  xls += [int(m,2)]

ans = 0
for x in xls:
  h = 0
  for u in a:
    h += x^u
  if h>ans:
    ans = h
print(ans)
H,W=map(int,input().split())
s="#"*W+"".join("#"+input()for _ in range(H))
f=-~W*-~H
d=[[0]*f for _ in range(f)]
for i in range(W,f-1):
 d[i][i-1]=s[i]==s[i-1]=="."
 d[i][i-W-1]=s[i]==s[i-W-1]=="."
from scipy.sparse.csgraph import csgraph_from_dense as C,floyd_warshall as F
import numpy as p
Q=F(C(d),directed=False)
print(int(max(Q[Q!=p.inf])))

### FIXED CODE ###

import math
N, = map(int, input().split())
xs = []
ys = []
for _ in range(N):
    x, y = map(int, input().split())
    xs.append(x)
    ys.append(y)

def bb(a,b,c,d,e,f):
    if not (c-a)*(f-b)-(e-a)*(d-b):
        return None, None
    aa = a * a
    bb = b * b
    cc = c * c
    dd = d * d
    ee = e * e
    ff = f * f
    py = ((e - a) * (aa + bb - cc - dd) - (c - a) * (aa + bb - ee- ff)) / (2 * (e - a)*(b - d) - 2 * (c - a) * (b - f))
    px = (2 * (b - f) * py - aa - bb + ee + ff) / (2 * (e - a)) \
        if (c == a) else (2 * (b - d) * py - aa - bb + cc + dd) / (2 * (c - a))
    return px, py


pxs = []
pys = []
for i in range(N):
    for j in range(i+1, N):
        for k in range(j+1, N):
#            print(i,j,k)
            px, py = bb(xs[i],ys[i],xs[j],ys[j],xs[k],ys[k])
            if not px:
                continue
            pxs.append(px)
            pys.append(py)
for i in range(N):
    for j in range(i+1, N):
        pxs.append((xs[i]+xs[j])/2)
        pys.append((ys[i]+ys[j])/2)

rr = 10**10
for px, py in zip(pxs,pys):
    r = 0
    for x, y in zip(xs, ys):
        r = max(r, (x-px)**2+(y-py)**2)
    rr = min(rr, r)
print(rr**0.5)
n = int(input())
for i in range(1, 100001):
	if i*(615) == n:
		c = i
		break
try:
	if c > 0:
		print(1)
except:
	print(0)

### FIXED CODE ###

#ossan
m1, d1 = map(int, input().split())
m2, d2 = map(int, input().split())
if d2 == 1:
	print(1)
else:
	print(0)
import math

A,B,C,D = map(int,input().split())
#print(A,B,C,D)
lcm = C * D / math.gcd(C,D)
count = 0
for i in range(A,B+1):
    if i%lcm != 0:
        count+=1
print(count)

### FIXED CODE ###

from fractions import gcd

A,B,C,D = map(int,input().split())

adivc = A//C
if A%C != 0:
    adivc = A//C + 1
bdivc = B//C
countC = bdivc - adivc + 1

adivd = A//D
if A%D != 0:
    adivd = A//D + 1
bdivd = B//D
countD = bdivd - adivd + 1

lcm = (int)(C * D / gcd(C, D))
adivlcm = A // lcm
if A%lcm != 0:
    adivlcm = A // lcm + 1
bdivlcm = B // lcm
countlcm = bdivlcm - adivlcm + 1

print(B-A+1-(countC+countD-countlcm))
N, W = map(int, input().split())

DP = [-1] * (W+1)
DP[W] = 0

def maxv(i, v):
    if i >= 0:
        if v > DP[i]:
            DP[i] = v

for w, v in (map(int, input().split()) for _ in range(N)):
    for i in range(1, W+1):
        if DP[i] >= 0:
            maxv(i-w, DP[i]+v)
            maxv(0, DP[i-w])

print(DP[0])


### FIXED CODE ###

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

IN = list(list(map(int, input().split())) for _ in range(N))
sumw = 0
sumv = 0
for w, v in IN:
    sumw += w
    sumv += v

DP = dict()
DP[sumv] = sumw

def minv(i, v):
    if not DP.get(i):
        DP[i] = v
    else:
        if v < DP[i]:
            DP[i] = v

for w, v in IN:
    DPpre = DP.copy()
    for i in DPpre:
        minv(i-v, DPpre[i]-w)

for v in sorted(DP, reverse=True):
    if DP[v] <= W:
        print(v)
        break
import sys
def MI(): return map(int,sys.stdin.readline().rstrip().split())


class SCC:
    def __init__(self,N):
        self.N = N
        self.graph = [[] for _ in range(N)]
        self.graph_rev = [[] for _ in range(N)]
        self.flag = [False]*N

    def add_edge(self,start,end):
        if start == end:
            return
        self.graph[start].append(end)
        self.graph_rev[end].append(start)

    def dfs(self,node,graph):
        self.flag[node] = True
        for n in graph[node]:
            if self.flag[n]:
                continue
            self.dfs(n,graph)
        self.order.append(node)

    def first_dfs(self):
        self.flag = [False]*self.N
        self.order = []
        for i in range(self.N):
            if self.flag[i] == False:
                self.dfs(i,self.graph)

    def second_dfs(self):
        self.flag = [False]*self.N
        self.ans = []
        for n in reversed(self.order):
            if self.flag[n]:
                continue
            self.flag[n] = True
            self.order = []
            self.dfs(n,self.graph_rev)
            self.order.reverse()
            self.ans.append(self.order)

    def scc(self):
        self.first_dfs()
        self.second_dfs()
        return self.ans


N,M = MI()
SCC = SCC(N)

for _ in range(M):
    a,b = MI()
    SCC.add_edge(a,b)

ANS = SCC.scc()

print(len(ANS))
for s in ANS:
    print(*([len(s)]+s))



### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)
def MI(): return map(int,sys.stdin.readline().rstrip().split())


class SCC:
    def __init__(self,N):
        self.N = N
        self.graph = [[] for _ in range(N)]
        self.graph_rev = [[] for _ in range(N)]
        self.flag = [False]*N

    def add_edge(self,start,end):
        if start == end:
            return
        self.graph[start].append(end)
        self.graph_rev[end].append(start)

    def dfs(self,node,graph):
        self.flag[node] = True
        for n in graph[node]:
            if self.flag[n]:
                continue
            self.dfs(n,graph)
        self.order.append(node)

    def first_dfs(self):
        self.flag = [False]*self.N
        self.order = []
        for i in range(self.N):
            if self.flag[i] == False:
                self.dfs(i,self.graph)

    def second_dfs(self):
        self.flag = [False]*self.N
        self.ans = []
        for n in reversed(self.order):
            if self.flag[n]:
                continue
            self.flag[n] = True
            self.order = []
            self.dfs(n,self.graph_rev)
            self.order.reverse()
            self.ans.append(self.order)

    def scc(self):
        self.first_dfs()
        self.second_dfs()
        return self.ans


N,M = MI()
SCC = SCC(N)

for _ in range(M):
    a,b = MI()
    SCC.add_edge(a,b)

ANS = SCC.scc()

print(len(ANS))
for s in ANS:
    print(*([len(s)]+s))
h,w,*a=open(0).read().split();b=a.index("snuke");print([chr(i)for i in range(65,65+int(h))][b%int(w)]+str(b//int(w)+1))

### FIXED CODE ###

h,w,*a=open(0).read().split();b=a.index("snuke")
print([chr(i)for i in range(65,91)][b%int(w)]+str(b//int(w)+1))
ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))

import math 

a,b,c,d = mi()

g = c*d//math.gcd(c,d)

# cの倍数の個数
ac = (a-1)//c
bc = b//c
nc = bc-ac

# dの倍数の個数
ad = (a-1)//d
bd = b//d 
nd = bd-ad

# cdのgcdの倍数の個数
ag = (a-1)//g
bg = b//g
ng = bg-ag

ans = b-(a-1)-nc - nd + ng

# print(g,nc,nd,ng)
print(ans)

### FIXED CODE ###

ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))

import fractions

a,b,c,d = mi()

g = c*d // fractions.gcd(c,d)

# cの倍数の個数
ac = (a-1)//c
bc = b//c
nc = bc-ac

# dの倍数の個数
ad = (a-1)//d
bd = b//d
nd = bd-ad

# cdのgcdの倍数の個数
ag = (a-1)//g
bg = b//g
ng = bg-ag

ans = b-(a-1)-nc - nd + ng

# print(g,nc,nd,ng)
print(ans)
N, K = map(int, input().split())
A = list(map(int, input().split()))
max_a = max(A)

dp = [0] * (K+1)

for a in A:
    dp[a] = 1

for i in range(max_a + 1, K + 1):
    for a in A:
        if dp[i - a] == 0:
            dp[i] = 1
            break
    else:
        dp[i] = 0

ans = "First" if dp[i] else "Second"
print(ans)


### FIXED CODE ###

N, K = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
max_a = A[-1]

dp = [0] * (K+1)

for a in A:
    dp[a] = 1

for i in range(1, K + 1):
    bl = False
    for a in A:
        if i - a < 0:
            break
        if dp[i - a] == 0:
            bl = True
            break
    dp[i] = 1 if bl else 0


ans = "First" if dp[K] else "Second"
print(ans)
a = input()
print(a+(a**2)+(a**3))

### FIXED CODE ###

a = int(input())
print(a+(a**2)+(a**3))
r*r

### FIXED CODE ###

r = int(input())
print(r**2)
N, Q = map(int, input().split())

# 木構造をリストで表現する
G = [[] for _ in range(N)]
for i in range(N-1):
    a, b = map(int, input().split())
    a = a - 1
    b = b - 1
    G[a].append(b)

# 各操作で与えられる値を、各頂点ごとに集計しておく
P = [0] * N
for i in range(Q):
    p, x = map(int, input().split())
    p = p - 1
    P[p] += x

# 各頂点のカウンター
Count = [0] * N


def dfs(v, point):
    # 現在いる頂点vの親までの値をpointとし、
    new_point = point + P[v]
    Count[v] = str(new_point)

    for next_v in G[v]:
        dfs(next_v, new_point)


dfs(0, 0)

res = " ".join(Count)

print(res)

### FIXED CODE ###

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

 
N,Q = map(int,input().split())
AB = [[int(x) for x in input().split()] for _ in range(N-1)]
PX = [[int(x) for x in input().split()] for _ in range(Q)]
 
graph = [[] for _ in range(N+1)]
for a,b in AB:
    graph[a].append(b)
    graph[b].append(a)
 
value = [0] * (N+1)
for p,x in PX:
    value[p] += x
 
def dfs(v,parent,add):
    value[v] += add
    for x in graph[v]:
        if x == parent:
            continue
        dfs(x,v,value[v])
 
dfs(1,0,0)
 
answer = ' '.join(map(str,value[1:]))
print(answer)
def solve(i, m):
  if dp[i][m] != -1:
    return dp[i][m]

  if m == 0:
    dp[i][m] = 1
  elif i >= n:
    dp[i][m] = 0
  elif solve(i+1, m):
    dp[i][m] = 1
  elif solve(i+1, m-A[i]):
    dp[i][m] = 1
  else:
    dp[i][m] = 0

  return dp[i][m]



n = input()
A = map(int, raw_input().split())
p = input()
m = map(int, raw_input().split())

dp = []

for i in range(n):
  for m in range(p):
    dp[i][m] == -1

for i in range(p):
  if solve(0, m[i]):
    print 'yes'
  else:
    print 'no'

### FIXED CODE ###

def solve(i, m):
  if dp[i][m] != -1:
    return dp[i][m]

  if m == 0:
    dp[i][m] = 1
  elif i >= n:
    dp[i][m] = 0
  elif solve(i+1, m):
    dp[i][m] = 1
  elif solve(i+1, m-A[i]):
    dp[i][m] = 1
  else:
    dp[i][m] = 0

  return dp[i][m]



n = input()
A = map(int, raw_input().split())
p = input()
m = map(int, raw_input().split())

dp = [[-1 for col in range(2000)] for row in range(n+1)]

for i in range(p):
  if solve(0, m[i]):
    print 'yes'
  else:
    print 'no'
n,k=map(int,input().split())
d=list(map(int,input().split()))
d=d*2
ans=0
for i in range(1,k+1):
  
  for j in range(i+1):
    have=[d[n+c-j] for c in range(i)] #ここにi個の宝石を入れる
    have.sort()
    print(have)
    if i!=k:
      for h in range(k-i):
        if have==[] or have[0]>=0:
          break
        del have[0]
      #いらない宝石を可能な限り詰めた状態
    if sum(have)>ans:
      ans=sum(have)
print(ans)


### FIXED CODE ###

n,k=map(int,input().split())
d=list(map(int,input().split()))
d=d*2
ans=0
for i in range(1,min(k+1,n+1)):
  
  for j in range(i+1):
    have=[d[n+c-j] for c in range(i)] #ここにi個の宝石を入れる
    have.sort()
    if i!=k:
      for h in range(k-i):
        if have==[] or have[0]>=0:
          break
        del have[0]
      #いらない宝石を可能な限り詰めた状態
    if sum(have)>ans:
      ans=sum(have)
print(ans)
from operator import itemgetter
tik = [[1,2],[7,3],[4,4],[5,5],[3,5],[2,5],[9,6],[8,7],[6,6]]
dic = {"1":2,"7":3,"4":4,"5":5,"3":5,"2":5,"9":6,"8":7,"6":6}

n,k = map(int, input().split())
x = list(map(int, input().split()))
inf = float("INF")
dp = [0]+[-1]*(n+10)
q = []
for i in range(k):
    q.append([x[i],dic[str(x[i])]])

q = sorted(q, key=itemgetter(1), reverse=False)

s = []
p=0
t = 0
for i in range(n):
    for j in range(k):
        if i+q[j][1] <=n+10000000:
            if dp[i]!=-1:
            
                if  dp[i]==0:
                    dp[i+q[j][1]] = q[j][0]
                else:dp[i+q[j][1]] = str(dp[i])+str(q[j][0])
        #if i+q[j][1] ==n:
            #print(dp[20])
s = list(dp[n])
s.sort()
s = s[::-1]
print(''.join(s))

### FIXED CODE ###

from operator import itemgetter
tik = [[1,2],[7,3],[4,4],[5,5],[3,5],[2,5],[9,6],[8,7],[6,6]]
dic = {"1":2,"7":3,"4":4,"5":5,"3":5,"2":5,"9":6,"8":7,"6":6}

n,k = map(int, input().split())
x = list(map(int, input().split()))
dp = [0]+[-1]*(n+10)
q = []
for i in range(k):
    q.append([x[i],dic[str(x[i])]])

q = sorted(q, key=itemgetter(1), reverse=False)

s = []
p=0
t = 0
for i in range(n):
    for j in range(k):
        if i+q[j][1] <=n:
            if dp[i]!=-1:
            
                if  dp[i]==0:
                    ko = q[j][0]
                    dp[i+q[j][1]] = max(q[j][0],dp[i+q[j][1]])

                else:
                    ko = dp[i]+q[j][0]
                    dp[i+q[j][1]] = max(dp[i]*10+q[j][0], dp[i+q[j][1]])
        #if i+q[j][1] ==n:
            #print(dp[20])
s = list(str(dp[n]))
s.sort()
s = s[::-1]
print(''.join(s))
n,k = map(int,input().split())
s = input()
li = [0]
count = 1

for i in range(n-1):
    if s[i] != s[i+1]:
        li.append(count)
    count += 1
li.append(count)

print(li)

m = len(li)

if s[0] == '1':
    t = int(m/2-1)
    if k >= t:
        print(n)
    else:
        max1 = 0
        for i in range(t-k+1):
            max1 = max(li[2*(i+k)+1] - li[2*i],max1)
        print(max1)
else:
    t = int(m/2)
    if k >= t:
        print(n)
    else:
        max1 = li[2*k]
        for i in range(t-k):
            max1 = max(li[2*(i+k+1)] - li[2*i+1],max1)
        print(max1)


### FIXED CODE ###

n,k = map(int,input().split())
s = input()
li = [0]
count = 1

for i in range(n-1):
    if s[i] != s[i+1]:
        li.append(count)
    count += 1
li.append(count)

m = len(li)

if s[0] == '1':
    li.append(li[-1])
    li.append(li[-1])
    t = int(m/2-1)
    if k >= t:
        print(n)
    else:
        max1 = 0
        for i in range(t-k+2):
            max1 = max(li[2*(i+k)+1] - li[2*i],max1)
        print(max1)
else:
    li.append(li[-1])
    t = int(m/2)
    if k >= t:
        print(n)
    else:
        max1 = li[2*k]
        for i in range(t-k):
            max1 = max(li[2*(i+k+1)] - li[2*i+1],max1)
        print(max1)
map = input( int() )
print( 2*3.14*R )

### FIXED CODE ###

print(int(input())*6.3)
import sys
input = sys.stdin.readline
#区間の管理は　[a, b)で管理していることに注意

# INT_MIN = -10 ** 18
# MAX_N = 4 * 10 ** 5
# MAX_N = 20


# def init(n_):
#     #簡単にするために2のべき乗に揃える
#     n = 1
#     while n <= n_:
#         n *= 2
#     return n

#初期化
N = int(input())
# n = 1
# while n <= N:
#     n *= 2

n = 131073
data = [0] * n
# data = [0] * (2 * n - 1)

def update(k, a):
    k = k + n - 1
    # data[k] = a
    while k >= 0:
        data[k] = max(a, data[k])
        k = (k - 1) // 2
        # data[k] = max(data[2 * k + 1], data[2 * k + 2])

def query(a, b, k = 0, l = 0, r = n):
    if r <= a or b <= l:
        return 0
    elif a <= l and r <= b:
        return data[k]
    else:
        return max(query(a, b, 2 * k + 1, l, (l + r)//2), query(a, b, 2 * k + 2, (l + r)//2, r))

H = tuple(map(int, input().split()))
A = tuple(map(int, input().split()))

# ans = 0

dp = [A[0]] + [0] * (N - 1)
update(H[0] - 1, A[0])
for i in range(1, N):
    # h = int(input())
    # a = int(input())
    dp[i] = query(0, H[i] - 1) + A[i]
    # h = H[i]
    # a = A[i]
    # tmp = query(1, h + 1) #[1, h)での最大値
    # print (h, tmp)
    update(H[i] - 1, dp[i])
    # ans = max(ans, tmp + a)
    # print (data)

print (max(dp))

### FIXED CODE ###

def main():
    import sys
    input = sys.stdin.readline
    #区間の管理は　[a, b)で管理していることに注意

    # INT_MIN = -10 ** 18
    # MAX_N = 4 * 10 ** 5
    # MAX_N = 20


    # def init(n_):
    #     #簡単にするために2のべき乗に揃える
    #     n = 1
    #     while n <= n_:
    #         n *= 2
    #     return n

    #初期化
    N = int(input())
    # n = 1
    # while n <= N:
    #     n *= 2

    n = 262144
    data = [0] * (2 * n - 1)

    def update(k, a):
        k = k + n - 1
        # data[k] = a
        while k >= 0:
            data[k] = max(a, data[k])
            k = (k - 1) // 2
            # data[k] = max(data[2 * k + 1], data[2 * k + 2])

    def query(a, b, k, l, r):
        if r <= a or b <= l:
            return 0
        elif a <= l and r <= b:
            return data[k]
        else:
            return max(query(a, b, 2 * k + 1, l, (l + r)//2), query(a, b, 2 * k + 2, (l + r)//2, r))

    H = tuple(map(int, input().split()))
    A = tuple(map(int, input().split()))

    # ans = 0

    dp = [A[0]] + [0] * (N - 1)
    update(H[0] - 1, A[0])
    for i in range(1, N):
        # h = int(input())
        # a = int(input())
        dp[i] = query(0, H[i] - 1, 0, 0, n) + A[i]
        # h = H[i]
        # a = A[i]
        # tmp = query(1, h + 1) #[1, h)での最大値
        # print (h, tmp)
        update(H[i] - 1, dp[i])
        # ans = max(ans, tmp + a)
        # print (data)

    print (query(0, N, 0, 0, n))

if __name__ == '__main__':
    main()
import collections
mat = [map(int, raw_input().split(' ')) for _ in range(int(raw_input()))]
q = collections.deque([(0,0)])
moves = []
while(q):
	i,j = q.popleft()
	if mat[i][j] % 2:
		if j + 1 < len(mat[0]):
			moves.append([(i,j), (i, j + 1)])
			q.append((i,j + 1))
		elif i + 1 < len(mat):
			moves.append([(i,j), (i+1, j)])
			q.append((i + 1,j ))
print len(moves)
for u,v in moves: print u[0],u[1], v[0], v[1]

### FIXED CODE ###

import collections
h,w = map(int, raw_input().split())
mat = [map(int, raw_input().split(' ')) for _ in range(h)]
elems = [(i,j) for i in range(len(mat)) for j in range(len(mat[0]))]
elems.sort(key = lambda x: x[0] + x[1])
q = collections.deque(elems)
moves = []
while(q):
	i,j = q.popleft()
	if mat[i][j] % 2:
		if j + 1 < len(mat[0]):
			mat[i][j] -= 1
			mat[i][j+1] += 1
			moves.append([(i+1,j+1), (i+1, j + 2)])
			#q.append((i,j + 1))
		elif i + 1 < len(mat):
			mat[i][j] -=1
			mat[i+1][j] += 1
			moves.append([(i+1,j+1), (i+2, j+1)])
			#q.append((i + 1,j ))
print len(moves)
for u,v in moves: print u[0],u[1],v[0],v[1]
a = [a,i,u,e,o]
n = str(input())

if n in a:
    print('vowel')
else:
    print('consonant')

### FIXED CODE ###

a = ['a','i','u','e','o']
n = str(input())
 
if n in a:
    print('vowel')
else:
    print('consonant')
N = int(input().strip())

n_list = [[] for i in range(N)]
d = [0] * N

for i in range(N-1):
    a, b = map(int, input().strip().split())
    a -= 1
    b -= 1
    n_list[a].append([b,i])
    n_list[b].append([a,i])
    d[a] += 1
    d[b] += 1


#print(n_list)
#print(d)

d_dict = {}
for i in range(N):
    d_dict[i] = d[i]
tmp = sorted(d_dict.items(), key = lambda x:x[1], reverse = True)

colors = [0] * (N)

root = tmp[0][0]

def paint(node, parent_edge_id):
    #print(node, parent_edge_id)
    tmp_color = 1
    for edge in n_list[node]:
        #print("ege:", edge)
        if edge[1] != parent_edge_id:
            if parent_edge_id != -1 and tmp_color == colors[parent_edge_id]:
                tmp_color += 1
            colors[edge[1]] = tmp_color
            paint(edge[0], edge[1])
            tmp_color += 1

    
try:
    paint(tmp[0][0], -1)
except IndexError:
    print(0)
print(tmp[0][1]) # color num 
for i in range(N-1):
    print(colors[i])

### FIXED CODE ###

import sys
N = int(input().strip())

n_list = [[] for i in range(N)]
d = [0] * N

for i in range(N-1):
    a, b = map(int, input().strip().split())
    a -= 1
    b -= 1
    n_list[a].append([b,i])
    n_list[b].append([a,i])
    d[a] += 1
    d[b] += 1


#print(n_list)
#print(d)

d_dict = {}
for i in range(N):
    d_dict[i] = d[i]
tmp = sorted(d_dict.items(), key = lambda x:x[1], reverse = True)

colors = [0] * (N)

root = tmp[0][0]

def paint(node, parent_edge_id):
    #print(node, parent_edge_id)
    tmp_color = 1
    for edge in n_list[node]:
        #print("ege:", edge)
        if edge[1] != parent_edge_id:
            if parent_edge_id != -1 and tmp_color == colors[parent_edge_id]:
                tmp_color += 1
            colors[edge[1]] = tmp_color
            paint(edge[0], edge[1])
            tmp_color += 1

    
sys.setrecursionlimit(10**7)
paint(tmp[0][0], -1)
print(tmp[0][1]) # color num 
for i in range(N-1):
    print(colors[i])