Harryxun/stf_run huggingface dataset:
j = 1
def dfs(graph, start, result, visited=None):
    global j
    if visited == None:
        visited = []
    visited.append(start)
    result[start][1]  = j
    for next in graph[start][2:]:
        if next in visited:
            continue
        j += 1
        dfs(graph, next, result, visited)
    else:
        j += 1
        result[start][2] = j

n = int(input())
g = [[]]
r = [[i,0,0] for i in range(n + 1)]

for i in range(n):
    g.append(list(map(int, input().split())))
dfs(g,1,r)
for i in range(1:n+1)
    print(*r[i])

### FIXED CODE ###

j = 1

def dfs(graph, start, result, visited=None):
    global j
    if visited == None:
        visited = []
    visited.append(start)
    result[start][1]  = j
    for next in graph[start][2:]:
        if next in visited:
            continue
        j += 1
        dfs(graph, next, result, visited)
    else:
        j += 1
        result[start][2] = j

n = int(input())
g = [[]]
r = [[i,0,0] for i in range(n + 1)]
v = []

for i in range(n):
    g.append(list(map(int, input().split())))


for i in range(1, n + 1):
    if i in v:
        continue
    dfs(g,i,r,v)
    j += 1

for i in range(1,n+1):
    print(*r[i])
N = int(input())
xyh = [list(map(int,input().split())) for i in range(N)]

for cx in range(101):
  for cy in range(101):
    h = abs(xyh[0][0] - cx) + abs(xyh[0][1] - cy) + xyh[0][2]
    for i in range(1, N):
      if abs(xyh[i][0] - cx) + abs(xyh[i][1] - cy) + xyh[i][2] != h:
        break
    else:
      print(' '.join(map(str, [cx,cy,h])))
      exit()
else:
  raise Exception('aaa!!!')

### FIXED CODE ###

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

xyh_hNonzero = sorted(xyh, reverse=True, key=lambda x:x[2])[0]

for cx in range(101):
  for cy in range(101):
    h = abs(xyh_hNonzero[0] - cx) + abs(xyh_hNonzero[1] - cy) + xyh_hNonzero[2]
    for i in range(N):
      if xyh[i][2] == 0:
        if abs(xyh[i][0] - cx) + abs(xyh[i][1] - cy) < h:
          break
      elif abs(xyh[i][0] - cx) + abs(xyh[i][1] - cy) + xyh[i][2] != h:
        break
    else:
      print(' '.join(map(str, [cx,cy,h])))
      exit()
else:
  raise Exception('aaa!!!')
def main():
  N = int(input())
  A = [int(x) for x in input().split()]
  
  B = [0] * N
  for i in range(N):
    e = int(A[N-i-1])
    B[e] = B[e] + 1
  
  for i in range(N):
    print(B[i])
    
if __name__ == '__main__':
  main()

### FIXED CODE ###

def main():
  N = int(input())
  A = [int(x) for x in input().split()]
  
  B = [0] * N    
  for i in range(N-1):
      B[A[N-i-2]-1] += 1
  
  for i in range(N):
    print(B[i])
    
if __name__ == '__main__':
  main()
#! /usr/bin/env python
# -*- coding: utf-8 -*-

from numba import jit

sN = []
sQ = []
Q = 0
N = 0


@jit
def gor(pos):
    for i in range(Q):
        if sN[pos] == sQ[i]['t']:
            if sQ[i]['d'] == 'R':
                pos = pos + 1
            else:
                pos = pos - 1

            if pos < 0:
                return False
            if pos > N - 1:
                return True

    return False


@jit
def getr():
    l = 0
    r = N - 1
    res = N
    while r >= l:
        mid = (l + r) // 2
        if gor(mid):
            res = mid
            r = mid - 1
        else:
            l = mid + 1
    return res


@jit
def gol(pos):
    for i in range(Q):
        if sN[pos] == sQ[i]['t']:
            if sQ[i]['d'] == 'L':
                pos = pos - 1
            else:
                pos = pos + 1

            if pos > N - 1:
                return False
            if pos < 0:
                return True

    return False


@jit
def getl():
    l = 0
    r = N - 1
    res = -1
    while l <= r:
        mid = (l + r) // 2
        if gol(mid):
            res = mid
            l = mid + 1
        else:
            r = mid - 1
    return res


if __name__ == '__main__':
    N, Q = map(int, input().split())  # N, Q for number

    sN = input()  # squares

    for i in range(0, Q):
        t, d = input().split()
        sQ.append({'t': t, 'd': d})

    removed_l = getl() + 1
    removed_r = N - getr()

    print(N - removed_l - removed_r)


### FIXED CODE ###

#! /usr/bin/env python
# -*- coding: utf-8 -*-

sN = []
sQ = []
dQ = []
Q = 0
N = 0


def gor(pos):
    for i in range(Q):
        if sN[pos] == sQ[i]:
            if dQ[i] == 'R':
                pos = pos + 1
            else:
                pos = pos - 1

            if pos < 0:
                return False
            if pos > N - 1:
                return True

    return False


def getr():
    l = 0
    r = N - 1
    res = N
    while r >= l:
        mid = (l + r) // 2
        if gor(mid):
            res = mid
            r = mid - 1
        else:
            l = mid + 1
    return res


def gol(pos):
    for i in range(Q):
        if sN[pos] == sQ[i]:
            if dQ[i] == 'L':
                pos = pos - 1
            else:
                pos = pos + 1

            if pos > N - 1:
                return False
            if pos < 0:
                return True

    return False


def getl():
    l = 0
    r = N - 1
    res = -1
    while l <= r:
        mid = (l + r) // 2
        if gol(mid):
            res = mid
            l = mid + 1
        else:
            r = mid - 1
    return res


if __name__ == '__main__':
    N, Q = map(int, input().split())  # N, Q for number

    sN = input()  # squares

    for i in range(0, Q):
        t, d = input().split()
        sQ.append(t)
        dQ.append(d)
        #sQ.append({'t': t, 'd': d})

    removed_l = getl() + 1
    removed_r = N - getr()

    print(N - removed_l - removed_r)
import numpy as np

n,d= int(input())

print(int(np.ceil(n/(2*d+1))))


### FIXED CODE ###

import numpy as np

n, d = map(int, input().split())

print(int(np.ceil(n/(2*d+1))))
h, w = map(int, input().split())
mass = [list(input()) for _ in range(h)]

ans = "Yes"
for i in range(h):
    for j in range(w):
        if mass[i][j] == "#":
            if i < w-1:
                if mass[i+1][j] == "#":
                    continue
            if 0 < i:
                if mass[i-1][j] == "#":
                    continue
            if j < h-1:
                if mass[i][j+1] == "#":
                    continue
            if 0 < j:
                if mass[i][j-1] == "#":
                    continue
            ans = "No"
            break

print(ans)



### FIXED CODE ###

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

ans = "Yes"
for i in range(h):
    for j in range(w):
        if mass[i][j] == "#":
            if i < h-1:
                if mass[i+1][j] == "#":
                    continue
            if 0 < i:
                if mass[i-1][j] == "#":
                    continue
            if j < w-1:
                if mass[i][j+1] == "#":
                    continue
            if 0 < j:
                if mass[i][j-1] == "#":
                    continue
            ans = "No"
            break

print(ans)
While 1:
    m,f,r=map(int,input().split())
    if m==f==r==-1:break
    a=m+f
    if a >= 80:print('A')
    elif a >= 65:print('B')
    elif a >= 50:print('C')
    elif a >= 30:
        if r > 50:print('C')
        else:print('D')
    else:print('F')

### FIXED CODE ###

while True:
    m,f,r=map(int,input().split())
    if m==f==r==-1:break
    a=m+f
    if m==-1 or f==-1:print('F')
    elif a >= 80:print('A')
    elif a >= 65:print('B')
    elif a >= 50:print('C')
    elif a >= 30:
        if r >= 50:print('C')
        else:print('D')
    else:print('F')
a, b, c, d, e, f = [int(i) for i in input().split()]
max_density = 0
#water = 0
#sugar = 0
for i_1 in range(f//(a*100)+1):
    for i_2 in range((f-100*a)//(b*100)+1):
        for i_3 in range(((i_1*a+i_2*b)*e)//c+1):
            i_4 = min((((i_1*a+i_2*b)*e)-i_3*c)//d , (f-(i_1*100*a+i_2*100*b+i_3*c))//d)
            if i_1 == 0 and i_2 == 0:
                break
            if (i_3*c + i_4*d)/(i_1*100*a+i_2*100*b+i_3*c + i_4*d) > max_density:
                max_density = (i_3*c + i_4*d)/(i_1*100*a+i_2*100*b+i_3*c + i_4*d)
                water = i_1*100*a+i_2*100*b
                sugar = i_3*c + i_4*d
print(water+sugar, sugar)

### FIXED CODE ###

a, b, c, d, e, f = [int(i) for i in input().split()]
max_density = 0.0
water = 0
sugar = 0
for i_1 in range(f//(a*100)+1):
    for i_2 in range((f-100*a*i_1)//(b*100)+1):
        for i_3 in range(min(((i_1*a+i_2*b)*e)//c , (f-(i_1*100*a+i_2*100*b))//c)+1):
            i_4 = min((((i_1*a+i_2*b)*e)-i_3*c)//d , (f-(i_1*100*a+i_2*100*b+i_3*c))//d)
            if i_1 == 0 and i_2 == 0:
                break
            if (i_3*c + i_4*d)/(i_1*100*a+i_2*100*b+i_3*c + i_4*d) >= max_density:
                max_density = (i_3*c + i_4*d)/(i_1*100*a+i_2*100*b+i_3*c + i_4*d)
                water = i_1*100*a+i_2*100*b
                sugar = i_3*c + i_4*d
print(water+sugar, sugar)
N=int(input())
data=[]
no10=[]
for i in range (N):
    a=int(input())
    data.append(a)
    if a%10!=0:
        no10.append(a)
        
ans=sum(data)
if ans%10!=0:
    print (ans)
elif len(no10)!=0:
    print(ans-no10[0])
else:
    print (0)

### FIXED CODE ###

A,B=map(int,input().split())
if (A+B)>=10:
    print ('error')
else:
    print (A+B)
a,b=int(input().split())
c=a*b
if c%2==0:
  print("Even")
else:
  print("Odd")

### FIXED CODE ###

a,b=(int(x) for x in input().split())
c=a*b
if c%2==0:
  print("Even")
else:
  print("Odd")
N = int(input())
res = [0 for i in range(100000)]
def lucas(N):
	if N == 0:
		return 2
	elif N == 1:
		return 1
	elif res[N] != 0:
		return res[N]
	return lucas(N-1) + lucas(N-2)

print(lucas(N))

### FIXED CODE ###

a = list(input())
if ((a[0] == a[1]) and (a[1] == a[2])) or ((a[1] == a[2]) and (a[2] == a[3])):
	print("Yes")
else:
	print("No")
n = int(input())
h = list(map(int, input().split()))
x = []
i = 0
ans = 0
while i != n - 1:
  while i != n - 1:
    if h[i] < h[i + 1]:
      break
    ans += 1
    i += 1
  x.append(ans)
print(max(x))

### FIXED CODE ###

n = int(input())
h = list(map(int, input().split()))
i = 0
count = 0
ans = []
while i < n - 1:
  if h[i] < h[i + 1]:
    ans.append(count)
    count = 0
  else:
    count += 1
  i += 1
ans.append(count)
print(max(ans))
n,k = input().split()
num_list = list(map(int,input().split()))

num_list.sort()
ans = 0

for i in range(k):
  ans += num_list[i]
else:
  print(ans)

### FIXED CODE ###

n,k = map(int,input().split())
num_list = list(map(int,input().split()))

num_list.sort()
ans = 0

for i in range(k):
  ans += num_list[i]
else:
  print(ans)
N = int(input())
F = [list(map(int, input().split())) for i in range(N)]
P = [list(map(int, input().split())) for j in range(N)]  
max = -9999999999  
for i in range(1, 2**10):
    sum = 0
    for j in range(N):
        count = 0
        for k in range(10):
            if ((i >> k)&1) == 1 and F[j][k] == 1:
                count += 1
        sum += P[j][count]
    max = max(max, sum)  
print(max)

### FIXED CODE ###

N = int(input())
F = [list(map(int, input().split())) for i in range(N)]
P = [list(map(int, input().split())) for j in range(N)]  
m = -9999999999  
for i in range(1, 2**10):
    s = 0
    for j in range(N):
        count = 0
        for k in range(10):
            if ((i >> k)&1) == 1 and F[j][k] == 1:
                count += 1
        s += P[j][count]
    m = max(m, s)  
print(m)
import numpy as np
from numba import njit

N = int(input())
scores = np.array([int(i) for i in input().split()], dtype='int64')
dpt = np.full((N, N), -10**18, dtype='int64')

#@njit('i8(i8[:],i8[:,:],i8,i8)', cache=True)
def get_max_score(scores, dpt, i, j):
    if i == j:
        dpt[i][j] = scores[i]
        return scores[i]
    else:
        if dpt[i][j] != -10**18:
            return dpt[i][j]
        result = max(scores[i] - get_max_score(scores, dpt, i+1, j), scores[j] - get_max_score(scores, dpt, i, j-1))
        dpt[i][j] = result
        return result

print(get_max_score(scores, dpt, 0, len(scores)-1))


### FIXED CODE ###

import numpy as np
from numba import njit

N = int(input())
scores = np.array(list(map(int, input().split())), dtype='int64')
dpt = np.full((N, N), -10**18, dtype='int64')

@njit('i8(i8[:],i8[:,:],i8,i8)', cache=True)
def get_max_score(scores, dpt, i, j):
    if i == j:
        dpt[i][j] = scores[i]
        return scores[i]
    else:
        if dpt[i][j] != -10**18:
            return dpt[i][j]
        result = max(scores[i] - get_max_score(scores, dpt, i+1, j), scores[j] - get_max_score(scores, dpt, i, j-1))
        dpt[i][j] = result
        return result

print(get_max_score(scores, dpt, 0, len(scores)-1))
def checkTriangle(a, b, c):
    if a + b > c and a + c > b and b + c > a:
        return True
    return False


def checkOct(a, b, c):
    a, b, c = [i * i for i in [a, b, c]]
    if a + b == c or a + c == b or b + c == a:
        return 0
    elif c < a + b or b < a + c or a < b + c:
        return 1
    else:
        return 2

for i in range(5):
    a, b, c = map(int, input())
    result = [0] * 3
    if checkTriangle(a, b, c):
        result[checkOct(a, b, c)] += 1
print(sum(result),*result)


### FIXED CODE ###

result = [0]*3
while True:
    a, b, c = sorted(map(int, input().split()))
    if a + b <= c:
        print(sum(result),*result)
        break
    flag = a ** 2 + b ** 2 - c*c
    if flag == 0:
        result[0] +=1
    elif flag >0:
        result[1] += 1
    else:
        result[2] += 1
import math
import sys
from collections import defaultdict

input = sys.stdin.readline
mod = 1000000007

n = int(input())

n2 = [1]
for _ in range(n):
    n2.append(n2[-1] * 2 % mod)

zero = 0
plus = defaultdict(int)
minus = defaultdict(int)

for _ in range(n):
    a, b = map(int, input().split())
    if a == 0 and b == 0:
        zero += 1
        continue
    p = math.gcd(a, b)
    a //= p
    b //= p
    if a * b > 0:
        plus[(abs(a), abs(b))] += 1
    else:
        minus[(abs(b), abs(a))] += 1

n -= zero

for k, v in plus.items():
    if minus[k] > 0:
        ans *= (n2[v] + n2[minus[k]] - 1)
        ans %= mod
        n -= v + minus[k]

ans *= n2[n]
ans = ans + zero - 1
ans %= mod
print(ans)


### FIXED CODE ###

import math
import sys
from collections import defaultdict

input = sys.stdin.readline
mod = 1000000007

n = int(input())

n2 = [1]
for _ in range(n):
    n2.append(n2[-1] * 2 % mod)

zero = 0
plus = defaultdict(int)
minus = defaultdict(int)

for _ in range(n):
    a, b = map(int, input().split())
    if a == 0 and b == 0:
        zero += 1
        continue
    elif a == 0:
        plus[(1, 0)] += 1
    elif b == 0:
        minus[(1, 0)] += 1
    else:
        p = math.gcd(a, b)
        a //= p
        b //= p
        if a * b > 0:
            plus[(abs(a), abs(b))] += 1
        else:
            minus[(abs(b), abs(a))] += 1

n -= zero
ans = 1

for k, v in plus.items():
    if minus[k] > 0:
        ans *= (n2[v] + n2[minus[k]] - 1)
        ans %= mod
        n -= v + minus[k]

ans *= n2[n]
ans %= mod
ans += zero - 1
ans %= mod
print(ans)
from collections import defaultdict
n, m = map(int, input().split())
nums = sorted([int(i) for i in input().split()])[::-1]

d = defaultdict(int)

for _ in range(m):
    b, c = map(int, input().split())
    d[c] += b


new_list = []
cnt = 0
for c, b in sorted(d.items(), key=lambda x: -x[0]):
    new_list += [c] * b
    cnt += b
    if cnt > 10000:
        break
tmp = sorted(nums + new_list)[::-1]
print(sum(tmp[:n]))


### FIXED CODE ###

# from collections import defaultdict
# n, m = map(int, input().split())
# nums = [int(i) for i in input().split()]
#
# num_freq = defaultdict(int)
#
# for _ in range(m):
#     b, c = map(int, input().split())
#     num_freq[c] += b
#
#
# new_list = []
# for num, freq in sorted(num_freq.items(), key=lambda x: -x[0]):
#     new_list += [num] * freq
#     if len(new_list) >= n:
#         break
# tmp = sorted(nums + new_list)[::-1]
# print(sum(tmp[:n]))

# ↑と同じ処理なのに↑のはREになる
n, m = map(int, input().split())
nums = list(map(int, input().split()))
exc = []

for i in range(m):
    exc.append(list(map(int, input().split())))
exc.sort(key=lambda x: x[1], reverse=True)
e = []
count = 0
for i in range(m):
    freq = exc[i][0]
    e += [exc[i][1]] * freq
    count += freq
    if count >= n:
        break
cards = sorted(nums + e, reverse=True)
print(sum(cards[:n]))
a, b = int(input().split())
if a + b >= 10:
  print("error")
else:
  print(a + b)

### FIXED CODE ###

a, b = map(int, input().split())
if a + b >= 10:
  print("error")
else:
  print(a + b)
import sys
S=input()
if len(S)>1:
    for i in range(n//2):
        s=S[2*i]
        if s=="L":
            print("No")
            sys.exit()
        s=S[2*i+1]
        if s=="R":
            print("No")
            sys.exit()
if n%2==1:
    s=S[-1]
    if s=="L":
        print("No")
        sys.exit()
print("Yes")

### FIXED CODE ###

import sys
S=input()
n=len(S)
if n>1:
    for i in range(n//2):
        s=S[2*i]
        if s=="L":
            print("No")
            sys.exit()
        s=S[2*i+1]
        if s=="R":
            print("No")
            sys.exit()
if n%2==1:
    s=S[-1]
    if s=="L":
        print("No")
        sys.exit()
print("Yes")
N, L = map(int, input().split())
s = sorted([input() for i in range(N)])

print(*s, sep="")


### FIXED CODE ###

i = list(map(int, input().split(" ")))
#print(s)
#print(s[1])
#import pdb; pdb.set_trace()

if  [5, 5, 7] == sorted(i):
    print("YES")
else:
    print("NO")
# -*- coding: utf-8 -*-
N, K = map(int, input().split())
P = list(map(int, input().split()))
C = list(map(int, input().split()))
k_max = 5001
score = [0] * N

for i in range(N):
  score_i = [-10**18-1] * k_max # iからスタートしてK回操作する場合の累積和
  score_i[0] = C[P[i]-1]
  index = P[i]-1
  for k in range(1, K):
    if index == i:
      # 既に進んだことがあるマスの場合
      
      # ループ終了インデックスからループ開始インデックスの累積和の差を確認
      loop_score = score_i[k-1] # 1ループで増えるスコア
      if loop_score > 0:
        loop_num = k # ループする要素数はk(indexが0 ~ k-1)
        
        tmp_score = [0] * k_max
        tmp_score[0] = (K//k -1) * loop_score
        tmp_index = index
        for j in range (1, loop_num + K%k + 1):
          tmp_score[j] = tmp_score[j-1] + C[P[tmp_index]-1]
          tmp_index = P[tmp_index]-1
        score[i] = max(tmp_score)
      else:
        score[i] = max(score_i)
      break
    else:
      if k == K-1:
        score_i[k] = score_i[k-1] + C[P[index]-1]
        score[i] = max(score_i)
        break   
    score_i[k] = score_i[k-1] + C[P[index]-1]
    index = P[index]-1
print(max(score))

### FIXED CODE ###

# -*- coding: utf-8 -*-
N, K = map(int, input().split())
P = list(map(int, input().split()))
C = list(map(int, input().split()))
k_max = 10100
score = [-10**18-1] * N

for i in range(N):
  score_i = [-10**18-1] * k_max # iからスタートしてK回操作する場合の累積和
  score_i[0] = C[P[i]-1]
  index = P[i]-1
  for k in range(1, K):
    if index == i:
      # 既に進んだことがあるマスの場合
      
      loop_score = score_i[k-1] # 1ループで増えるスコア
      if loop_score > 0:
        loop_num = k # ループする要素数はk(indexが0 ~ k-1)
        
        tmp_score = [-10**18-1] * k_max
        tmp_score[0] = (K//k -1) * loop_score
#        print("loop_score", loop_score)
#        print("tmp_score", tmp_score)
        tmp_index = index
#        print("loop_num + K%k + 1", loop_num + K%k + 1)
        for j in range (1, loop_num + K%k + 1):
          tmp_score[j] = tmp_score[j-1] + C[P[tmp_index]-1]
          tmp_index = P[tmp_index]-1
#        print("max(tmp_score)", max(tmp_score))
        score_i[k] = max(tmp_score)
      break
    score_i[k] = score_i[k-1] + C[P[index]-1]
    index = P[index]-1
  score[i] = max(score_i)
print(max(score))
n,k=map(int,input().split())
s=input()
a=[]
a.append(0)
tmp=1
for i in range(len(s)-1):
	if s[i] != s[i+1]:
		a.append(i+1)
a.append(n)

#print(a)

if len(a)==2:
	print(a[1])
else:
	if s[-1]=='0':
		m=2*k
	else:
		m=2*k+1
	_max=a[m]
	i=len(a)-1
	while i-m>=0:
		tmp=a[i]-a[i-m]
		#print('i:{} tmp:{}'.format(i,tmp))
		if tmp>_max:
			_max=tmp
		i-=1
	print(_max)

### FIXED CODE ###

n,k=map(int,input().split())
s=input()
a=[]
a.append(0)
for i in range(len(s)-1):
	if s[i] != s[i+1]:
		a.append(i+1)
a.append(n)
if s[-1]=='0':
	m=2*k
else:
	m=2*k+1
t=4*k+1
_max=0
i=len(a)-1
if i- m<0:
	print(n)
else:
	while i-m>=0:
		tmp=a[i]-a[i-m]
		#print('i:{} tmp:{}'.format(i,tmp))
		if tmp>_max:
			_max=tmp
		m=t-m
		i-=1
	if a[i]>_max:
		_max=a[i]
	print(_max)
import sys

#入力する値の個数N
N = input()

#入力される値 A
A = list(map(int, input().split()))

#print(N)
#print(A)
ans = 1
if 0 in A:
    print("-1")
    sys.exit()


for i in A:
    #print(i)
    ans *= i
    #print(ans)
    if ans > 10**18:
        print("-1")
        sys.exit()

print(ans)

### FIXED CODE ###

#入力される値A B
A, B = map(int, input().split())

#出力される値
print(A*B)
N,M,X,Y = map(int, input().split())
num_list = [list(map(int, input().split())) for _ in range(2)]
 
x_max = max(num_list[0])
y_min = min(num_list[1])
 
if x_max >= y_max:
    print('War')
elif x_max < X or y_max > Y:
    print('War')
else:
    print('No war')

### FIXED CODE ###

N,M,X,Y = map(int, input().split())
num_list = [list(map(int, input().split())) for _ in range(2)]

Z = list(range(X+1,Y+1))

for z in Z:
    if max(num_list[0]) < z and min(num_list[1]) >= z:
        print('No War')
        break
    if z == Z[-1]:
        print('War')
"""
5 3
1 9
1 7
2 6
2 5
3 1
->26
7 4
1 1
2 1
3 1
4 6
4 5
4 5
4 5
->25
6 5
5 1000000000
2 990000000
3 980000000
6 970000000
6 960000000
4 950000000
->4900000016
"""

from collections import deque
n,k= map(int,input().split())
td=[]
for i in range(n):
    td.append(list(map(int,input().split())))
td.sort(key=lambda x:x[1],reverse=True)
select=[]
noselect=[]
cat=[]
for tdi in td:
    if tdi[0] in cat:
        noselect.append(tdi)
        continue
    select.append(tdi)
    cat.append(tdi[0])
    if len(select)==k:
        break
i=0
while len(select) < k:
    select.append(noselect[i])
    i+=1
noselect=noselect[i:]

select.sort(key=lambda x:x[1])
select=deque(select)
#cat=list(set([tdi[0] for tdi in select]))
for no in noselect:
    if no[0] not in cat:
        continue
    if (2 * len(cat)) - 1 < no[1] - select[0][1]:
        select.popleft()
        select.append(no)
        cat=list(set([tdi[0] for tdi in select]))
    else:
        break
print(sum([tdi[1] for tdi in select])+(len(cat)**2))


### FIXED CODE ###

a,b,c=map(int,input().split())
print((a*b)//2)
N, M=map(int,input().split())
dic={}
def f(num):
    if not num in dic:
        lis=[]
        for i in range(1,int(num**0.5)+1):
            if num%i==0:
                lis.append(i)
                if i**2!=num:
                    lis.append(num//i)
        lis.sort()
        dic[num]=lis
    return dic[num]

res=0
def c(m,n):
    if n>0:
        for i in f(m):
            j=m//i
            c(j,n-1)
    else:
        global res
        res+=len(f(m))

c(M,n=N-2)
print(res)   

### FIXED CODE ###

def cmb(n,r):
    r=min(r,n-r)
    result=1
    for i in range(n-r+1,n+1):
        result*=i
    for i in range(1,r+1):
        result//=i
    return result

def factorize(n):
    i=2
    result={}
    while True:
        if i**2>n:
            break
        count=0
        while n%i==0:
            n//=i
            count+= 1
        if count!=0:
            result[i]=count
        i+=1
    if n>1:
        result[n]=1
    return result


N,M = map(int,input().split())
l = factorize(M)

r = 1
for i,j in l.items():
    r *= cmb(j+N-1,j)%(10**9+7)
    r %= (10**9+7)
print(r)
T = int(input())
X = int(input())
print(float(T)/float(X))

### FIXED CODE ###

T,X =map(int, input().split())
print(float(T)/float(X))