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

import sys
n,k = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
l = sys.maxsize * (-1)
r = sys.maxsize

while l+1 < r:
  x = (l+r)//2
  def isOk():
    tot = 0
    for i in range(n):
      if a[i] < 0:
        l = -1
        r = n
        while (l+1<r):
          c = (l+r)//2;
          if (a[c] * a[i] < x):
            r = c
          else:
            l = c
        tot += n-r
      else:
        l = -1
        r = n
        while (l+1<r):
          c = (l+r)//2
          if (a[c] * a[i] < x):
            l = c
          else:
            r = c
        tot += r
      if (a[i]*a[i] < x):
        tot -= 1
    tot /= 2
    return tot < k
  if (isOk()):
    l = x
  else:
    r = x;
print(l)

### FIXED CODE ###

import sys
n,k = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
l = sys.maxsize * (-1)
r = sys.maxsize

while l+1 < r:
  x = (l+r)//2
  def isOk():
    tot = 0
    for i in range(n):
      if a[i] < 0:
        l = -1
        r = n
        while (l+1<r):
          c = (l+r)//2;
          if (a[c] * a[i] < x):
            r = c
          else:
            l = c
        tot += n-r
      else:
        l = -1
        r = n
        while (l+1<r):
          c = (l+r)//2
          if (a[c] * a[i] < x):
            l = c
          else:
            r = c
        tot += r
      if (a[i]*a[i] < x):
        tot -= 1
    tot /= 2
    return tot < k
  if (isOk()):
    l = x
  else:
    r = x;
print(l)
### BUGGY CODE ###

def main():
  n=int(input())
  l=list(map(int,input().split()))
  l.sort()
  import bisect
  ans=0
  for i in range(n-2):
    for j in range(i+1,n-1):
      a=l[i]
      b=l[j]
      idxl=bisect.bisect_right(l[j+1:],abs(a-b))
      idxr=bisect.bisect_left(l[j+1:],abs(a+b))
      ans+=idxr-idxl
  print(ans)
if __name__=='__main__':
  main()


### FIXED CODE ###

n=int(input())
l=sorted(list(map(int,input().split())))
import bisect
ans=0
for i in range(n):
  for j in range(i):
    index=bisect.bisect_right(l,l[i]-l[j])#このindexよりも右側のものでかつjより左のものが当てはまるもの
    ans += max(j - index,0)
print(ans)
### BUGGY CODE ###

s=input()
q=int(input())
for i in range(q):
  lis=list(map(str,input().split()))
  if lis[0]=="1":
    s=s[::-1]
  elif lis[1]=="1":
    s=lis[2]+s
  else:
    s+=lis[2]

print(s)

### FIXED CODE ###

s=input()
q=int(input())
keep=1
mae=""
ato=""
for i in range(q):
  lis=list(map(str,input().split()))
  if lis[0]=="1":
    keep*=-1
  elif lis[1]=="1":
    if keep==1:
      mae=lis[2]+mae
    else:
      ato+=lis[2]
  else:
    if keep==1:
      ato+=lis[2]
    else:
      mae=lis[2]+mae

if keep==1:
  print(mae+s+ato)
else:
  print(ato[::-1]+s[::-1]+mae[::-1])
### BUGGY CODE ###

import numpy as np
import sys
input = sys.stdin.readline

N, K = map(int, input().strip().split(" "))
A = np.zeros(N + 1, dtype=np.int32)
A[1:] = np.array(list(map(int, input().strip().split(" "))), dtype=np.int32)
A = np.cumsum(A) - np.array(range(N + 1), dtype=np.int32)

rem_count = {}
rem_count[0] = 1
ans = 0
for i in range(1, N + 1):
    if i - K >= 0:
        rem_count[A[i - K] % K] -= 1
    if A[i] % K in rem_count:
        ans += rem_count[A[i] % K]
        rem_count[A[i] % K] += 1
    else:
        rem_count[A[i] % K] = 1

print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline

N, K = map(int, input().strip().split(" "))
A = list(map(int, input().strip().split(" ")))
A = [0] + A
for i in range(1, N + 1):
    A[i] += A[i - 1]
    A[i - 1] -= i - 1
A[N] -= N

rem_count = {}
rem_count[0] = 1
ans = 0
for i in range(1, N + 1):
    if i - K >= 0:
        rem_count[A[i - K] % K] -= 1
    if A[i] % K in rem_count:
        ans += rem_count[A[i] % K]
        rem_count[A[i] % K] += 1
    else:
        rem_count[A[i] % K] = 1

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

from collections import defaultdict
n,p=map(int,input().split())
S=input()
ans=0
if p==5:
    for i in range(n):
        if int(S[i])==5 or int(S[i])==0:
            ans+=i+1
elif p==2:
    for i in range(n):
        if int(S[i])%2==0:
            ans+=i+1
else:
    kouho=defaultdict(int)
    s=0
    for i in range(n):
        s+=int(S[-(i+1)])*(10**i)
        a=s%p
        kouho[a]+=1
    for j in range(p):
        z=kouho[j]
        ans+=z*(z-1)//2
    ans+=kouho[0]
print(ans)

### FIXED CODE ###

from collections import defaultdict
n,p=map(int,input().split())
S=input()
ans=0
if p==5:
    for i in range(n):
        if int(S[i])==5 or int(S[i])==0:
            ans+=i+1
elif p==2:
    for i in range(n):
        if int(S[i])%2==0:
            ans+=i+1
else:
    kouho=defaultdict(int)
    s=0
    ruijo=1
    for i in range(n):
        ruijo%=p
        s+=int(S[-(i+1)])*(ruijo)
        a=s%p
        kouho[a]+=1
        ruijo*=10
    for j in range(p):
        z=kouho[j]
        ans+=z*(z-1)//2
    ans+=kouho[0]
print(ans)
### BUGGY CODE ###

import numpy as np
h,w = map(int,input().split())
ans = [[0]*(w+2) for _ in range(h+2)]
grid = []
grid.append(['#']*(w+2))
for _ in range(h):
    s = list(input())
    grid.append(['#'] + s + ['#'])
grid.append(['#']*(w+2))
for i in range(1,h+1):
    for j in range(0,w+2):
        if grid[i][j] == '#':
            if j >= 1:
                for k in range(j-start):
                    ans[i][start+k] += j-start
            start = j + 1
for j in range(1,w+1):
    for i in range(0,h+2):
        if grid[i][j] == '#':
            if i >= 1:
                for k in range(i-start):
                    ans[start+k][j] += i-start
            start = i + 1
print(np.amax(ans)-1)


### FIXED CODE ###

h,w = map(int,input().split())
ans = [[0]*(w+2) for _ in range(h+2)]
grid = []
grid.append(['#']*(w+2))
for _ in range(h):
    s = list(input())
    grid.append(['#'] + s + ['#'])
grid.append(['#']*(w+2))
for i in range(1,h+1):
    for j in range(0,w+2):
        if grid[i][j] == '#':
            if j >= 1:
                for k in range(j-start):
                    ans[i][start+k] += j-start
            start = j + 1
for j in range(1,w+1):
    for i in range(0,h+2):
        if grid[i][j] == '#':
            if i >= 1:
                for k in range(i-start):
                    ans[start+k][j] += i-start
            start = i + 1
print(max(list(map(lambda x:max(x),ans)))-1)
### BUGGY CODE ###

a,b,x = map(int, input().split())
count = 0
for i in range(a,b+1):
    if i % x == 0:
        count = count + 1

print(count)

### FIXED CODE ###

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

ans = b//x - (a-1)//x

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

A = list(input())
n = len(A)

count = 0
for _ in range(n):
    a = 0
    for i in reversed(range(1, n)):
        if  A[i-1] == 'B' and A[i] == 'W':
            A[i] = 'B'
            A[i-1] = 'W'
            count += 1
            a += 1
    
    if a == 0: break

print(count)


### FIXED CODE ###

A = list(input())

count = 0
ans = 0
for a in A:
    if a == 'B':
        count += 1
    else:
        ans += count

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

# coding: utf-8
# Your code here!
from functools import cmp_to_key
s = input()
K = int(input())

e = set([])

def cmp(a, b):
    if a == b: return 0
    return -1 if a < b else 1
    
def substring_sort(a,b):
    if len(a) != len(b):
        return cmp(len(a), len(b))
    else:
        return cmp(a,b)

for i in range(1,len(s)+1):
    for j in range(len(s)):
    #     if len(e) < 5:
    #         e.add(s[j:j+i])
    #     if len(e) == 5:
    #         break
    # else:
    #     continue
    # break
        e.add(s[j:j+i])
# print(e)
# result = sorted(e,key=cmp_to_key(substring_sort),reverse=True)
result = sorted(e)
# print(result)
print(result[K-1])


### FIXED CODE ###

# coding: utf-8
# Your code here!

from functools import cmp_to_key
s = input()
K = int(input())
 
e = set([])
 
def cmp(a, b):
    if a == b: return 0
    return -1 if a < b else 1
    
def substring_sort(a,b):
    if len(a) != len(b):
        return cmp(len(a), len(b))
    else:
        return cmp(a,b)
 
for i in range(1,K+1):
    for j in range(len(s)):
    #     if len(e) < 5:
    #         e.add(s[j:j+i])
    #     if len(e) == 5:
    #         break
    # else:
    #     continue
    # break
        e.add(s[j:j+i])
# print(e)
# result = sorted(e,key=cmp_to_key(substring_sort),reverse=True)
result = sorted(e)
# print(result)
print(result[K-1])
### BUGGY CODE ###

n = int(input())
a_lst = []
b_lst = []
sum_lst = []

for i in range(0, n):
    a, b = [int(elem) for elem in input().split()]
    a_lst.append(a)
    b_lst.append(b)

tmp = zip(b_lst, a_lst)
tmp = sorted(tmp)
b_lst, a_lst = zip(*tmp)   

for i in range(0, len(a_lst)):
    sum_lst.append(sum(a_lst[:i+1]))

flag = 0
for a, b in zip(sum_lst, b_lst):
    if a > b:
        flag = 1

if flag == 0:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

n = int(input())
a_lst = []
b_lst = []

for i in range(0, n):
    a, b = [int(elem) for elem in input().split()]
    a_lst.append(a)
    b_lst.append(b)

tmp = zip(b_lst, a_lst)
tmp = sorted(tmp)
b_lst, a_lst = zip(*tmp)   

flag = 0
sums = 0
for i in range(0, len(a_lst)):
    sums += a_lst[i]
    if sums > b_lst[i]:
        flag = 1
        break

if flag == 0:
    print("Yes")
else:
    print("No")
### BUGGY CODE ###

x,y,z=map(int,input().split())
l=[z]
per=0
while sum(l)<=x:
    l.append(y)
    l.append(z)
    #print(l)
    #print(sum(l))
    if sum(l)<=x:
        per+=1
print(per)

### FIXED CODE ###

x,y,z=map(int,input().split())
l=[z]
per=0

per=(x-z)//(y+z)

print(per)
### BUGGY CODE ###

from collections import deque 
N = int(input())
S = input()
s = deque(list(S))
count = 0
def findb(ind,checker):
    global count
    b = S[ind:].count("B")
    if b > 0:
        if ind + checker < N:
            if S[ind+checker] == "B":
                b -= 1
        count += b
def findg(ind,checker):
    global count
    g = S[ind:].count("G")
    if g > 0:
        if ind + checker < N:
            if S[ind+checker] == "G":
                g -= 1
        count += g
def findr(ind,checker):
    global count
    r = S[ind:].count("R")
    if r > 0:
        if ind + checker < N:
            if S[ind+checker] == "R":
                r -= 1
        count += r
for i in range(N-2):
    temp = s.popleft()
    st = S[i:]
    if temp == "R":
        for j in [x for x, y in enumerate(st) if y == 'G']:
            findb(i+j,j)
        for j in [x for x, y in enumerate(st) if y == 'B']:
            findg(i+j,j)
    elif temp == "G":
        for j in [x for x, y in enumerate(st) if y == 'B']:
            findr(i+j,j)
        for j in [x for x, y in enumerate(st) if y == 'R']:
            findb(i+j,j)
    else:
        for j in [x for x, y in enumerate(st) if y == 'R']:
            findg(i+j,j)
        for j in [x for x, y in enumerate(st) if y == 'G']:
            findr(i+j,j)
print(count)

### FIXED CODE ###

N = int(input())
S = input()
r = S.count('R')
g = S.count('G')
b = S.count('B')
count = r * g * b
for i in range(N):
    for j in range(i+1,N-1):
        if 2*j - i <= N-1:
            l = set([S[i],S[j],S[2*j-i]])
            if len(l) == 3:
                count -= 1
print(count)
### BUGGY CODE ###

import re
s=input()
m=0
for i in range(len(s)):
  dst = re.sub(r'01|10', "", s,1)
  if dst == s:
    break
  s = dst
  m += 2
print(m)

### FIXED CODE ###

s=input();print(min(s.count("0"), s.count("1"))*2)
### BUGGY 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,K=map(int,input().split())
A=list(map(int,input().split()))
MOD=10**9+7
A.sort()
ans=0

for i in range(N-K+1):
    ans+=A[-(i+1)]*cmb(N-(1+i),K-1)
    ans=ans%MOD
    ans-=A[i]*cmb(N-(1+i),K-1)
    ans=ans%MOD

print(ans)

### FIXED CODE ###


N,K=map(int,input().split())
A=list(map(int,input().split()))
MOD=10**9+7
A.sort()

fac=[None for i in range(N)]
finv=[None for i in range(N)]
inv=[None for i in range(N)]

def COMinit(num):
    global fac
    global finv
    global inv
    fac[0]=1
    fac[1]=1
    finv[0]=1
    finv[1]=1
    inv[1]=1

    for i in range(2,num):
        fac[i] = fac[i-1] * i % MOD
        inv[i] = MOD - inv[MOD%i] * (MOD // i) % MOD
        finv[i] = finv[i-1] * inv[i] % MOD

def COM(n,k):
    if n<k:
        return 0
    elif n<0 or k<0:
        return 0
    else:
        return int(fac[n] * (finv[k] * finv[n - k] % MOD) % MOD)
        
ans=0
COMinit(N)

for i in range(N-K+1):
    ans+=A[-(i+1)]*COM(N-(1+i),K-1)
    ans=ans%MOD
    ans-=A[i]*COM(N-(1+i),K-1)
    ans=ans%MOD

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

import sys
import os
import math
import bisect
import collections
import itertools

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

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

lcm = lambda x, y: x * y / math.gcd(x, y)

MOD = 10 ** 9 + 7
MAX = float('inf')


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

    N = ii()
    S = [collections.Counter(iss()) for _ in range(N)]

    ret = 0
    for s in S:
        ret += S.count(s) - 1

    print(ret//2)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
import os


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

    N = int(sys.stdin.readline().rstrip())
    lines = ["".join(sorted(line.rstrip())) for line in sys.stdin.readlines()]

    ret = 0
    sortedlines = {}
    for n in range(N):
        item = lines[n]
        if item in sortedlines:
            sortedlines[item] += 1
            ret += sortedlines[item] - 1
        else:
            sortedlines[item] = 1

    print(ret)


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

A,B,Q = (int(i) for i in input().split())
s = [int(input()) for i in range(A)]
t = [int(input()) for i in range(B)]
x = [int(input()) for i in range(Q)]

def len_L(s,x):
    L= 99999999999
    for i in s:
        if i <= x:
            L = x - i
        else:
            break
    return L

def len_R(s,x):
    for i in s:
        if i >= x:
            return i - x
    return 99999999999

for i in x:
    ls = len_L(s,i)
    lt = len_L(t,i)
    rs = len_R(s,i)
    rt = len_R(t,i)

    mini = min([2*ls+rt , ls+2*rt ,2*rs+lt , rs+2*lt , max([lt,ls]) , max([rt,rs])])
    print(mini)


### FIXED CODE ###

import bisect
A,B,Q = map(int,input().split())
S = [-float('inf')]+list(int(input())for i in range(A))+[float('inf')]
T = [-float('inf')]+list(int(input())for i in range(B))+[float('inf')]
x = list(int(input())for i in range(Q))

for i in x:
    si = bisect.bisect_left(S,i)
    ti = bisect.bisect_left(T,i)
    ans = min(max(S[si],T[ti])-i,i-min(S[si-1],T[ti-1]),\
            2*S[si]-i-T[ti-1],2*T[ti]-i-S[si-1],\
             T[ti]+i-2*S[si-1],S[si]+i-2*T[ti-1])
    print(ans)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
Q = int(input())
n_data = {i: A.count(i) for i in range(1, 10 ** 5 + 1)}
ans = sum(A)
for _ in range(Q):
  b, c = map(int, input().split())
  ans += (c - b) * n_data[b]
  n_data[c] += n_data[b]
  n_data[b] = 0
  print(ans)

### FIXED CODE ###

from collections import Counter


N = int(input())
A = list(map(int, input().split()))
Q = int(input())
n_data = Counter(A)
ans = sum(A)
for _ in range(Q):
  b, c = map(int, input().split())
  ans += (c - b) * n_data[b]
  n_data[c] += n_data[b]
  n_data[b] = 0
  print(ans)
### BUGGY CODE ###

# AtCoder Beginner Contest 125
# https://atcoder.jp/contests/abc125
import sys

s2nn = lambda s: [int(c) for c in s.split(' ')]
ss2nn = lambda ss: [int(s) for s in list(ss)]
ss2nnn = lambda ss: [s2nn(s) for s in list(ss)]
i2s = lambda: sys.stdin.readline().rstrip()
i2n = lambda: int(i2s())
i2nn = lambda: s2nn(i2s())
ii2ss = lambda n: [sys.stdin.readline() for _ in range(n)]
ii2nnn = lambda n: ss2nnn(ii2ss(n))

cache = {}


def gcd(a, b):
    if a not in cache:
        cache[a] = {}
    if b in cache[a]:
        return cache[a][b]
    if b == 0:
        cache[a][b] = a
        return a
    n = gcd(b, a % b)
    cache[a][b] = n
    return n

def main(N, An):
    if N == 2:
        n = max(An[0], An[1])
        print(n)
        return
    nn = [An[0]] * N
    nn[0] = An[1]
    for i in range(1, N):
        for j in range(N):
            if i == j:
                continue
            nn[j] = gcd(nn[j], An[i])
    print(int(max(nn)))

N = i2n()
An = i2nn()
main(N, An)


### FIXED CODE ###

# AtCoder Beginner Contest 125
# https://atcoder.jp/contests/abc125
import sys

s2nn = lambda s: [int(c) for c in s.split(' ')]
ss2nn = lambda ss: [int(s) for s in list(ss)]
ss2nnn = lambda ss: [s2nn(s) for s in list(ss)]
i2s = lambda: sys.stdin.readline().rstrip()
i2n = lambda: int(i2s())
i2nn = lambda: s2nn(i2s())
ii2ss = lambda n: [sys.stdin.readline() for _ in range(n)]
ii2nnn = lambda n: ss2nnn(ii2ss(n))

cache = {}


def gcd(a, b):
    if a not in cache:
        cache[a] = {}
    if b in cache[a]:
        return cache[a][b]
    if b == 0:
        cache[a][b] = a
        return a
    n = gcd(b, a % b)
    cache[a][b] = n
    return n

def main_lte(N, An):
    if N == 2:
        n = max(An[0], An[1])
        print(n)
        return
    nn = [An[0]] * N
    nn[0] = An[1]
    for i in range(1, N):
        for j in range(N):
            if i == j:
                continue
            nn[j] = gcd(nn[j], An[i])
    print(int(max(nn)))

def main(N, An):
    if N == 2:
        n = max(An[0], An[1])
        print(n)
        return
    nn0 = gcd(An[0], An[1])
    nn1 = set((An[0], An[1]))
    for i in range(2, N):
        t1 = nn0
        nn0 = gcd(nn0, An[i])
        t2 = [gcd(n, An[i]) for n in nn1]
        nn1 = set(t2)
        nn1.add(t1)
    n = max(nn1)
    print(int(n))

N = i2n()
An = i2nn()
main(N, An)
### BUGGY CODE ###

import sys
input = sys.stdin.buffer.readline

H, W, M = map(int, input().split())

bomb_h = [0] * H
bomb_w = [0] * W
grid = [[False] * W for _ in range(H)]
for i in range(M):
    h, w = map(int, input().split())
    bomb_h[h-1] += 1
    bomb_w[w-1] += 1
    grid[h-1][w-1] = True

max_h = max(bomb_h)
max_w = max(bomb_w)

h_indices = []
for i in range(H):
    if bomb_h[i] == max_h:
        h_indices.append(i)

w_indices = []
for i in range(W):
    if bomb_w[i] == max_w:
        w_indices.append(i)

ans = max_w + max_h - 1
for h in h_indices:
    for w in w_indices:
        if not grid[h][w]:
            ans += 1
            print(ans)
            exit()

if ans == -1:
    ans = 0

print(ans)


### FIXED CODE ###

import sys
input = sys.stdin.buffer.readline

H, W, M = map(int, input().split())

bomb_h = [0] * H
bomb_w = [0] * W
bomb = set()
for i in range(M):
    h, w = map(int, input().split())
    bomb_h[h-1] += 1
    bomb_w[w-1] += 1
    bomb.add((h-1, w-1))

max_h = max(bomb_h)
max_w = max(bomb_w)

h_indices = []
for i in range(H):
    if bomb_h[i] == max_h:
        h_indices.append(i)

w_indices = []
for i in range(W):
    if bomb_w[i] == max_w:
        w_indices.append(i)

ans = max_w + max_h - 1
for h in h_indices:
    for w in w_indices:
        if (h, w) not in bomb:
            ans += 1
            print(ans)
            exit()

if ans == -1:
    ans = 0

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

from itertools import combinations

N = int(input())
S = input()

ans = set()
for comb in combinations(range(len(S)), 3):
    password = ""
    for c in comb:
        password += S[c]
    ans.add(password)

print(len(ans))

### FIXED CODE ###

N = int(input())
S = input()

ans = 0
for i in range(10):
    a = S.find(str(i))
    if a == -1: continue
    for j in range(10):
        b = S.find(str(j), a + 1)
        if b == -1: continue
        for k in range(10):
            if S.find(str(k), b + 1) != -1:
                ans += 1

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

H,W,K = map(int,input().split())
import numpy as np
from collections import deque
ans = 10000
S = np.array([list(map(int,list(input()))) for _ in range(H)])
for i in range(2**(H-1)):
  q = deque([0])
  for h in range(H):
    if (i>>h)&1:
      q.append(h+1)
  q.append(H)
  p = deque()
  for a in range(len(q)-1):
    p.append(S[q[a]:q[a+1]:,:])
  
  t_a = len(q)-2
  t_b = 0
  judge = False
  for w in range(1,W+1):
    for a in p:
      if np.sum(a[:,t_b:w])>K:
        if w-1==t_b:
          judge = True
          break
        else:
          t_a += 1
          t_b = w-1
          if np.sum(a[:,t_b:w])>K:
            judge = True
            break
    if judge:
      break
  if judge:
    continue
  else:
    ans = min(ans,t_a)
    
print(ans)

### FIXED CODE ###

def main():
  H,W,K = map(int,input().split())
  import numpy as np
  from collections import deque
  ans = 10000
  S = np.array([list(map(int,list(input()))) for _ in range(H)])
  cum = [[0]*W for _ in range(H+1)]
  for j in range(W):
    for i in range(1,H+1):
      cum[i][j] = cum[i-1][j]+S[i-1][j]

  cum = np.array(cum)
  for i in range(2**(H-1)):
    j = 0
    q = deque([0])
    for h in range(H):
      if (i>>h)&1:
        q.append(h+1)
    q.append(H)
    t_a = len(q)-2
    if t_a>=ans:
      continue
    p = deque()
    judge = False
    for a in range(len(q)-1):
      x = cum[q[a+1]]-cum[q[a]]
      if (x>K).any():
        judge = True
        break
      else:
        p.append(list(x))

    if judge:
      continue
    n = len(p)
    l = [0]*n
    for w in range(W):
      y = [l[j]+p[j][w] for j in range(n)]
      if max(y)>K:
        t_a+=1
        l = [p[j][w] for j in range(n)]
        if t_a>=ans:
          judge = True
          break
      else:
        l = y
    if judge:
      continue
    ans = min(ans,t_a)

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

import sys 
     
N,M  = map(int,input().split())
     
a = [[0 for i in range(2)] for j in range(M)]
     
for l in range(M):
  a[l][0] , a[l][1] = map(int,input().split())
     
for l in range(M):
   if a[l][0] == 1:
     for k in range(M):
      if a[k][0] == a[l][1]:
        if a[k][1] == N:
          print('POSSIBLE')
          sys.exit()
print ('IMPOSSIBLE')

### FIXED CODE ###

import sys 

N,M  = map(int,input().split())
     
a = [[0 for i in range(2)] for j in range(M)]
b = [] 
c = []

for i in range(M):
  a[i][0] , a[i][1] = map(int,input().split())
  first, second = a[i][0],a[i][1]
  if first == 1:
    b.append(second)
  if second == N:
    c.append(first)

b_set = set(b)
c_set = set(c)

if list(b_set & c_set) is None or len(list(b_set & c_set)):
  res = ('POSSIBLE')
else:
  res = ('IMPOSSIBLE')

print(res)
### BUGGY CODE ###

n=int(input())
league=[tuple(map(int,input().split())) for _ in range(n)]

total_match=n*(n-1)//2
match=0
day=0

order=[0]*n

for _ in range(total_match):
    day+=1
    today_match=[]

    for i in range(n):
        try:
            m=league[i][order[i]]-1
            if not i in today_match and not m in today_match:
                if league[m][order[m]]-1==i:
                    today_match.extend((i,m))
                    order[i]+=1
                    order[m]+=1
        except:
            continue
    if not today_match:
        day=-1
        break
    match+=len(today_match)//2
    if match>=total_match:
        break

print(day)

### FIXED CODE ###

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

N = int(input())
pair = N * (N - 1) // 2
ptoi = dict()

i = 0
for x in range(1, N):
    for y in range(x + 1, N + 1):
        ptoi[(x, y)] = i
        ptoi[(y, x)] = i
        i += 1

edge = [[] for _ in range(pair)]
indeg = [0] * pair
for i in range(1, N+1):
    inp = list(map(int, input().split()))
    for s, t in zip(inp[:-1], inp[1:]):
        edge[ptoi[(i, s)]].append(ptoi[(i, t)])
        indeg[ptoi[(i, t)]] += 1


now = [i for i, d in enumerate(indeg) if d == 0]
day = 0
while now:
    nxt = []
    while now:
        s = now.pop()
        for t in edge[s]:
            if indeg[t] <= 0:
                continue
            indeg[t] -= 1
            if indeg[t] == 0:
                nxt.append(t)
    day += 1
    now = nxt

if all(i <= 0 for i in indeg):
    print(day)
else:
    print(-1)