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

N,C = map(int,input().split())
D = [list(map(int,input().split())) for _ in range(C)]
c = [list(map(int,input().split())) for _ in range(N)]

cst = [[0,0,0] for i in range(C)]

for clr in range(1,C+1):
    for i in range(N):
        for j in range(N):
            cst[clr-1][(i+j+2)%3] += D[c[i][j]-1][clr-1]

ans = 10**10

for i in range(C):
    for j in range(C):
        for k in range(C):
            if i == j or i == k or j == k:
                continue
            ans = min(ans,cst[i][0]+cst[j][1]+cst[k][2])

print(ans)


### FIXED CODE ###

N,C = map(int,input().split())
D = [list(map(int,input().split())) for _ in range(C)]
c = [list(map(int,input().split())) for _ in range(N)]

cst = [[0,0,0] for i in range(C)]

for clr in range(1,C+1):
    for i in range(N):
        for j in range(N):
            cst[clr-1][(i+j+2)%3] += D[c[i][j]-1][clr-1]

ans = 10**10

for i in range(C):
    for j in range(C):
        for k in range(C):
            if i == j or i == k or j == k:
                continue
            ans = min(ans,cst[i][0]+cst[j][1]+cst[k][2])

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

import math

def main(X):
    end = False
    lst = f(X)
    # print(lst)
    for L in lst:
        if end:
            break
        else:
            for l in L:
                B = 1
                A = B + l[0]
                while g(A, B) > l[1]:
                    if g(A, B) < g(A + 1, B + 1):
                        break
                    B += 1
                    A = B + l[0]
                while g(A, B) <= l[1]:
                    if g(A, B) == l[1]:
                        print(A, B)
                        end = True
                        break
                    B += 1
                    A = B + l[0]
                # ***********************
                if end:
                    break
                else:
                    B = -1
                    A = B + l[0]
                    while g(A, B) > l[1]:
                        if g(A, B) < g(A - 1, B - 1):
                            break
                        B -= 1
                        A = B + l[0]
                    while g(A, B) <= l[1]:
                        if g(A, B) == l[1]:
                            print(A, B)
                            end = True
                            break
                        B -= 1
                        A = B + l[0]
                if end:
                    break


def f(X):
    return [[[X // i, i], [i, X // i]] for i in range(1, math.floor(X ** 0.5) + 1) if X % i == 0]

def g(A, B):
    return (A ** 4) + (A ** 3) * B + (A ** 2) * (B ** 2) + A * (B ** 3) + (B ** 4)



if __name__ == '__main__':
    X = int(input())
    main(X)


### FIXED CODE ###

import math

def main(X):
    lst = f(X)
    for L in lst:
        for l in L:
            for B in range(-120, 120, 1):
                A = B + l[0]
                if g(A, B):
                    print(A, B)
                    exit()

def f(X):
    return [[[X // i, i], [i, X // i]] for i in range(1, math.floor(X ** 0.5) + 1) if X % i == 0]

def g(A, B):
    return A ** 5 - B ** 5 == X



if __name__ == '__main__':
    X = int(input())
    main(X)
### BUGGY CODE ###

# coding: UTF-8
n = int(raw_input())
value_list = []
diff_indx1 = 0
diff_indx2 = 0
for i in range(n):
    value_list.append(int(raw_input()))
    if i == 1:
        diff = value_list[1] - value_list[0]
        diff_indx1 = 1
    if value_list[i] >= value_list[diff_indx1]:
        for j in range(i):
            diff2 = value_list[i] - value_list[j]
            if diff <= diff2:
                diff = diff2
                diff_indx1 = i
                diff_indx2 = j
                #print("{}:{} - {} = {}").format(diff_indx1,value_list[i],value_list[j],diff)
    elif value_list[diff_indx2] > value_list[i]:
        diff_indx2 = i
        diff_indx1 = i
print diff


### FIXED CODE ###

from sys import stdin

N,*datas = [int(i) for i in stdin.readlines()]
now_max = max(datas[1:])
max_index = datas.index(now_max)
diff = now_max - datas[0]

for i in range(1,N-1):
    if i == max_index:
        now_max = max(datas[i+1:])
        max_index = datas.index(now_max,i+1)
    new_diff = now_max - datas[i]
    if diff < new_diff:
        diff = new_diff

print(diff)
### BUGGY CODE ###

import numpy as np

S = [v for v in input()]
N = len(S)
M = np.array([[0] * N for i in range(N)])
for i in range(N):
    if S[i] == 'L':
        M[i - 1][i] = 1
    else:
        M[i + 1][i] = 1

L = np.linalg.matrix_power(M, 10 ** 100)
a = np.dot(L, [1 for i in range(N)])

print(' '.join(map(str, a)))

### FIXED CODE ###

S = [v for v in input()]
N = len(S)
M = [0] * N
for i in range(N):
    if S[i] == 'L':
        M[i] = i - 1
    else:
        M[i] = i + 1

binary = format(10 ** 100, 'b')
Bin = []
for v in binary:
    a = int(v)
    Bin.append(a)

ans = [1] * N
while Bin:
    a = Bin.pop()
    if a == 0:
        L = [0] * N
        for j in range(N):
            L[j] = M[M[j]]
        M = L
    else:
        new_ans = [0] * N
        for j in range(N):
            new_ans[M[j]] += ans[j]
        ans = new_ans

        L = [0] * N
        for j in range(N):
            L[j] = M[M[j]]
        M = L

print(' '.join(map(str, ans)))
### BUGGY CODE ###

n = int(input())

def sieve1(n):
    isPrime = [True] * (n+1)
    isPrime[0] = False
    isPrime[1] = False
    for i in range(2*2, n+1, 2):
        isPrime[i] = False
    for i in range(3, n+1):
        if isPrime[i]:
            for j in range(i+i, n+1, i):
                isPrime[j] = False
    return isPrime
numOfDivisors = [2] * (n+1)
numOfDivisors[1] = 1
numOfDivisors[0] = 0
isPrime = sieve1(n)
for i in range(2, n+1):
    if isPrime[i]:
        for j in range(2*i, n+1, i):
            x = j // i
            numOfDivisors[j] += numOfDivisors[x] - 1
ans = 0
for k in range(1, n+1):
    ans += numOfDivisors[k] * k
print (ans)

### FIXED CODE ###

n = int(input())

def sieve1(n):
    isPrime = [True] * (n+1)
    isPrime[0] = False
    isPrime[1] = False
    for i in range(2*2, n+1, 2):
        isPrime[i] = False
    for i in range(3, n+1):
        if isPrime[i]:
            for j in range(i+i, n+1, i):
                isPrime[j] = False
    return isPrime
numOfDivisors = [2] * (n+1)
numOfDivisors[1] = 1
numOfDivisors[0] = 0
isPrime = sieve1(n)
for i in range(2, n+1):
    if isPrime[i]:
        for j in range(2*i, n+1, i):
            x = j // i
            numOfDivisors[j] += numOfDivisors[x] - 1
ans = 0
for k in range(1, n+1):
    ans += numOfDivisors[k] * k
print (ans)
### BUGGY CODE ###

def dijkstra(s, n,  cost):
    d = [float("inf")] * n
    used = [False] * n
    d[s] = 0

    while True:
        v = -1
        for i in range(n):
            if (not used[i]) and (v == -1):
                v = i
            elif (not used[i]) and d[i] < d[v]:
                v = i
        if v == -1:
            break
        used[v] = True

        for j in range(n):
            d[j] = min(d[j], d[v] + cost[v][j])
    return d

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

cnt = [0 for i in range(n)]
cost = [[float(10 ** 10) for i in range(n)] for i in range(n)]

for i in range(n-1):
    x, y = map(int, input().split())
    cost[x-1][y-1] = 1
    cost[y-1][x-1] = 1
    cnt[x-1] += 1
    cnt[y-1] += 1

ans = 0
a = dijkstra(u-1,n,cost)
b = dijkstra(v-1,n,cost)
for i in range(n):
    if a[i] <= b[i]:
        if cnt[i] == 1:
            if b[i]-a[i]-1 > 0:
                ans = max(ans,b[i]-1)
        else:
            ans = max(ans,b[i])
print(ans)

### FIXED CODE ###

n,u,v = map(int,input().split())
lis = [list(map(int,input().split())) for i in range(n-1)]

graph = [[] for _ in range(n+1)]

for a,b in lis:
    graph[a].append(b)
    graph[b].append(a)

def dfs(v):
    dist = [-1] * (n+1)
    stack = [v]
    dist[v] = 0
    while stack:
        v = stack.pop()
        dw = dist[v] + 1
        for w in graph[v]:
            if dist[w] >= 0:
                continue
            dist[w] = dw
            stack.append(w)
    return dist

takahashi = dfs(u)
aoki = dfs(v)

ans = 0

for i in range(1,n+1):
    if takahashi[i] < aoki[i]:
        ans = max(ans,aoki[i]-1)

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

#!/usr/bin/env python3
(h, n), *m = [[*map(int, i.split())] for i in open(0)]
dp = [0] + [10**9] * h
for i in range(1, h + 1):
    dp[i] = min(dp[max(i - a, 0)] + b for a, b in m)
print(dp[-1])


### FIXED CODE ###

(h, n), *m = [[*map(int, i.split())] for i in open(0)]
dp = [0] + [10**9] * h
for i in range(1, h + 1):
    for a, b in m:
        dp[i] = min(dp[i], dp[max(i-a,0)]+b)
print(dp[-1])
### BUGGY CODE ###

import math
import numpy as np


def main():
    s = input().split(" ")
    N = int(s[0])
    K = int(s[1])
    A = [int(a) for a in input().split(" ")]
    F = [int(a) for a in input().split(" ")]
    A.sort()
    F.sort()
    F.reverse()
    AF = [A[i] * F[i] for i in range(N)]
    idx = np.argsort(AF)[::-1]

    A = [A[idx[i]] for i in range(N)]
    F = [F[idx[i]] for i in range(N)]
    AF = [AF[idx[i]] for i in range(N)]
    m = np.max(AF)

    for i in range(m - 1, 0, -1):
        count = 0
        for n in range(N):
            if(AF[n] <= i):
                continue
            count += math.ceil((AF[n] - i) / F[n])
            if(count > K):
                print(i + 1)
                return
    print(0)


if(__name__ == "__main__"):
    main()


### FIXED CODE ###

import math
import numpy as np


def main():
    s = input().split(" ")
    N = int(s[0])
    K = int(s[1])
    A = np.array([int(a) for a in input().split(" ")])
    F = np.array([int(a) for a in input().split(" ")])
    A = np.sort(A)
    F = np.sort(F)[::-1]
    AF = A * F
    m = np.max(AF)

    if(func(0, AF, F, N, K)):
        print(0)
        return
    a = 0
    b = m
    for aaa in range(m):
        if((b - a) <= 1):
            print(b)
            return
        mid = int((b - a) / 2.) + a
        if(func(mid, AF, F, N, K)):
            b = mid
        else:
            a = mid
    print("???????")


def func(saidai, AF, F, N, K):
    count = np.sum(np.ceil((AF[(AF - saidai) > 0] - saidai) / F[(AF - saidai) > 0]))
    return count <= K


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

import math
#N = int(input())
N, M =  map(int,input().split())
#W =list(map(int,input().split()))
a = [(int(input())) for i in range(M)]


def comb(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

def stair_count(start,end):
    #print(start,end)
    aida = end - start
    total = 1
    i = aida-1
    #print("aida/2={}".format(aida/2))
    kazu = 1
    while (aida%2==0 and i >= (aida/2)) or (aida%2!=0 and i>(aida/2)):
        total += comb(i,kazu)
        kazu += 1
        i -= 1
    return total

start = 0
answer = 1
for i in a:
    #print("i={}".format(i))
        if i == start:
            print(0)
            exit()
        else:
            answer = (answer * stair_count(start, i-1))
            start = i+1
answer = (answer * stair_count(start, N))
    #print("answer={}".format(answer))
print(answer%1000000007)


### FIXED CODE ###

#N = int(input())
N, M =  map(int,input().split())
#W =list(map(int,input().split()))
a = [(int(input())) for i in range(M)]

import sys

sys.setrecursionlimit(100000)
memo  =[-1]*(N+2)
def stair_count(n):
    if memo[n]!= -1:
        return memo[n]
    if n==0 or n==1:
        memo[n] =1
        return memo[n]
    memo[n] = stair_count(n-1) + stair_count(n-2)
    return memo[n]

start = 0
answer = 1
for i in a:
        if i == start:
            print(0)
            exit()
        else:
            n = i-1-start
            answer = (answer * stair_count(n))
            start = i+1
n = N -start
answer = (answer * stair_count(n))
print(answer%1000000007)
### BUGGY CODE ###

num = list(map(int,input().split()))
per = []

for i in range(num[0],num[1]+1):
    for j in range(num[0],num[1]+1):
        if i != j:
            per.append((i*j)%2019)
per.sort()

print(per[0])
        

### FIXED CODE ###

import itertools
import sys

num = list(map(int,input().split()))
per = []

for i in range(num[0],num[1]+1):
    for j in range(num[0],num[1]+1):
        if i <= j:
            break
        else:
            per.append((i*j)%2019)
            if (i*j)%2019 == 0:
                print(0)
                sys.exit()
per.sort()

print(per[0])
### BUGGY CODE ###

n = int(input())

nums = list(map(int, input().split()))
temp = nums.copy()
for i in range(n):
    nums.pop(i)
    t = {}
    for j in nums:
        t[j] = nums.count(j)
    result = 0
    for v in t.values():
        if (v > 1):
            result += int(v*(v-1)/2)
    print(result)
    nums = temp.copy()

### FIXED CODE ###

import collections

n = int(input())

nums = list(map(int, input().split()))

cnt = collections.Counter(nums)

def c2(n):
    return int(n * (n-1) / 2)

total = 0

for c in cnt.values():
    total += c2(c)

for i in range(n):
    d = cnt[nums[i]]
    diff = c2(d) - c2(d-1)
    print(total - diff)
### BUGGY CODE ###

n, m = map(int, input().split())
broken_list = [int(input()) for _ in range(m)]
enable_list = [i for i in range(2, n+1) if not i in broken_list]
a = [0] * (n+1)
a[0] = 1
a[1] = 0 if 1 in broken_list else 1

if n == 1:
  print(1)
  exit()
if n == 2:
  if broken_list:
    print(1)
  else:
    print(2)
  exit()
  
for i in enable_list:
  a[i] = a[i-1] + a[i-2]
  a[i] %= 1000000007

print(a[n])

### FIXED CODE ###

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

a = 1
b = 1

i = 2

for j in range(m):
  ind = int(input())
  if ind == 1:
    b = 0
    continue
  while i < ind:
    a, b = b, a+b
    i += 1
  else:
    a, b = b, 0
    i += 1
    
while i < n+1:
  a, b = b, a+b
  i += 1
  
  
print(b%1000000007)
### BUGGY CODE ###

import math
import fractions
from functools import reduce


def calc_lcm(x, y):
    return (x * y) // fractions.gcd(x, y)


def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)


def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)


if __name__ == '__main__':
    n, m = list(map(int, input().split()))
    a = list(map(lambda x: int(x) // 2, input().split()))
    a = list(set(a))

    while True:
        odd_flag = 0
        even_flag = 0
        for i in range(len(a)):
            if a[i] % 2 == 0:
                a[i] = a[i] / 2
                even_flag = 1
                if odd_flag == 1:
                    print(0)
                    exit()
            else:
                odd_flag = 1
                if even_flag == 1:
                    print(0)
                    exit()

        if even_flag == 0:
            break
        elif odd_flag == 0:
            m = m // 2

    lcm = lcm_list(a)

    # lcm = a[0]
    # for i in a:
    #     lcm = calc_lcm(lcm, i)

    print(math.ceil((m // lcm) / 2))

### FIXED CODE ###

from fractions import gcd
from functools import reduce
import sys
sys.setrecursionlimit(10 ** 7)

def lcm_base(x, y):
    return (x * y) // gcd(x, y)

def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)


if __name__ == '__main__':
    n, m = list(map(int, input().split(" ")))
    a = list(map(int, input().split(" ")))
    a = list(set(a))

    # for j in a:
    #     if j % 2 != 0:
    #         print("0")

    # a = [i/2 for i in a]
    l = lcm_list(a)

    # if l == 0:
    #     print(0)
    #     exit()

    if (2 * m) < l:
        print("0")
        exit()

    i = l / 2

    for j in a:
        if i // (j // 2) % 2 == 0:
            print(0)
            exit()

    # if m < i:
    #     print("0")
    else:
        # print("1")
        print(int(((m - i) // l) + 1))
        # print(int((m // i + 1) // 2))
### BUGGY CODE ###

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

def dfs(stack, B):
    if len(B)==1:
        if B[0]==1:
            stack.append(1)
            return stack
        else: return None
    else:
        tmp = []
        flag = False
        for i, b in enumerate(B):
            stack_ = stack + [b]
            B_ = B[:i] + B[i+1:]
            if b==i+1: tmp.append(dfs(stack_, B_))
        for tp in tmp:
            if tp is not None:
                flag = True
                ans = tp
        if flag:
            return ans
        else:
            return None
ans = dfs([], B)
if ans is None:
    print('-1')
else:
    ans = ans[::-1]
    for i in range(N):
        print(ans[i])

### FIXED CODE ###

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

stack = []
for i in range(N):
    tmp = []
    flag = True
    for j in range(len(B)):
        if B[j]==j+1:
            tmp.append(j)
    if tmp:
        tmp.sort(reverse=True)
        ans = tmp[0]
        B = B[:ans] + B[ans+1:]
        stack.append(ans+1)
    else:
        flag = False
        break
if flag:
    stack = stack[::-1]
    for i in stack:
        print(i)
else:
    print(-1)
### BUGGY CODE ###

a,b,n=map(int,input().split())
ans=0
x=0
while(x<=n or -(-x//a)<=n):
    ans=max(ans,((a*x)//b - a*(x//b)))
    y=-(-x//a)
    ans=max(ans,((a*y)//b - a*(y//b)))
    x+=b
print(ans)


### FIXED CODE ###

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

def f(x):
    return (a*x)//b - a*(x//b)

print(f(min(b-1,n)))
### BUGGY CODE ###

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

i=1
j=0
k=0
ta=0
rb=0
tc=0
cnt=0
m=0

aa=[]
bb=[]
c=[]
for i in range(len(l)*(len(l)-1)):
    # if i%(n)!=0:
    j = int(i/n)
    k = n*(j)+i%n-n*j
    # aa.append(j)
    # bb.append(k)
    # c.append(i)
    if j < k:
        for m in range(k+1,len(l)):
            if l[m] < l[j]+l[k] and l[j]<l[m]+l[k] and l[k]<l[m]+l[j]:
                cnt+=1
print(cnt)
# print(aa)
# print(bb)
# print(c)
#
#

# for i in range(0,len(l)-2):
#
#     for j in range(i+1,len(l)-1):
#
#         for k in range(j+1,len(l)):
#             if l[i] < l[j]+l[k] and l[j]<l[i]+l[k] and l[k]<l[i]+l[j]:
#                 cnt+=1
# print(cnt)


### FIXED CODE ###

import bisect
n=int(input())
l=list(map(int, input().split()))

i=1
j=0
k=0
ta=0
rb=0
tc=0
cnt=0
m=0
ls=sorted(l)



for i in range(0,len(ls)-2):

    for j in range(i+1,len(ls)-1):
        l1 = ls[i]
        l2 = ls[j]
        ll= l1+l2
        # mid = 0
        k = bisect.bisect_left(ls,ll) - 1

        cnt+=k-j
print(cnt)
### BUGGY CODE ###

from functools import reduce
n=int(input())
l1=list(map(int,input().split()))
a = reduce((lambda x, y: x * y), l1) 
if a>10**18:
  print("-1")
else:
  print(a)

### FIXED CODE ###


n=int(input())
l1=list(map(int,input().split()))
p=1
k=0
if 0 in l1:
  print("0")
  exit()
for i in range(n):
  p*=l1[i]
  if p>10**18:
    k=1
    break
if k==1:
  print("-1")
else:
  print(p)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

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

from collections import Counter

C=Counter(A)

LIST=sorted(C.values())
LEN=len(LIST)
SUM=sum(LIST)

for k in range(1,N+1):
    if k>LEN:
        print(0)
    else:
        BASE=LIST[-k:]
        #print(BASE)

        REST=SUM-sum(BASE)
        REST0=REST

        MIN=min(BASE)
        MAX=max(BASE)

        if MAX*k-sum(BASE)<=REST:
            print(SUM//k)
            continue

        while MIN!=MAX:
            mid=(MIN+MAX+1)//2
            REST=REST0

            for b in BASE:
                if b<mid:
                    REST-=mid-b

            #print(MAX,MIN,mid,REST)

            if REST>=0:
                MIN=mid
            else:
                MAX=mid-1

        print(MIN)


### FIXED CODE ###

import sys
input = sys.stdin.readline

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

from collections import Counter
from itertools import accumulate
import bisect

C=Counter(A)

LIST=sorted(C.values())
LEN=len(LIST)
SUM=[0]+list(accumulate(LIST))
MIN=0
MAX=SUM[-1]

for k in range(1,N+1):
    MIN=0
    while MIN!=MAX:
        mid=(MIN+MAX+1)//2
        x=bisect.bisect_right(LIST,mid)

        if SUM[x]+(LEN-x)*mid>=mid*k:
            MIN=mid
        else:
            MAX=mid-1

    print(MIN)
### BUGGY CODE ###

h, w = map(int, input().split())

g = [list("#" * (w + 2))]
for _ in range(h):
    g.append(["#"] + list(input()) + ["#"])
g += [list("#" * (w + 2))]

DX = [0, 1, 0, -1]
DY = [1, 0, -1, 0]

#print(*g, sep="\n")


def cnt_dot(k, l):
    if g[k][l] == ".":
        cnt = 1
        for dx, dy in zip(DX, DY):
            x, y = k + dx, l + dy
            while g[x][y] == ".":
                cnt += 1
                x, y = x + dx, y + dy
        return cnt
    else:
        return 0


res = 0
for i in range(h + 2):
    for j in range(w + 2):
        res = max(res, cnt_dot(i, j))
print(res)



### FIXED CODE ###

def main():
    h, w = map(int, input().split())

    g = [list("#" * (w + 2))]
    for _ in range(h):
        g.append(["#"] + list(input()) + ["#"])
    g += [list("#" * (w + 2))]
    area = [[0] * (w + 2) for _ in range(h + 2)]

    for i in range(h + 2):
        cnt = 0
        for j in range(w + 2):
            if g[i][j] == "#":
                for k in range(j - cnt, j):
                    area[i][k] += cnt
                cnt = 0
            else:
                cnt += 1

    for i in range(w + 2):
        cnt = 0
        for j in range(h + 2):
            if g[j][i] == "#":
                for k in range(j - cnt, j):
                    area[k][i] += cnt
                cnt = 0
            else:
                cnt += 1

    res = 0
    for i in range(h + 2):
        for j in range(w + 2):
            res = max(res, area[i][j])
    print(res - 1)
if __name__ == '__main__':
    main()
### BUGGY CODE ###

#Z[i]:length of the longest list starting from S[i] which is also a prefix of S
#O(|S|)
def Z_algorithm(s):
    N = len(s)
    Z_alg = [0]*N

    Z_alg[0] = N
    i = 1
    j = 0
    while i < N:
        while i+j < N and s[j] == s[i+j]:
            j += 1
        Z_alg[i] = j
        if j == 0:
            i += 1
            continue
        k = 1
        while i+k < N and k + Z_alg[k]<j:
            Z_alg[i+k] = Z_alg[k]
            k += 1
        i += k
        j -= k
    return Z_alg

N=int(input())
S=input()
S=[S[i] for i in range(0,N)]

def condition(num):
    if num==0:
        return True
    for i in range(0,N-2*num+1):
        s=S[i:]
        data=Z_algorithm(s)
        for j in range(num,len(data)):
            if data[j]>=num:
                return True

    return False

start=0
end=N
while end-start>1:
    test=(end+start)//2
    if condition(test):
        start=test
    else:
        end=test

if condition(end):
    print(end)
else:
    print(start)


### FIXED CODE ###

from itertools import groupby

N=int(input())
S=input()
def condition(num):
    if num==0:
        return True
    else:
        flag=0
        data=[]
        for i in range(0,N-num+1):
            data.append([S[i:i+num],i])
        data.sort()
        partdata=[data[i][0] for i in range(0,len(data))]
        partdata=groupby(partdata)
        subdata=[]
        for key,group in partdata:
            g=len(list(group))
            subdata.append(g)
        s=0
        t=subdata[0]-1
        if len(subdata)==1:
            if data[t][1]-data[s][1]>=num:
                flag=1
        for i in range(0,len(subdata)-1):
            if data[t][1]-data[s][1]>=num:
                flag=1
            s=t+1
            t=t+subdata[i+1]
        if data[t][1]-data[s][1]>=num:
            flag=1
        return flag==1

start=0
end=N
while end-start>1:
    test=(end+start)//2
    if condition(test):
        start=test
    else:
        end=test
if condition(end):
    print(end)
else:
    print(start)
### BUGGY CODE ###

import math
gcd = 0
N = int(input())
for a in range(1, N + 1):
  for b in range(1, N + 1):
    for c in range(1, N + 1):
      arr1 = math.gcd(a, b) 
      arr2 = math.gcd(c, b)
      gcd += math.gcd(arr1, arr2)
print(gcd)



### FIXED CODE ###

import math
gcd1 = 0
gcd3 = 0
gcd6 = 0
N = int(input())
for a in range(1, N + 1):
  for b in range(1, N + 1):
    for c in range(1, N + 1):
      if a < b < c:
        gcd6 += math.gcd(a,math.gcd(b, c))
      elif a == b < c or a < b == c:
        gcd3 += math.gcd(a,math.gcd(b, c))
      elif a == b == c:
        gcd1 += math.gcd(a,math.gcd(b, c))
print(6 * gcd6 + 3 * gcd3 + gcd1)