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

def main():
  N,M=map(int,input().split())

  if M == 0:
    print(-1)
    exit()

  INF = 10**6
  pqc = [tuple(map(lambda x:int(x)-1,input().split())) for _ in range(M)]

  to1d={v:{} for v in range(N)}
  count=2
  for p,q,c in pqc:
    if not to1d[p].get(c):
      to1d[p][c] = count
      count += 1
    if not to1d[q].get(c):
      to1d[q][c] = count
      count += 1

  G = [{} for _ in range(count)]
  for p,q,c in pqc:
    v1,v2 = to1d[p][c],to1d[q][c]
    G[v1][v2] = G[v2][v1] = 0

  for v in range(N):
    if len(to1d[v])<=1: continue
    tmp = list(to1d[v].keys())
    for i in range(len(tmp)-1):
      for j in range(i+1,len(tmp)):
        v1,v2 = to1d[v][tmp[i]],to1d[v][tmp[j]]
        G[v1][v2] = G[v2][v1] = 1

  def dijkstra(start = 0, goal = 1):
      from heapq import heappop, heappush
      NN = len(G)
      d = [INF]*NN
      d[start] = 0
      que = []
      heappush(que, start)
      while que:
          p = divmod(heappop(que),NN)
          v = p[1]
          if d[v] < p[0]: continue
          for u in G[v].keys():
              if d[u] > d[v] + G[v][u]:
                  d[u] = d[v] + G[v][u]
                  heappush(que, d[u]*NN+u)
          if v == goal: return d[goal]
      return d[goal]

  for c in to1d[0].keys():
    v = to1d[0][c]
    G[0][v] = 1
  for c in to1d[N-1].keys():
    v = to1d[N-1][c]
    G[v][1] = 0

  ans = dijkstra(0,1)
  print(ans if ans < INF else -1)
  
if __name__=="__main__":
  main()

### FIXED CODE ###

def main():
  N,M=map(int,input().split())

  if M == 0:
    print(-1)
    exit()

  INF = 10**6
  pqc = [tuple(map(lambda x:int(x)-1,input().split())) for _ in range(M)]

  to1d={v:{} for v in range(N)}
  count=2
  for p,q,c in pqc:
    if not to1d[p].get(c):
      to1d[p][c] = count
      count += 1
    if not to1d[q].get(c):
      to1d[q][c] = count
      count += 1

  G = [{} for _ in range(N+count)]
  for p,q,c in pqc:
    v1,v2 = to1d[p][c],to1d[q][c]
    G[v1][v2] = G[v2][v1] = 0

  for i in range(N):
    if len(to1d[i])<=1: continue
    for c in to1d[i].keys():
      v = to1d[i][c]
      G[v][count] = 1
      G[count][v] = 0
    count += 1

  def dijkstra(start = 0, goal = 1):
      from heapq import heappop, heappush
      NN = len(G)
      d = [INF]*NN
      d[start] = 0
      que = []
      heappush(que, start)
      while que:
          p = divmod(heappop(que),NN)
          v = p[1]
          if d[v] < p[0]: continue
          for u in G[v].keys():
              if d[u] > d[v] + G[v][u]:
                  d[u] = d[v] + G[v][u]
                  heappush(que, d[u]*NN+u)
          if v == goal: return d[goal]
      return d[goal]

  for c in to1d[0].keys():
    v = to1d[0][c]
    G[0][v] = 1
  for c in to1d[N-1].keys():
    v = to1d[N-1][c]
    G[v][1] = 0

  ans = dijkstra(0,1)
  print(ans if ans < INF else -1)
  
if __name__=="__main__":
  main()
### BUGGY CODE ###

import sys
import bisect
input = sys.stdin.readline

def main():
    n = int(input())
    s = list(map(int,input().split()))
    ans=0
    point=-1
    for i in range(n-1):
        mark=0
        if i > point and i + ans < n:
            for j in range(n-i-1):
                if s[i+j]>=s[i+j+1]:
                    mark+=1
                    if mark>=ans:
                        ans=mark
                        point=i+j+1
                else:
                    break
    print(ans)
main()

### FIXED CODE ###

def main():
    n = int(input())
    s = list(map(int,input().split()))
    ans=0
    point=-1
    for i in range(n-1):
        mark=0
        if i > point and i + ans < n:
            for j in range(n-i-1):
                if s[i+j]>=s[i+j+1]:
                    mark+=1
                    if mark>=ans:
                        ans=mark
                else:
                    if mark>=ans:
                        ans=mark
                        point=i+j
                    break
    print(ans)
main()
### BUGGY CODE ###

N = int(input())
S = [sorted(list(input())) for n in range(N)]

cnt = 0
for n in range(N):
    s = S.pop(0)
    cnt += S.count(s)

print(cnt)

### FIXED CODE ###

from collections import Counter

def MI():
    return map(int, input().split())

def LI():
    return list(map(int, input().split()))

N = int(input())
S = [list(input()) for _ in range(N)]
cnt = []

for s in S:
    tmp = []
    si = Counter(s)
    for l, c in si.items():
        tmp.append((l, c))
    tmp.sort(key = lambda x : x[0])
    cnt.append(tuple(tmp))
 
cnt = Counter(cnt)
ans = 0

for n in cnt.values():
    ans += n * (n - 1) // 2

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

a, b = map(int, input().split())
i = 1
common = []
while True:
    if a % i == 0 and b % i == 0:
        a //= i
        b //= i
        common.append(i)
    if min(a, b) < i:
        break
    i += 1

count = 1
for i in range(1, len(common)):
    for j in range(1, i):
        if common[i] % common[j] == 0:
            break
    else:
        count += 1
print(count)


### FIXED CODE ###

import fractions
import math
a, b = map(int, input().split())
greatest = fractions.gcd(a, b)

factor = [1]
max_iter = int(math.sqrt(greatest)) + 1
for i in range(2, max_iter):
    while greatest % i == 0:
        greatest //= i
        factor.append(i)
if greatest != 1:
    factor.append(greatest)
factor = set(factor)
print(len(factor))
### BUGGY CODE ###

n = int(input())

a = list(map(int,input().split()))
b = [i for i in a]


def solve(cnt,A,N):
    for i in range(1, N):
        if sum(A[0:i])>0:
            if sum(A[0:i+1])>=0:
                r = A[i]
                A[i]=-sum(A[0:i])-1
                cnt+=abs(r-A[i])
        else:
            if sum(A[0:i+1])<=0:
                r = A[i]
                A[i]=-sum(A[0:i])+1
                cnt+=abs(r-A[i])
    return cnt

cnt1=0
if b[0]<=0:
    ini=b[0]
    b[0]=1
    cnt1=abs(1-ini)


ans1=solve(cnt1,b,n)
cnt2=0
if a[0]>=0:
    ini=a[0]
    a[0]=-1
    cnt2=abs(-1-ini)


ans2=solve(cnt2,a,n)
print(min(ans1,ans2))


### FIXED CODE ###

n = int(input())

a = list(map(int,input().split()))
b = [i for i in a]


def solve(cnt,A,N):
    sumA=A[0]
    for i in range(1, N):
        if sumA>0:
            if sumA+A[i]>=0:
                r = A[i]
                A[i]=-sumA-1
                cnt+=abs(r-A[i])
        else:
            if sumA+A[i]<=0:
                r = A[i]
                A[i]=-sumA+1
                cnt+=abs(r-A[i])

        sumA+=A[i]
    return cnt

cnt1=0
if b[0]<=0:
    ini=b[0]
    b[0]=1
    cnt1=abs(1-ini)


ans1=solve(cnt1,b,n)
cnt2=0
if a[0]>=0:
    ini=a[0]
    a[0]=-1
    cnt2=abs(-1-ini)


ans2=solve(cnt2,a,n)

print(min(ans1,ans2))
### BUGGY CODE ###

input_array = [int(i) for i in input().split()]
S = str(input())

N = int(input_array[0])
K = int(input_array[1])

S_array = list(S)

S_count_array = [0]

count = 0
for i in range(len(S_array)):
  if i == 0:
    S_count_array[count] = 1
  else:
    if S_array[i] == S_array[i-1]:
      S_count_array[count] += 1
    else:
      S_count_array.append(1)
      count += 1

sum_s_number = []
if S_array[0] == "0":
  for i in range(len(S_count_array)):
    if (i+1) % 2 == 0:
      sum_s_number.append(sum(S_count_array[i:i+(K*2)+1]))
    else:
      sum_s_number.append(sum(S_count_array[i:i+(K*2)]))

else:
  for i in range(len(S_count_array)):
    if (i+1) % 2 == 0:
      sum_s_number.append(sum(S_count_array[i:i+(K*2)]))
    else:
      sum_s_number.append(sum(S_count_array[i:i+(K*2)+1]))

print(max(sum_s_number))



### FIXED CODE ###

n,k = map(int,input().split())
s = input()

l = [0]

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

l.append(n)

ans = 0
for i in range(len(l)-1):
  index = min(i+2*k + int(s[l[i]]=="1"), len(l)-1)
  ans = max(ans, l[index] - l[i])

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

#array内で積がx未満になるペアの数
def syakutori_pos(x,array):
    n=len(array)
    res=0
    j=n-1
    for i in range(n):
        tmp=0
#         j=n-1
        y=-(-x//array[i])
        while j!=-1:
            
            if array[j]>=y:
                j-=1
            else:
                break
        
        tmp+=j+1
        if array[i]**2<x:
            tmp-=1
        res+=tmp
    res=res//2
    return res



# #array内で積がx未満になるペアの数
# def syakutori_neg(x,array_pos,array_neg):
#     n_pos=len(array_pos)
#     n_neg=len(array_neg)
#     y=-(-x//array_neg)

#     res=0
#     j=0
#     k=-1
#     for i in range(n_pos):
#         tmp=0

#         while k<n_neg-1:     
#             if y[k+1]<=array_pos[i]:
#                 k+=1
#             else:
#                 break
# #         print(k,y[k])
#         j=max(j,k)
#         while j<n_neg-1:
#             if array_pos[i]<=y[j]:
#                 j+=1
#             else:
#                 break

#         tmp+=j-k+1
#         res+=j-k
#     return n_pos*n_neg-res

def syakutori_neg(x,array_pos,array_neg):
    n_pos=len(array_pos)
    n_neg=len(array_neg)
    y=x//array_neg
    res=0

    for z in y:
        res+=len(A_pos[A_pos>z])
    return res


import numpy as np
N,K=map(int,input().split())
A=list(map(int,input().split()))

A=np.array(A)

A_pos=np.sort(A[A>0])
A_neg=np.sort(A[A<0])
A_neg2=np.sort(-A_neg.copy())
n_post=(len(A_pos)*(len(A_pos)-1)//2)+(len(A_neg)*(len(A_neg)-1))//2
n_zero=len(A[A==0])*(len(A_pos)+len(A_neg))+len(A[A==0])*(len(A[A==0])-1)//2
n_neg=len(A_pos)*len(A_neg)

def syakutori(x):
    if x>0:
        return syakutori_pos(x,A_pos)+syakutori_pos(x,A_neg2)+n_neg+n_zero
    elif x==0:
        return n_neg
    else:
        return syakutori_neg(x,A_pos,A_neg)




r=10**18
l=-10**18
while(r-l>1):
    mid=(l+r)//2
    z=syakutori(mid)
#     z= count_pair(mid)
#     print(l,r)
    if z < K:
        l=mid
    else:
        r=mid
print(l)

### FIXED CODE ###

import numpy as np
N,K=map(int,input().split())
A=list(map(int,input().split()))

A=np.array(A)

A_pos=np.sort(A[A>0])
A_neg=np.sort(A[A<0])
A_neg2=-A_neg[::-1]
n_pos=len(A_pos)
n_neg=len(A_neg)
n_zero=N-n_pos-n_neg

def position_in_neg(x):
    y=n_pos-np.searchsorted(A_pos,x//A_neg,side='right')
    return y.sum()

def position_in_pos(x):
    z=np.searchsorted(A_pos,-(-x//A_pos),side='left')
    w=np.searchsorted(A_neg2,-(-x//A_neg2),side='left')
    tmp=len(A_pos[A_pos**2<x])+len(A_neg2[A_neg2**2<x])
    return (z.sum()+w.sum()-tmp)//2

def position(x):
    if x<0:
        return position_in_neg(x)
    elif x==0:
        return n_pos*n_neg
    else:
        return position_in_pos(x)+n_pos*n_neg+(n_pos+n_neg)*n_zero+n_zero*(n_zero-1)//2

l=-pow(10,18)
r=pow(10,18)
while(r-l>1):
    mid=(l+r)//2
    if position(mid)<K:
        l=mid
    else:
        r=mid
print(l)
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
b = [0] * n

for i in range(1,n+1): #1~nについて
    b[i-1] = a.index(i) + 1

print(*b)

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
b = [0 for j in range(n)]

for i in range(n):
    b[a[i]-1] = i+1

print(*b)
### BUGGY CODE ###

N = int(input())
C=list(input())
type=set(C)
L=0
R=0
X=0
if 'R' in type and 'W' in type:
    for i in range(N):
      L=i
      if L==N-1-R:
        break
      if C[i]=='W':
        type=set(C[i+1:])
        if 'R' in type:
          for ii in range(N-L-R):
            if C[N-1-R-ii]=='R':
              C[L]='R'
              C[N-1-R-ii]='W'
              X+=1
              R+=ii+1
              break
            if L==N-1-R:
              break
        else:
          break
print(X)

### FIXED CODE ###

N = int(input())
C=list(input())
type=set(C)
L=0
R=0
RR=0
X=0
if 'R' in type and 'W' in type:
    for i in range(N):
      L=i
      R=RR
      if L>=N-1-R:
        break
      if C[i]=='W':
          for ii in range(N-L-R):
            if C[N-1-R-ii]=='R':
              C[L]='R'
              C[N-1-R-ii]='W'
              X+=1
              break
            RR+=1
            if L>=N-1-R:
              break
print(X)
### BUGGY CODE ###

N = int(input())
L = list(map(int,input().split()))
ans = 1
for i in range(1,N):
    Pj = min(L[:i])
    Pi = L[i]
    if Pj > Pi:
        ans += 1
print(ans)

### FIXED CODE ###

import sys
read = sys.stdin.buffer.read#全部読み込むやつ
readline = sys.stdin.buffer.readline#1行読み込むやつ
readlines = sys.stdin.buffer.readlines#リストで読み込むらしい


N,*L = map(int,read().split())
ans = 0
Pj = L[0]
for i in L:
    Pj = min(Pj,i)    
    if Pj >= i:
        ans += 1
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
H, W = map(int, input().split())
A = []
for _ in range(H):
    A.append(list(map(int, input().split())))
B = []
C = []
for y in range(H):
    B.append(list(map(int, input().split())))
    C.append(list(abs(a-b) for (a, b) in zip(A[y], B[y])))
VMAX = 80*159+1
dp = [[[0] * VMAX for _ in range(W)] for _ in range(H)]
dp[0][0][C[0][0]] = 1
for y in range(H):
    for x in range(W):
        if y==0 and x==0:
            continue
        for v in range(VMAX):
            if y-1 >= 0 and dp[y-1][x][v]:
                if abs(v+C[y][x]) < VMAX:
                    dp[y][x][abs(v+C[y][x])] = 1
                dp[y][x][abs(v-C[y][x])] = 1
            if x-1 >= 0 and dp[y][x-1][v]:
                if abs(v+C[y][x]) < VMAX:
                    dp[y][x][abs(v+C[y][x])] = 1
                dp[y][x][abs(v-C[y][x])] = 1
ans = -1
for v in range(VMAX):
    if dp[-1][-1][v]:
        ans = v
        break
print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline
H, W = map(int, input().split())
A = []
for _ in range(H):
    A.append(list(map(int, input().split())))
B = []
C = []
for y in range(H):
    B.append(list(map(int, input().split())))
    C.append(list(abs(a-b) for (a, b) in zip(A[y], B[y])))
VMAX = 80*159+1
dp = [[0 for _ in range(W)] for _ in range(H)]
dp[0][0] |= 1 << C[0][0]
for y in range(H):
    for x in range(W):
        if y==0 and x==0:
            continue
        if y-1 >= 0:
            dp[y][x] |= dp[y-1][x] << C[y][x]
            dp[y][x] |= dp[y-1][x] >> C[y][x]
            d = C[y][x]+1
            r = format(dp[y-1][x] & (2**d-1), '0'+str(d)+'b')
            r = r[::-1]
            dp[y][x] |= int(r, 2)
        if x-1 >= 0:
            dp[y][x] |= dp[y][x-1] << C[y][x]
            dp[y][x] |= dp[y][x-1] >> C[y][x]
            d = C[y][x]+1
            r = format(dp[y][x-1] & (2**d-1), '0'+str(d)+'b')
            r = r[::-1]
            dp[y][x] |= int(r, 2)
ans = -1
for v in range(VMAX):
    if dp[-1][-1] >> v & 1:
        ans = v
        break
print(ans)
### BUGGY CODE ###

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())
N,M = [int(hoge) for hoge in input().split()]
Friend = UnionFind(N)
for m in range(M):
    A,B = [int(hoge)-1 for hoge in input().split()]
    Friend.union(A,B)
ans = 0
for G in Friend.all_group_members().values():
    ans = max(ans,len(G))
print(ans)

### FIXED CODE ###

from collections import deque
N,M = [int(hoge) for hoge in input().split()]
Friend = [[] for _ in range(N)]
for m in range(M):
    A,B = [int(hoge)-1 for hoge in input().split()]
    Friend[A].append(B)
    Friend[B].append(A)
Root = [-1]*N
Youso = []
curnum = 0
for n in range(N):
    Y = 0
    if Root[n] == -1:
        Root[n] = curnum
        Y += 1
        queue = deque()#pop,appendleft
        queue.append(n)
        while queue:
            curpos = queue.pop()
            for tsugi in Friend[curpos]:
                if Root[tsugi] == -1:
                    queue.appendleft(tsugi)
                    Root[tsugi] = curnum
                    Y += 1
        Youso.append(Y)
print(max(Youso))
### BUGGY CODE ###

n=int(input())

su = 0
for i in range(1,n+1):
    m = int(n/i)
    su += int(m*(2*i + (m-1)*i)/2)
    

print(su)

### FIXED CODE ###

n=int(input())

su = 0
for i in range(1,n+1):
    m = int(n/i)
    su += int(m*(2*i + (m-1)*i)/2)
    

print(su)
### BUGGY CODE ###

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

r = 'YES'
for i in range(n-1):
    if A[i] in A[i+1:]:
        r = 'NO'
        break
print(r)

### FIXED CODE ###

n = int(input())
A = list(map(int, input().split()))
print('YES' if len(A)==len(set(A)) else 'NO')
### BUGGY CODE ###

N,Q=map(int,input().split())
S=input()

# 最初から数えておく
C=[1 if S[i:i+2]=='AC' else 0 for i in range(N-1)]
#print(C)
#exit()

#print()
#print("#"*20)
for q in range(Q):
    l,r=map(int,input().split())
    #print(S[l-1:r].count("AC"))
    print(sum(C[l-1:r-1]))



### FIXED CODE ###

N,Q=map(int,input().split())
S=input()

# 最初から数えておく
#C=[1 if S[i:i+2]=='AC' else 0 for i in range(N-1)]
C=[0]*(N+1)
for i in range(N):
    C[i+1]=C[i]+(1 if S[i:i+2]=='AC' else 0)
#print(C)
#exit()

#print()
#print("#"*20)
for q in range(Q):
    l,r=map(int,input().split())
    #print(S[l-1:r].count("AC"))
    #print(sum(C[l-1:r-1]))
    print(C[r-1]-C[l-1])
### BUGGY CODE ###

from itertools import accumulate
import sys
input = sys.stdin.readline
from itertools import chain

dp = []
dp2 = []
aac = []

def fdp(l, r):
    global dp, dp2
    if dp2[l][r]:
        return dp[l][r]
    else:
        dp2[l][r] = 1
        if l == r:
            return 0
        result_tmp = float('inf')
        for kugiri in range(l, r):
            result_tmp = min(result_tmp, fdp(l, kugiri) + fdp(kugiri+1, r))
        result = result_tmp + (aac[r+1] - aac[l])
        dp[l][r] = result
        return result
def main():
    global dp, dp2, aac
    n = int(input())
    a = tuple(map(int, input().split()))
    aac = list(accumulate(a))
    aac = tuple(chain([0], aac))
    dp = [[0] * n for _ in range(n)]
    dp2 = [[0] * n for _ in range(n)]
    fdp(0, n - 1)
    print(dp[0][-1])
if __name__ == '__main__':
    main()

### FIXED CODE ###

from itertools import accumulate
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
from itertools import chain

dp = []
dp2 = []
aac = []

def fdp(l, r):
    global dp, dp2
    if dp2[l][r]:
        return dp[l][r]
    else:
        dp2[l][r] = 1
        if l == r:
            return 0
        result_tmp = float('inf')
        for kugiri in range(l, r):
            result_tmp = min(result_tmp, fdp(l, kugiri) + fdp(kugiri+1, r))
        result = result_tmp + (aac[r+1] - aac[l])
        dp[l][r] = result
        return result
def main():
    global dp, dp2, aac
    n = int(input())
    a = tuple(map(int, input().split()))
    aac = list(accumulate(a))
    aac = tuple(chain([0], aac))
    dp = [[0] * n for _ in range(n)]
    dp2 = [[0] * n for _ in range(n)]
    fdp(0, n - 1)
    print(dp[0][-1])
if __name__ == '__main__':
    main()
### BUGGY CODE ###

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

p = []
for i, v in enumerate(A):
  p.append((v, i))
  
p.sort(reverse=True)

dp = [[0] * (n + 1) for _ in range(n + 1)]

for i in range(n):
  k = p[i][0]
  r = p[i][1]
  for x in range(i + 1):
    y = i - x
    dp[x + 1][y] = max(dp[x + 1][y], dp[x][y] + abs(r - x) * k)
    dp[x][y + 1] = max(dp[x][y + 1], dp[x][y] + abs(r - (n - 1 - y)) * k)

ans = 0
for i in range(n):
  ans = max(ans, dp[i][n-i])
  
print(ans)

### FIXED CODE ###

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

p = []
for i, v in enumerate(A):
  p.append((v, i))
  
p.sort(reverse=True)

dp = [[0] * (n + 1) for _ in range(n + 1)]

for i in range(n):
  k = p[i][0]
  r = p[i][1]
  for x in range(i + 1):
    y = i - x
    dp[x + 1][y] = max(dp[x + 1][y], dp[x][y] + abs(r - x) * k)
    dp[x][y + 1] = max(dp[x][y + 1], dp[x][y] + abs(r - (n - 1 - y)) * k)

ans = 0
for i in range(n):
  ans = max(ans, dp[i][n-i])
  
print(ans)
### BUGGY CODE ###

import numpy as np

N = int(input())

A = list(range(N+1))
for n in range(N+1):
    if np.mod(n, 3) == 0 or np.mod(n, 5) == 0:
        A[n] = 0

print(sum(A))

### FIXED CODE ###

N = int(input())

A = list(range(N+1))
for n in range(N+1):
    if n%3 == 0 or n%5 == 0:
        A[n] = 0

print(sum(A))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**9)

def multigcd(n,arr):
  a,b=max(n,arr[0]),min(n,arr[0])
  while b!=0:
    a,b=b,a%b
  if len(arr)==1:
    return a
  else:
    return multigcd(a,arr[1:])

n=int(input())
arr=list(map(int,input().split()))
print(multigcd(arr[0],arr[1:]))

### FIXED CODE ###

def gcd(a,b):
  a,b=max(a,b),min(a,b)
  if b==0:
    return a
  else:
    return gcd(b,a%b)
 
n=int(input())
arr=list(map(int,input().split()))
tmp=gcd(arr[0],arr[1])
for i in range(1,n):
  tmp=gcd(tmp,arr[i])
print(tmp)
### BUGGY CODE ###

H, W, K = map(int, input().split())
S = [input() for _ in range(H)]
ans = 10**9
for bit in range((1 << (H-1))):
    vidx = []
    gok = True
    g = 0
    gid = [0] * H
    for i in range(H-1):
        if (bit >> i) & 1:
            g += 1
        gid[i+1] = g
    g += 1
    gnum = [0]*g
    vertical = 0
    for w in range(W):
        ok = True
        one = [0]*g
        for h in range(H):
            one[gid[h]] += int(S[h][w])
            gnum[gid[h]] += int(S[h][w])
            if one[gid[h]] > K:
                gok = False
            if gnum[gid[h]] > K:
                ok = False
        if not ok:
            vertical += 1
            vidx.append(w)
            gnum = one

    # if bit == 2:
    #    print('aaaaa')
    #    print(gid)
    #    print(vidx)
    #    print(bin(bit), g-1, vertical)
    #    print('aaaaa')
    if gok:
        if ans > g-1 + vertical:
            ans = g-1 + vertical
            # print(bin(bit), g-1, vertical)
            # print(vidx)
            # print(ans)
        # ans = min(ans, g-1 + vertical)
if ans == 10**9:
    print(-1)
else:
    print(ans)


### FIXED CODE ###

# 各行の所属するグループを配列として持たせる実装。列ごと見ていってダメなら垂直線追加していく
H, W, K = map(int, input().split())
S = [input() for _ in range(H)]
ans = 10**9
for bit in range((1 << (H-1))):
    vidx = []
    gok = True
    g = 0
    gid = [0] * H
    for i in range(H-1):
        if (bit >> i) & 1:
            g += 1
        gid[i+1] = g
    g += 1
    gnum = [0]*g
    vertical = 0
    for w in range(W):
        ok = True
        one = [0]*g
        for h in range(H):
            one[gid[h]] += int(S[h][w])
            gnum[gid[h]] += int(S[h][w])
            if one[gid[h]] > K:
                gok = False
            if gnum[gid[h]] > K:
                ok = False
        if not ok:
            vertical += 1
            vidx.append(w)
            gnum = one

    # if bit == 2:
    #    print('aaaaa')
    #    print(gid)
    #    print(vidx)
    #    print(bin(bit), g-1, vertical)
    #    print('aaaaa')
    if gok:
        if ans > g-1 + vertical:
            ans = g-1 + vertical
            # print(bin(bit), g-1, vertical)
            # print(vidx)
            # print(ans)
        # ans = min(ans, g-1 + vertical)
if ans == 10**9:
    print(-1)
else:
    print(ans)