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

import sys
from math import ceil, floor, sqrt, sin, cos, pi
from itertools import accumulate, permutations, combinations
from fractions import gcd # 最大公約数
from collections import deque, Counter
from operator import itemgetter
from heapq import heappop,heappush
sys.setrecursionlimit(10**7)
def lcm(x, y): return ((x * y) // gcd(x, y)) # 最小公倍数
# list(map(int, input().split()))
n = int(input())
v = list(map(float, input().split()))

ans = []
for x in permutations(v):
    p = x[0]
    for i in range(1, n):
        p = (p + x[i])/2.0
    ans.append(p)
print(max(ans))

### FIXED CODE ###

import sys
from math import ceil, floor, sqrt, sin, cos, pi
from itertools import accumulate, permutations, combinations
from fractions import gcd # 最大公約数
from collections import deque, Counter
from operator import itemgetter
from heapq import heappop,heappush
sys.setrecursionlimit(10**7)
def lcm(x, y): return ((x * y) // gcd(x, y)) # 最小公倍数
# list(map(int, input().split()))
n = int(input())
v = list(map(float, input().split()))

v.sort()
ans = v[0]
for i in range(1, n):
    ans = (ans + v[i])/2
print(ans)
### BUGGY CODE ###

N = int(input())
A = [int(a) for a in input().split()] + [0] * 2
X = [[-10**10] * (N+1) for _ in range(N+1)]
X[A[0]][A[1]] = 0
ans = 0
ma = 0
MA = [-5] * (N+1)
MA[A[0]] = MA[A[1]] = 0
for i in range(N):
    B = A[i*3+2:i*3+5]
    cnt = len(set(B))
    if cnt == 1:
        ans += 1
    elif cnt == 2:
        a1 = B[0]^B[1]^B[2]
        a2 = (sum(B) - a1) // 2
        X[a1], X[a1][a2], X[a2][a2] = [max(X[a2][j] + 1, X[j][a2] + 1, MA[j]) for j in range(N+1)], max(ma, X[a2][a2] + 1), max(ma, X[a1][a1] + 1)
        X[a2] = [max(x, m) for x, m in zip(X[a2], MA)]
        MA = [max(m, x1, x2) for m, x1, x2 in zip(MA, X[a1], X[a2])]
        MA[a1] = max(MA[a1], max(X[a1]))
        MA[a2] = max(MA[a2], X[a1][a2], X[a2][a2])
        ma = max(ma, MA[a1], MA[a2])
    else:
        a, b, c = B
        X[a][b], X[a][c], X[b][c] = max(ma, X[c][c] + 1), max(ma, X[b][b] + 1), max(ma, X[a][a] + 1)
        X[a] = [max(x, m) for x, m in zip(X[a], MA)]
        X[b] = [max(x, m) for x, m in zip(X[b], MA)]
        X[c] = [max(x, m) for x, m in zip(X[c], MA)]
        MA[a] = max(MA[a], max(X[a]))
        MA[b] = max(MA[b], X[a][b], max(X[b]))
        MA[c] = max(MA[c], X[a][c], X[b][c], max(X[c]))
        MA = [max(m, xa, xb, xc) for m, xa, xb, xc in zip(MA, X[a], X[b], X[c])]
        ma = max(ma, MA[a], MA[b], MA[c])

print(ans + max(ma, max(max(x) for x in X)))

### FIXED CODE ###

N = int(input())
A = [int(a) for a in input().split()] + [0] * 2
X = [[-10**10] * (N+1) for _ in range(N+1)]
X[A[0]][A[1]] = 0
ans = 0
ma = 0
MA = [-10**10] * (N+1)
MA[A[0]] = MA[A[1]] = 0
for i in range(N):
    B = A[i*3+2:i*3+5]
    cnt = len(set(B))
    if cnt == 1:
        ans += 1
    elif cnt == 2:
        a1 = B[0]^B[1]^B[2]
        a2 = (sum(B) - a1) // 2
        # 
        # X[a1], X[a2][a2] = [max(X[a2][j] + 1, X[j][a2] + 1, X[a1][j], X[j][a1]) for j in range(N+1)], max(ma, X[a2][a2], X[a1][a1] + 1)
        # X[a1], X[a1][a2], X[a2][a2] = [max(X[a2][j] + 1, X[j][a2] + 1, X[a1][j], X[j][a1]) for j in range(N+1)], max(X[a1][a2], X[a2][a2] + 1, ma), max(ma, X[a2][a2], X[a1][a1] + 1)
        X[a1], X[a1][a2], X[a2][a2] = [max(X[a2][j] + 1, X[j][a2] + 1, MA[j]) for j in range(N+1)], max(X[a1][a2], X[a2][a2] + 1, ma), max(ma, X[a2][a2], X[a1][a1] + 1)
        #
        X[a2] = [max(X[a2][j], MA[j]) for j in range(N+1)]
        MA = [max(MA[j], X[a1][j], X[a2][j]) for j in range(N+1)]
        MA[a1] = max(MA[a1], max(X[a1]), X[a2][a1])
        MA[a2] = max(MA[a2], X[a1][a2], X[a2][a2])
        ma = max(ma, MA[a1], MA[a2])
    else:
        a, b, c = B
        X[a][b], X[a][c], X[b][c] = max(X[a][b], ma, X[c][c] + 1), max(X[a][c], ma, X[b][b] + 1), max(X[b][c], ma, X[a][a] + 1)
        X[a] = [max(X[a][j], MA[j]) for j in range(N+1)]
        X[b] = [max(X[b][j], MA[j]) for j in range(N+1)]
        X[c] = [max(X[c][j], MA[j]) for j in range(N+1)]
        MA[a] = max(MA[a], max(X[a]))
        MA[b] = max(MA[b], X[a][b], max(X[b]))
        MA[c] = max(MA[c], X[a][c], X[b][c], max(X[c]))
        MA = [max(MA[j], X[a][j], X[b][j], X[c][j]) for j in range(N+1)]
        ma = max(ma, MA[a], MA[b], MA[c])

print(ans + max(ma, max(max(x) for x in X)))
### BUGGY CODE ###

import math
N=int(input())
Candidate=-(-math.sqrt(N)//1)
tens=0
while N%Candidate!=0:
    Candidate+=1
while Candidate//pow(10,tens)!=0:
    tens+=1
print(tens)

### FIXED CODE ###

import math
N=int(input())
Candidate=-(-math.sqrt(N)//1)
while N%Candidate!=0:
    Candidate-=1
Candidate=N/Candidate
print(len(str(Candidate))-2)
### BUGGY CODE ###


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

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], A[0])
for i in range(1, N):
    # h = int(input())
    # a = int(input())
    dp[i] = query(1, H[i]) + A[i]
    # h = H[i]
    # a = A[i]
    # tmp = query(1, h + 1) #[1, h)での最大値
    # print (h, tmp)
    update(H[i], 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()
### BUGGY CODE ###

# coding: utf-8
# Your code here!
import sys
input = sys.stdin.readline

def itercomb(n,k):
    _a = 2**k-1
    yield _a
    _ALL=2**n
    while 1:
        _x = _a & -_a
        _y = _a + _x
        _a = (((_a & ~_y) // _x) >> 1) | _y
        if _a >= _ALL: break
        yield _a

MOD=10**9+7
n=int(input())
A= [[int(i) for i in input().split()] for j in range(n)]

dp = [0]*(2**n)
dp[0] = 1
"""
for m in range(1,n+1):
    for a in itercomb(n,m):
        dp[a] = sum(dp[a^2**c] for c in range(n) if 2**c&a and A[m-1][c])%MOD

for a in range(1,2**n):
    m=bin(a).count("1")
    dp[a] = sum(dp[a^2**c] for c in range(n) if 2**c&a and A[m-1][c])%MOD


_ALL=2**n
for m in range(1,n+1):
    a = 2**m-1
    while a < _ALL:
        ans=0
        for c in range(n):
            if 2**c&a and A[m-1][c]:
                ans += dp[a^2**c]
                ans%=MOD
        dp[a] = ans
        x = a & -a
        y = a + x
        a = (((a & ~y) // x) >> 1) | y

for m in range(1,n+1):
    for a in itercomb(n,m):
        ans=0
        for c in range(n):
            if 2**c&a and A[m-1][c]:
                ans += dp[a^2**c]
                ans%=MOD
        dp[a] = ans

for m in range(1,n+1):
    for a in itercomb(n,m):
        ans=0
        for c,i in enumerate(A[m-1]):
            if i and 2**c&a:
                ans += dp[a^2**c]
                ans%=MOD
        dp[a] = ans
"""
_ALL=2**n
for m in range(1,n+1):
    a = 2**m-1
    while a < _ALL:
        ans=0
        for c,i in enumerate(A[m-1]):
            if i and 2**c&a:
                ans += dp[a^2**c]
                ans%=MOD
        dp[a] = ans
        x = a & -a
        y = a + x
        a = (((a & ~y) // x) >> 1) | y


print(dp[2**n-1])

### FIXED CODE ###

# coding: utf-8
# Your code here!
import sys
input = sys.stdin.readline

def itercomb(n,k):
    _a = (1<<k)-1
    yield _a
    while 1:
        _x = _a & -_a
        _y = _a + _x
        _a = (((_a & ~_y) // _x) >> 1) | _y
        if _a >= _ALL: break
        yield _a

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

MOD=10**9+7
_ALL=1<<n
dp = [0]*(_ALL)
dp[0] = 1

for m in range(1,n+1):
    for a in itercomb(n,m):
        for c,i in enumerate(A[m-1]):
            if (1<<c)&a and i:
                dp[a] += dp[a^(1<<c)]
                if dp[a] > MOD:
                    dp[a] -= MOD


#print(dp)
print(dp[2**n-1])
### BUGGY CODE ###

import sys

input = sys.stdin.readline
n, k = map(int, input().split())
h = list(map(int, input().split()))
dp = [-1] * n
dp[0] = 0
dp[1] = abs(h[0] - h[1])
if n == 2:
    print(dp[1])
else:
    for i in range(2, n):
        if i <= k:
            for j in range(1, i + 1):
                mind = abs(h[i] - h[i - j]) + dp[i - j]
                dp[i] = min(dp[i], mind) if dp[i] != -1 else mind
        else:
            for j in range(1, k + 1):
                mind = abs(h[i] - h[i - j]) + dp[i - j]
                dp[i] = min(dp[i], mind) if dp[i] != -1 else mind
    print(dp[n - 1])


### FIXED CODE ###

import sys


def input():
    return sys.stdin.readline().strip()


def main():
    n, k = map(int, input().split())
    h = list(map(int, input().split()))
    dp = [0] * n
    dp[0] = 0
    dp[1] = abs(h[0] - h[1])

    for i in range(2, n):
        dp[i] = min(abs(h[i] - h[j]) + dp[j] for j in range(max(0, i - k), i))
    print(dp[n - 1])


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

N=int(input())
S=list(input())
ans=0
for i in range(N):
    for j in range(i+1,N):
        if S[i]==S[j]:
          continue
        for k in range(j+1,N):
            if k-j==j-i:
                continue
            if not (S[i]==S[j] or S[j]==S[k] or S[i]==S[k]):
                ans+=1
print(ans)

### FIXED CODE ###

N=int(input())
S=input()
totalPattern = S.count("R")*S.count("G")*S.count("B")
for i in range(N-1):
    for j in range(i+1,N):
        k=j+(j-i)
        if k>N-1:
            continue
        if not S[i] == S[j] and not S[i] == S[k] and not S[j] == S[k]:
            totalPattern-=1
print(totalPattern)
### BUGGY CODE ###

n = input()
S = map(int, raw_input().split())
q = input()
T = map(int, raw_input().split())

count   = 0
isExist = False
low     = 0
high    = n - 1
middle  = 0

for j in range(q):
    search = T[j]
    while True:
        middle = (high + low)/2
        print middle
        if S[middle] == search:
            count = count + 1
            break
        elif middle == 0:
            break
        elif search < S[middle]:
            high = middle - 1
        elif S[middle] < search:
            low = middle + 1

print count

### FIXED CODE ###

def binarySearch(n, S, search):
    low    = 1 - 1
    high   = n - 1
    middle = 0

    while low < high:
        middle = (high + low)/2
        if S[middle] == search or S[low] == search or S[high] == search:
            return 1
        elif search < S[middle]:
            high = middle - 1
        elif S[middle] < search:
            low = middle + 1
    return 0

n = input()
S = map(int, raw_input().split())
q = input()
T = map(int, raw_input().split())

count = 0

for j in range(q):
    search = T[j]
    count = count + binarySearch(n, S, search)

print count
### BUGGY CODE ###

H=int(input())
count=1
ans=0
while H//2!=1:
    count+=1
    H=H//2
for i in range(0,count+1):
    ans+=2**i
print(ans)

### FIXED CODE ###

H=int(input())
count=1
ans=0
if H==1:
    print(1)
    exit()
while H//2!=1:
    count+=1
    H=H//2
for i in range(0,count+1):
    ans+=2**i
print(ans)
### BUGGY CODE ###

N, M = map(int, input().split())
l_1 = [[] for i in range(N+1)]
l_2 = []
for i in range(M):
  p, y = map(int, input().split())
  l_1[p].append(y)
  l_2.append([p, y])
  
for i in range(N+1):
  l_1[i].sort()
    
for i in range(M):
  c = l_2[i]
  ans = str(c[0]).zfill(6) + str(l_1[c[0]].index(c[1])+1).zfill(6)
  print(ans)


### FIXED CODE ###

import bisect
N, M = map(int, input().split())
l_1 = [[] for i in range(N+1)]
l_2 = []
for i in range(M):
  p, y = map(int, input().split())
  l_1[p].append(y)
  l_2.append([p, y])
  
for i in range(N+1):
  l_1[i].sort()
    
for i in range(M):
  c = l_2[i]
  n = bisect.bisect_left(l_1[c[0]], c[1]) + 1
  ans = str(c[0]).zfill(6) + str(n).zfill(6)
  print(ans)
### BUGGY CODE ###

try:
    from math import gcd
except:
    from fractions import gcd
import operator
from collections import deque


class Segtree:
    """
    st = Segtree(4, f=operator.add, e=0)
    st[1:] = [4, 9, 16]
    st[0] = -99
    assert st[-1] == 16
    assert st[:] == [-99, 4, 9, 16]
    assert st.grasp(1, 3) == 13
    """

    def __init__(self, n, f=operator.add, e=0):
        """all(f(v, e) == f(e, v) == v for v in data)"""
        self.r = range(n)
        self.size = 2 ** ((n - 1).bit_length())
        self.tree = [e] * (2 * self.size)
        self.f = f
        self.iden = e

    def __len__(self):
        return len(self.r)

    def __list__(self):
        return self.tree[self.size-1:self.size-1+len(self.r)]

    def __repr__(self):
        return repr(list(self))

    def grasp(self, i=0, j=None):
        """reduce(f, data[i:j], e)"""
        if j is None:
            j = len(self)
        i = self.size - 1 + max(i, 0)
        j = self.size - 1 + min(j, len(self))
        ans = self.iden
        while j - i > 0:
            if i & 1 is 0:
                ans = self.f(self.tree[i], ans)
            if j & 1 is 0:
                ans = self.f(ans, self.tree[j-1])
            i = i >> 1
            j = (j - 1) >> 1
        return ans

    def __getitem__(self, i):
        r = self.r[i]
        if isinstance(r, int):
            return self.tree[self.size - 1 + r]
        else:
            return [self.tree[self.size - 1 + ri] for ri in r]

    def __setitem__(self, i, v):
        """Extra elements will be ignored when i is a slice."""
        r = self.r[i]
        if isinstance(r, int):
            r = [r]
            v = [v]
        q = deque()
        s = set()

        def addnext(j):
            k = (j - 1) // 2
            if k >= 0 and k not in s:
                q.append(k)
                s.add(k)

        for ri, vi in zip(r, v):
            j = self.size - 1 + ri
            self.tree[j] = vi
            addnext(j)
        while len(q):
            j = q.popleft()
            s.remove(j)
            vl = self.tree[2 * j + 1]
            vr = self.tree[2 * j + 2]
            self.tree[j] = self.f(vl, vr)
            addnext(j)


N = int(input())
A = [int(s) for s in input().split()]
st = Segtree(N, f=gcd, e=0)
st[:] = A
ans = max([gcd(st.grasp(0, i), st.grasp(i+1)) for i in range(N)])
print(ans)


### FIXED CODE ###

try:
    from math import gcd
except:
    from fractions import gcd
from itertools import accumulate

N = int(input())
A = [int(s) for s in input().split()]
s = [0] + list(accumulate(A, gcd))
t = list(reversed(list(accumulate(reversed(A), gcd)))) + [0]

ans = max([gcd(s[i-1], t[i]) for i in range(1, N+1)])
print(ans)
### BUGGY CODE ###

n, m = map(int, input().split())
for i in range(m//n,0,-1):
    if m % i == 0:
        break
print(i) 

### FIXED CODE ###

def solve():
    n,m = map(int,input().split())
    for i in range(m//n,0,-1):
        if m%i==0: break
    print(i)
solve()
### BUGGY CODE ###

S = list(input())
ans = 0
sub = []
num = 0
for i in range(len(S)):
  for j in range(i,len(S)):
    if i == j and S[i] == '0':
      ans += 1
    elif j-i >=  3:
      sub = S[i:j+1]
      num = ''.join(map(str,sub))
      if int(num) % 2019 == 0:
        ans += 1
print(ans)

### FIXED CODE ###

S = list(str(input()))
S.reverse()
mod = 2019
rem = [0]*mod
num = 0
rem[num] += 1
d = 1
ans = 0
for s in S:
  num += int(s) * d
  num %= mod
  d *= 10
  d %= mod
  rem[num] += 1
for r in rem:
  ans += r*(r-1)//2
print(ans)
### BUGGY CODE ###

from collections import deque

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

for i in range(n-1):
    a, b = map(int, input().split())
    neighbor[a-1].append(b-1)
    neighbor[b-1].append(a-1)

for i in range(q):
    pl.append(list(map(int, input().split())))

parent = [-1 for _ in range(n)]
child = [[] for _ in range(n)]
parent[0] = 0
point = [0] * n
que = deque([])


def makeTree():
    global parent, neighbor, child, que
    queue = deque([[0, 0]])
    while len(queue) > 0:
        now = queue.popleft()
        que.append(now[0])
        for neiv in neighbor[now[0]]:
            if parent[neiv] == -1:
                parent[neiv] = now[0]
                queue.append([neiv, now[1]])
                child[now[0]].append(neiv)


def calcPoint():
    global pl, parent, point, que
    for p in pl:
        point[p[0] - 1] += p[1]
    que.popleft()
    for v in que:
        point[v] += point[parent[v]]


makeTree()

calcPoint()

print(*point)


### FIXED CODE ###

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

n, q = map(int, input().split())
neighbor = [[] for _ in range(n)]
point = [0]*n

for i in range(n-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    neighbor[a].append(b)
    neighbor[b].append(a)

for i in range(q):
    p, x = map(int, input().split())
    point[p-1] += x


def dfs(now, past):
    for nv in neighbor[now]:
        if nv == past:
            continue
        point[nv] += point[now]
        dfs(nv, now)


dfs(0, -1)


print(*point)
### BUGGY CODE ###

N = int(input())
a = list(map(int, input().split()))
li = []
for i in range(N):
    li.append(a.count(i + 1))

for i in range(N):
    print(li[i])


### FIXED CODE ###

N = int(input())
a = list(map(int, input().split()))
li = [0] * N

for i in range(N-1):
    li[a[i]-1] = li[a[i]-1] + 1

for i in range(N):
    print(li[i])
### BUGGY CODE ###

N, M = map(int, input().split())
L = [0] * M
R = [0] * M
L, R = map(int, input().split())
ans = set(list(range(L, R+1)))
for i in range(M-1):
  L, R = map(int, input().split())
  ans = ans & set(list(range(L, R+1)))
print(len(ans))

### FIXED CODE ###

N,M = map(int,input().split())
L = []
R = []
for i in range(M):
    l,r = map(int,input().split())
    L.append(l)
    R.append(r)
ans = list(range(max(L),min(R)+1))
print(len(ans))
### BUGGY CODE ###

n = int( input() )
strs = []
for i in range( n ):
	strs.append( sorted( list( input() ) ) )

count = 0
strs = sorted( strs )
for i in range( n ) :
	bFound = False
	for j in range( i+1, n ) :
		if strs[i] == strs[j] :
			count += 1
			bFound = True
		elif bFound == True :
			break
		else:
			pass

print( count )

### FIXED CODE ###

from operator import mul
from functools import reduce

def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under

#=-------------------------------------  
n = int( input() )

dict = {}
for i in range( n ):
	sorted_input = "".join( sorted( list( input() ) ) )
	if dict.get( sorted_input ) == None:
		dict[ sorted_input ] = 1
	else :
		dict[ sorted_input ] += 1

count = 0
for eachValue in dict.values():
	if eachValue == 1 : continue
	count += cmb( eachValue, 2 )
print( count )
### BUGGY CODE ###

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

N, C = map(int, input().split())
T = 10**5+2

c_ls = [[0] * T for _ in range(C)]
# いもす
for i in range(N):
    s, t, c = map(int, input().split())
    c_ls[c-1][s] += 1
    c_ls[c-1][t] -= 1
# 各チャンネル毎の累積和
for i in range(C):
    for j in range(1, T):
        c_ls[i][j] += c_ls[i][j-1]
# 他チャンネルとの重複を見るために開始を1早める
for i in range(C):
    for j in range(1, T):
        if c_ls[i][j] > c_ls[i][j-1]:
            c_ls[i][j-1] += 1
# 全チャンネルを合計
sm = [0] * T
for i in range(C):
    for j in range(T):
        sm[j] += c_ls[i][j]
# 重複が一番多くなる箇所が答え
print(max(sm))


### FIXED CODE ###

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

N, C = map(int, input().split())
T = 10**5+2

c_ls = [[0] * T for _ in range(C)]
# いもす
for i in range(N):
    s, t, c = map(int, input().split())
    c_ls[c-1][s] += 1
    c_ls[c-1][t] -= 1
# 各チャンネル毎の累積和
for i in range(C):
    for j in range(1, T):
        c_ls[i][j] += c_ls[i][j-1]
# 他チャンネルとの重複を見るために開始を1早める
for i in range(C):
    for j in range(1, T):
        if c_ls[i][j] > c_ls[i][j-1]:
            c_ls[i][j-1] += 1
# 全チャンネルを合計
sm = [0] * T
for i in range(C):
    for j in range(T):
        sm[j] += c_ls[i][j]
# 重複が一番多くなる箇所が答え
print(max(sm))
### BUGGY CODE ###

import sys
input = sys.stdin.readline


def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    F = list(map(int, input().split()))

    A.sort()
    F.sort(reverse=True)

    r = A[-1]*F[0]

    l = -1

    while(r-l > 1):
        tmp = (l+r)//2
        k = 0
        for x, y in zip(A, F):
            k += max(0, x - (tmp // y))
        if k > K:
            l = tmp
        else:
            r = tmp
    print(r)


main()


### FIXED CODE ###

import sys
import bisect
import math
input = sys.stdin.readline
N, K = map(int, input().split())
A = list(map(int, input().split()))
F = list(map(int, input().split()))

A.sort()
F.sort(reverse=True)

B = [(A[i]*F[i], F[i]) for i in range(N)]
B.sort(reverse=True)
L = 0
R = B[0][0]
if sum(A) <= K:
    print(0)
    exit(0)
while(1):
    ans = (L+R) // 2
    flag = True
    tmp = 0
    for i in range(N):
        tmp += math.ceil(max(B[i][0] - ans, 0) / B[i][1])
        if tmp > K:
            flag = False
            break
    if flag:
        R = ans
    else:
        L = ans
    if L == R or L+1 == R:
        print(R)
        break
### BUGGY CODE ###

n=int(input())
t,a=[0]*n,[0]*n
for i in range(n):
  t[i],a[i]=map(int,input().split())
tt,aa=t[0],a[0]
for i in range(1,n):
  j=0
  while 1:
    j+=1
    if t[i]*j>=tt and a[i]*j>=aa:
      tt=t[i]*j
      aa=a[i]*j
      break
print(aa+tt)

### FIXED CODE ###

n=int(input())
t,a=[0]*n,[0]*n
for i in range(n):
  t[i],a[i]=map(int,input().split())
tt,aa=t[0],a[0]
for i in range(1,n):
  tt=t[i]*max((tt+t[i]-1)//t[i],(aa+a[i]-1)//a[i])
  aa=a[i]*max((tt+t[i]-1)//t[i],(aa+a[i]-1)//a[i])
print(aa+tt)
### BUGGY CODE ###

import itertools
N=int(input())
L=list(map(int,input().split()))
C=[x for x in itertools.combinations(L,3) if x[0]<x[1]+x[2] and x[1]<x[0]+x[2] and x[2]<x[0]+x[1]]
print(len(C))

### FIXED CODE ###

import bisect
N=int(input())
L=sorted(list(map(int,input().split())))
ans=0
for i in range(N-2):
  for j in range(N-i-2):        
    ans+=min(N-i-j-2,N-bisect.bisect_left(L,L[-j-1]-L[i]+1)-j-1)
print(ans)
### BUGGY CODE ###

#!usr/bim/python
#! -*- coding: utf-8 -*-

nk = raw_input()
nk = nk.split()
n,k = map(int,nk)

a = raw_input()
a = a.split()
a = map(int,a)

d = {}

for i in range(n):
    if a[i] in d:
        d[a[i]] += 1
    else:
        d[a[i]] = 1

l = d.values()

ans = 0

if len(l) <= k:
    pass
else:
    for i in range(len(l)-k):
        ans += min(l)
        l.remove(min(l))

print ans


### FIXED CODE ###

#!usr/bim/python
#! -*- coding: utf-8 -*-

nk = raw_input()
nk = nk.split()
n,k = map(int,nk)

a = raw_input()
a = a.split()
a = map(int,a)

d = {}

for i in range(n):
    if a[i] in d:
        d[a[i]] += 1
    else:
        d[a[i]] = 1

l = d.values()

ans = 0

if len(l) <= k:
    pass
else:
    l.sort()
    for i in range(len(l)-k):
        ans += l[i]

print ans