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

import sys

N, M = map(int, sys.stdin.readline().split())

def dijkstra(s,n,w,cost):
    #始点sから各頂点への最短距離
    #n:頂点数,　w:辺の数, cost[u][v] : 辺uvのコスト(存在しないときはinf)
    d = [float("inf")] * n
    used = [False] * n
    d[s] = 0
    sign_list = [[0] for _ in range(N - 1)]
    
    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])
               if d[j] == d[v]+cost[v][j]:
                   sign_list[j - 1] = v + 1
               
    return sign_list

cost = [[float("inf") for i in range(N)] for i in range(N)]

for i in range(M):
    x,y = map(int,input().split())
    cost[x - 1][y - 1] = 1
    cost[y - 1][x - 1] = 1
    
sign_list = dijkstra(0,N,M,cost)
flag = True
for i in range(N - 1):
    if sign_list[i] == 0:
        flag = False
        break

if flag:
    print('Yes')
    for i in range(N - 1):
        print(sign_list[i])
else:
    print('No')

### FIXED CODE ###

import sys
from collections import deque

N, M = map(int, sys.stdin.readline().split())
AB = [list(map(int, sys.stdin.readline().split())) for _ in range(M)]

graph = [[] for _ in range(N)]

for a, b in AB:
    graph[a - 1].append(b)
    graph[b - 1].append(a)
    
queue = deque()
visited = [0] * N
sign_list = [0] * N 

queue.append(1)
visited[0] = 1

while queue:
    room = queue.popleft()
    next_rooms = graph[room - 1]
    for r in next_rooms:
        if visited[r - 1] == 0:
            queue.append(r)
            sign_list[r - 1] = room
            visited[r - 1] = 1

yes = True
for s in sign_list[1:]:
    if s == 0:
        yes = False

if yes:
    print("Yes")
    for s in sign_list[1:]:
        print(s)
else:
    print("No")
### BUGGY CODE ###

import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)
sum = 0
K = int(input())
for k in range(K):
  for j in range(K):
    for i in range(K):
      sum = sum + gcd(k+1,j+1,i+1)
print(sum)

### FIXED CODE ###

from math import gcd
sum = 0
K = int(input())
for k in range(1,K+1):
  for j in range(1,K+1):
    t = gcd(k,j)
    for i in range(1,K+1):
      sum += gcd(t,i)
print(sum)
### BUGGY CODE ###

from itertools import combinations
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

n, k = map(int, input().split())
x = [0]* n
y = [0]* n
for i in range(n):
    x[i], y[i] = map(int, input().split())

xc = list(combinations(x,2))
yc = list(combinations(y,2))
ans = 4*10**18

for yy in yc:
    u = max(yy)
    d = min(yy)
    for xx in xc:
        r = max(xx)
        l = min(xx)
        count = 0
        for i in range(n):
            if l <= x[i] <=r and d <= y[i] <=u: count += 1
        if count >= k:
            ans = min(ans, (u-d)*(r-l))

print(ans)


### FIXED CODE ###

from itertools import combinations
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

n, k = map(int, input().split())
x = [0]* n
y = [0]* n
for i in range(n):
    x[i], y[i] = map(int, input().split())

xc = list(combinations(x,2))
yc = list(combinations(y,2))
ans = 4*10**18

for yy in yc:
    u = max(yy)
    d = min(yy)
    for xx in xc:
        r = max(xx)
        l = min(xx)
        count = 0
        for i in range(n):
            if l <= x[i] <=r and d <= y[i] <=u: count += 1
        if count >= k:
            ans = min(ans, (u-d)*(r-l))

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

import itertools
n = int(input())
l = [input() for i in range(n)]
cnt = 0

for x,y in itertools.combinations(l,2):
  
  lx = sorted(x)
  ly = sorted(y)
  if lx == ly:
    cnt += 1

print(cnt)

### FIXED CODE ###

import itertools
n = int(input())
l = ["".join(sorted(input())) for i in range(n)]
d = {}
cnt = 0

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

print(cnt)
### BUGGY CODE ###

data = input().split()
a = int(data[0])
b = int(data[1])
n = int(data[2])

max = 0
for i in range(n+1):
    test = int(a*i/b) - a*int(i/b)
    if max < test:
        max = test
print(max)

### FIXED CODE ###

a,b,n = map(int, input().split())
def func(x):
    return int(a*x/b) - a*int(x/b)

if n < b-1:
    print(func(n))
else :
    print(func(b-1))
### BUGGY CODE ###

import sys
input = sys.stdin.readline
import bisect
n,m = map(int,input().split())
A = list(map(int,input().split()))
A.sort()
#Query = []
#for _ in range(m):
#    b,c = map(int,input().split())
#    Query.append([c,b])
#Query.sort(reverse=True)
Query = [list(map(int,input().split())) for _ in range(m)]
Query = sorted(Query, key=lambda x:(x[1], x[0]), reverse=True)
ans = 0
for b,c in Query:
    #b,c = Query[i][1],Query[i][0]
    #b,c = Query[i][0],Query[i][1]
    if A[0] >= c:
        break
    else:
        #A.sort()
        index = bisect.bisect_left(A,c)
        ans += sum(A[index:])
        if b <= index:
            A = A[b:index]
            A.extend([c]*b)
        else:
            A = [c]*index
    #print(A)
print(ans + sum(A))

### FIXED CODE ###

import sys
input = sys.stdin.readline
import bisect
n,m = map(int,input().split())
A = list(map(int,input().split()))
A.sort()

minA = A[0]
Query = []
for _ in range(m):
    b,c = map(int,input().split())
    if c > minA:
        Query.append([b,c])
Query = sorted(Query, key=lambda x:(x[1], x[0]), reverse=True)

ans = 0
index = 0
for b,c in Query:
    if index >= n:
        break
    #print("----")
    cnt = 0
    Flag = True
    while Flag:
        #print(A,b,c,index)
        if A[index] < c:
            A[index] = c
            cnt += 1
            index += 1
            if (cnt >= b) or (index >= n):
                Flag = False
        else:
            Flag = False
    '''
    #A.sort()
    if A[0] >= c:
        break
    else:
        index = min(bisect.bisect_left(A,c),b)
        if index > len(A):
            ans += c * len(A)
            break
        else:
            ans += c * index
            A = A[index:]
    print(A)
    '''
print(sum(A))
### BUGGY CODE ###

N = int(input())
a = sorted(list(map(int, input().split())))
b = [0 for _ in range (N)]
for i in range(N):
    j = i-1
    while j >= 0:
        if abs(a[i]-a[j])<=1:
            b[i] += 1
            j -= 1
        else:
            break
    j = i+1
    while j <= N-1:
        if abs(a[i]-a[j])<=1:
            b[i] += 1
            j += 1
        else:
            break
print(max(b)+1)

### FIXED CODE ###

a =[0]*100002
n=int(input())
for i in list(map(int,input().split())):
    a[i-1]+=1
    a[i]+=1
    a[i+1]+=1
 
print(max(a))
### BUGGY CODE ###

#d
    
n=int(input())
x=input()

def popcount(m):
    return bin(m).count("1")

intx = int( "0b"+x ,0 )
popcount0 = x.count("1")

jisho = ["yet"]*n
pow2i = pow(2,n)

for i in range(n):
    pow2i //=2
    if x[i]=="0":
        pop = popcount0+1
        intxi = intx+pow2i
    else:
        pop = popcount0-1
        intxi = intx-pow2i
        
    if intxi==0:
        print(0)
        continue
    else:
        c=0
        while intxi!=0:
            if c==0:
                intxi=intxi%pop
            else:
                if jisho[intxi]=="yet":
                    togo = intxi%popcount(intxi)
                    jisho[intxi]= togo
                    intxi = togo
                else:
                    intxi =jisho[intxi]
                
            #print(intxi)
            c+=1
        print(c)
        #print()
#        print("f(n)=",c)

### FIXED CODE ###

#d 
n=int(input())
x=input()

def popcount(m):
    return bin(m).count("1")

intx = int( "0b"+x ,0 )
popcount0 = x.count("1")

intx_mod_pp1 = intx %(popcount0+1)
if popcount0!=1:
    intx_mod_pm1 = intx %(popcount0-1)
    

jisho = ["yet"]*n
# pow2ip = .5
# pow2im = .5

for i in range(n):
    if x[i]=="1" and popcount0==1:
        print(0)
        continue
    
    pow2ip = pow(2,n-i-1,popcount0+1)
    if popcount0!=1:
        pow2im = pow(2,n-i-1,popcount0-1)

    if False:
        pass
    
    
    else:
        intxi=1
        c=0
        while intxi!=0:
            if c==0:
                if x[i]=="0":
                    pop = popcount0+1
                    intxi = (intx_mod_pp1 + pow2ip%pop )%pop
                else:
                    pop = popcount0-1
                    intxi = (intx_mod_pm1 - pow2im%pop )%pop        
            else:
                if jisho[intxi]=="yet":
                    togo = intxi%popcount(intxi)
                    jisho[intxi]= togo
                    intxi = togo
                else:
                    intxi =jisho[intxi]
                
            #print(intxi)
            c+=1
        print(c)
        #print()
    
#        print("f(n)=",c)
### BUGGY CODE ###

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

for i in range(N):
    print(A.index(i+1)+1,end=' ')

### FIXED CODE ###

N=int(input())
keys=list(map(int,input().split()))
A={ value:index  for index,value in enumerate(keys,1) }

for i in range(1,N+1):
    print(A[i],end=' ')
### BUGGY CODE ###

n, p = map(int, input().split())
if n == 1:
    print(p)
else:
    ans = 1
    for i in range(1, 10**6+1):
        if pow(i, n) > p:
            break

        if p % pow(i, n) == 0:
            ans = i
    print(ans)


### FIXED CODE ###

n, p = map(int, input().split())
if n == 1:
    print(p)
else:
    ans = 1
    for i in range(1, 10**6+1):
        if pow(i, n, 10**20) > p:
            break

        if p % pow(i, n, 10**20) == 0:
            ans = i
    print(ans)
### BUGGY CODE ###

N = int(input())
ans = 0
for i in range(1, (N+1)//2):
    for j in range((N+1)//2, N+1):
        if (i + j) == N:
            ans += 1

print(ans)

### FIXED CODE ###

N = int(input())
if N % 2 == 1:
    N += 1
ans = (N/2)-1
print(int(ans))
### BUGGY CODE ###

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

def dfs(v, color):
    colors[v] = color
    for to in g[v]:
        if colors[to] == color: return
        if colors[to] == 0 and not dfs(to, -color):
            return False
    return True

def Washall_Floyd(d):
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j], d[i][k]+d[k][j])
    return d

n = int(input())
g = [[] for _ in range(n)]
f_inf =float('inf')
dist = [[f_inf]*n for _ in range(n)]
for i in range(n): dist[i][i]=0

for i in range(n):
    S = input()
    for j in range(n):
        if S[j] == '1':
            g[i].append(j)
            dist[i][j] = 1
            dist[j][i] = 1

colors = [0] * n
ans = -1
if not dfs(0, 1):
    print(ans)
else:
    Washall_Floyd(dist)
    for d in dist:
      tmp = max(d)
      ans = max(tmp, ans)
    print(ans+1)

### FIXED CODE ###

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

def dfs(v, color):
    colors[v] = color
    for to in g[v]:
        if colors[to] == color: return
        if colors[to] == 0 and not dfs(to, -color):
            return False
    return True

def Washall_Floyd(d):
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j], d[i][k]+d[k][j])
    return d

n = int(input())
g = [[] for _ in range(n)]
f_inf =float('inf')
dist = [[f_inf]*n for _ in range(n)]
for i in range(n): dist[i][i]=0

for i in range(n):
    S = input()
    for j in range(n):
        if S[j] == '1':
            g[i].append(j)
            dist[i][j] = 1
            dist[j][i] = 1

colors = [0] * n
ans = -1
if not dfs(0, 1):
    print(ans)
else:
    Washall_Floyd(dist)
    for d in dist:
      tmp = max(d)
      ans = max(tmp, ans)
    print(ans+1)
### BUGGY CODE ###

N,M = map(int,input().split())
H = list(map(int,input().split()))
List = []
for k in range(1,N+1):
  List.append(k)
for i in range(M):
  A,B = map(int,input().split())
  tmpA = H[A-1]
  tmpB = H[B-1]
  if(tmpA < tmpB):
    if(List.count(A) == 0):
      pass
    else:
      List.remove(A)
  elif(tmpA > tmpB):
    if(List.count(B) == 0):
      pass
    else:
      List.remove(B)
  else:
    if(List.count(A) == 0):
      pass
    else:
      List.remove(A)
    if(List.count(B) == 0):
      pass
    else:
      List.remove(B)
print(str(len(List)))

### FIXED CODE ###

N,M = map(int,input().split())
H = list(map(int,input().split()))
List = [0]*N
for i in range(M):
    A,B = map(int,input().split())
    if(H[A-1] > H[B-1]):
        List[B-1] = 1
    elif(H[A-1] < H[B-1]):
        List[A-1] = 1
    else:
        List[A-1] = 1
        List[B-1] = 1
print(str(List.count(0)))
### BUGGY CODE ###

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

limit_sum = sum(sorted(p_list, reverse=True)[:3])

scope_index = -1
max_sum = 0
for p_i in range(len(p_list)):
    now_sum = 0
    for i in range(k):
        if len(p_list) <= (p_i + i):
            break
        now_sum += p_list[p_i + i]

    if limit_sum == now_sum:
        max_sum = now_sum
        scope_index = p_i
        break

    if max_sum < now_sum:
        max_sum = now_sum
        scope_index = p_i

print((max_sum+k)/2)

### FIXED CODE ###

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

scope_index = 0
max_sum = 0
for i in range(k):
    max_sum += p_list[i]

now_sum = max_sum
for p_i in range(k, len(p_list)):
    now_sum -= p_list[p_i - k]
    now_sum += p_list[p_i]

    if max_sum < now_sum:
        scope_index = p_i
        max_sum = now_sum

ex = (max_sum+k)/2
print(ex)
### BUGGY CODE ###


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

class UnionFind:
    def __init__(self, N):
        self.rank = [0] * N
        self.parent = [i for i in range(N)]
        self.n = N

    def find(self, x):
        if self.parent[x] == x:
            return x
        else:
            self.parent[x] = self.find(self.parent[x])
            return self.parent[x]

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

        if (self.rank[x] < self.rank[y]):
            self.parent[x] = y
        else:
            self.parent[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

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

    def get_parents(self):
        count = 0
        for i in range(self.n):
            if self.find(i) == i:
                count += 1

        return count

N, M = map(int, input().split())
A = [0] * M
B = [0] * M
for i in range(M):
    a, b = map(int, input().split())
    A[i] = a-1
    B[i] = b-1

def count(uf):
    count = 0
    for i in range(N):
        for j in range(i, N):
            if not uf.same(i, j):
                count += 1
    return count

uf = UnionFind(N)

i = M-1
ans = [0] * M
while i >= 0:
    ans[i] = count(uf)
    uf.unite(A[i], B[i])
    i -= 1

for i in ans:
    print(i)


### FIXED CODE ###


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

class UnionFind:
    def __init__(self, N):
        self.rank = [0] * N
        self.parent = [i for i in range(N)]
        self.n = N
        self.size = [1 for i in range(N)]

    def find(self, x):
        if self.parent[x] == x:
            return x
        else:
            self.parent[x] = self.find(self.parent[x])
            return self.parent[x]

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

        if (self.rank[x] < self.rank[y]):
            self.parent[x] = y
            self.size[y] += self.size[x]
        else:
            self.parent[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
                self.size[x] += self.size[y]
            else:
                self.size[x] += self.size[y]

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

    def get_parents(self):
        count = 0
        for i in range(self.n):
            if self.find(i) == i:
                count += 1

        return count

    def get_size(self, x):
        root = self.find(x)
        return self.size[root]



N, M = map(int, input().split())
A = [0] * M
B = [0] * M
for i in range(M):
    a, b = map(int, input().split())
    A[i] = a-1
    B[i] = b-1

uf = UnionFind(N)

i = M-1
ans = [0] * M
x = (N*(N-1)//2)
while i >= 0:
    ans[i] = x

    if not uf.same(A[i], B[i]):
        x -= uf.get_size(A[i]) * uf.get_size(B[i])

    uf.unite(A[i], B[i])
    i -= 1


for i in ans:
    print(i)
### BUGGY CODE ###

r,b,g,n = map(int,input().split())

c = []
ans = 0
c.append(int(n/r))
c.append(int(n/b))
c.append(int(n/g))

for i in range(c[0]+1):
  for j in range(c[1]+1):
    for k in range(c[2]+1):
      if (i*r + j*b + k*g) == n:
        ans += 1

print(ans)

### FIXED CODE ###

r,g,b,n = map(int,input().split())
ans = 0

for i in range(n + 1):
  for j in range(n + 1):
    tmp = n - i*r - j*g
    if tmp >= 0 and tmp%b == 0:
      ans += 1

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

import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
def main():
  n=int(input())
  a=[list(map(int,input().split())) for _ in range(n)]
  f=lambda x:((x[0]-1)*(n-1+n-x[0]+1))//2+x[1]-x[0]-1
  m=(n*(n-1))//2
  g=[[] for _ in range(m)]
  for i in range(n):
    for j in range(n-2):
      if i+1>a[i][j]:
        t0=f((a[i][j],i+1))
      else:
        t0=f((i+1,a[i][j]))
      if i+1>a[i][j+1]:
        t1=f((a[i][j+1],i+1))
      else:
        t1=f((i+1,a[i][j+1]))
      g[t0].append(t1)
  def dfs(t):
    if v[t]:
      if c[t]==0:
        return -1
      else:
        dp[t]
    v[t]=1
    for l in g[t]:
      ret=dfs(l)
      if ret==-1:return -1
      dp[t]=max(dp[t],ret+1)
    c[t]=1
    mi.discard(t)
    return dp[t]
  ans=0
  v=[0]*m
  c=[0]*m
  dp=[0]*m
  #print(g)
  mi=set(list(range(m)))
  while mi:
    i=mi.pop()
    tmp=dfs(i)
    if tmp==-1:
      print(-1)
      exit()
    ans=max(ans,tmp)
    #print(dp)
  print(ans+1)

if __name__=='__main__':
  main()


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
def main():
  n=int(input())
  a=[list(map(int,input().split())) for _ in range(n)]
  f=lambda x:((x[0]-1)*(n-1+n-x[0]+1))//2+x[1]-x[0]-1
  m=(n*(n-1))//2
  g=[[] for _ in range(m)]
  for i in range(n):
    for j in range(n-2):
      if i+1>a[i][j]:
        t0=f((a[i][j],i+1))
      else:
        t0=f((i+1,a[i][j]))
      if i+1>a[i][j+1]:
        t1=f((a[i][j+1],i+1))
      else:
        t1=f((i+1,a[i][j+1]))
      g[t0].append(t1)
  def dfs(t):
    if v[t]:
      if c[t]==0:
        return -1
      else:
        return dp[t]
    v[t]=1
    for l in g[t]:
      ret=dfs(l)
      if ret==-1:return -1
      dp[t]=max(dp[t],ret+1)
    c[t]=1
    mi.discard(t)
    return dp[t]
  ans=0
  v=[0]*m
  c=[0]*m
  dp=[0]*m
  #print(g)
  mi=set(list(range(m)))
  while mi:
    i=mi.pop()
    tmp=dfs(i)
    if tmp==-1:
      print(-1)
      exit()
    ans=max(ans,tmp)
    #print(dp)
  print(ans+1)

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

import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)

K = int(input())

total = 0
for a in range(1,K+1):
  for b in range(1,K+1):
    for c in range(1,K+1):
      total += gcd(a,b,c)
      
print(total)  

### FIXED CODE ###

from math import gcd
 
K = int(input())
 
total = 0
for a in range(1,K+1):
  for b in range(1,K+1):
    for c in range(1,K+1):
      total += gcd(gcd(a,b),c)

print(total)
### BUGGY CODE ###

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

for x in range(1,N+1):
    m = A.index(x) + 1
    B.append(m)
print(*B)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
B = [0] * (N +1)

for i in range(N):
    B[A[i]] = i+1

print(*B[1:])
### BUGGY CODE ###

a,b,k=map(int,input().split())
for i in range(k):
  if a!=0:
    a-=1
  elif b!=0:
    b-=1
  else:
    continue
print(a,b)

### FIXED CODE ###

a,b,k=map(int,input().split())
if a>=k:
  print(a-k,b)
elif a+b>=k:
  print(0,a+b-k)
else:
  print(0,0)
### BUGGY CODE ###

from bisect import bisect_left

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

a.sort(reverse=True)
b = list(reversed(a))

rs = [0] * n
rs[0] = a[0]
for i, x in enumerate(a[1:]):
    rs[i+1] = rs[i] + x

L = 0
H = sum(a) ** 2 + 1

while H - L > 1:
    M = (L + H) // 2
    count = 0
    for x in a:
       count += n - bisect_left(b, M - x)
    if count == m:
        L = M
        break
    elif count > m:
        L = M
    else:
        H = M

ans = 0
count = 0
for x in a:
    c = n - 1 -  bisect_left(b, L - x)
    count += c + 1
    if c >= 0:
        ans += rs[c] + x * (c+1)

print(ans - (count-m) * L)


### FIXED CODE ###

from bisect import bisect_left

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

a.sort(reverse=True)
b = list(reversed(a))

rs = [0] * n
rs[0] = a[0]
for i, x in enumerate(a[1:]):
    rs[i+1] = rs[i] + x

L = a[-1] * 2
H = a[0] * 2

while H - L > 1:
    M = (L + H) // 2
    count = 0
    for x in a:
       count += n - bisect_left(b, M - x)
    if count == m:
        L = M
        break
    elif count > m:
        L = M
    else:
        H = M

ans = 0
count = 0
for x in a:
    c = n - 1 -  bisect_left(b, L - x)
    count += c + 1
    if c >= 0:
        ans += rs[c] + x * (c+1)

print(ans - (count-m) * L)
### BUGGY CODE ###

import sys
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def MAP(): return map(int, input().split())
inf = sys.maxsize

h, w, k = MAP()
s = [[int(i) for i in STR()] for _ in range(h)]

ans = inf
for i in range(2 ** (h - 1)): #縦方向の割り方を全探索 O(512)
    hdiv = [1 if i & 2 ** j else 0 for j in range(h - 1)]
    hdiv.append(1)
    sh = sum(hdiv)
    tmpans = sh - 1
    partsum = [0 for _ in range(sh)]
    j = 0
    while j < w: #O(2 * 10 ** 3)
        tmp = 0
        idx = 0
        flag = True
        for kk in range(h): #O(10)
            tmp += s[kk][j]
            if hdiv[kk]:
                partsum[idx] += tmp
                if partsum[idx] > k:
                    tmpans += 1
                    partsum = [0 for _ in range(sh)]
                    flag = False
                    break
                tmp = 0
                idx += 1
        if flag:
            j += 1
    ans = min(ans, tmpans)
print(ans)


### FIXED CODE ###

import sys
inf = sys.maxsize

if __name__ == '__main__':
    h, w, k = map(int, sys.stdin.readline().strip().split())
    s = [[int(i) for i in sys.stdin.readline().strip()] for _ in range(h)]
    
    ans = inf
    for i in range(2 ** (h - 1)): #縦方向の割り方を全探索 O(512)
        hdiv = [1 if i & 2 ** j else 0 for j in range(h - 1)]
        hdiv.append(1)
        sh = sum(hdiv)
        tmpans = sh - 1
        partsum = [0 for _ in range(sh)]
        partsum_p = [0 for _ in range(sh)]
        j = 0
        for j in range(w): #O(10 ** 3)
            tmp = 0
            idx = 0
            flag = False
            for kk in range(h): #O(10)
                tmp += s[kk][j]
                if hdiv[kk]:
                    partsum_p[idx] = partsum[idx]
                    partsum[idx] += tmp
                    if partsum[idx] > k and not flag:
                        tmpans += 1
                        flag = True
                    tmp = 0
                    idx += 1
            if flag:
                partsum = [partsum[l] - partsum_p[l] for l in range(sh)]
                partsum_p = [0 for _ in range(sh)]
                for kk in range(sh):
                    if partsum[kk] > k:
                        tmpans = inf
                        break
        ans = min(ans, tmpans)
    print(ans)
### BUGGY CODE ###

N,K = map(int,input().split())
p = list(map(int,input().split()))
E = [(1+i)/2 for i in p]
S = [0] + [sum(E[0:i+1]) for i in range(N)]
ans = 0
i = 0
while N-K-i >= 0:
  A = S[K+i] -S[i]
  ans = max(ans,A)
  i += 1
print(ans)

### FIXED CODE ###

N,K = map(int,input().split())
p = list(map(int,input().split()))
E = [(1+i)/2 for i in p]
S = [0]*(N+1)
sum = 0
for i in range(N):
  sum += E[i]
  S[i+1] = sum
ans = 0
i = 0
while N-K-i >= 0:
  A = S[K+i] -S[i]
  ans = max(ans,A)
  i += 1
print(ans)