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

import heapq
import math

n, k = map(int, input().split())
a = list(map(int, input().split()))
a.sort(reverse=True)
if k == 0:
    print(a[0])
    exit(0)
mean_a = sum(a) / k
q = []
for aa in a:
    d = max(math.floor(aa / mean_a)-2, 1)
    q.append((-aa/d, d))
    k -= (d-1)
heapq.heapify(q)

for _ in range(k):
    aa, n = heapq.heappop(q)
    heapq.heappush(q, (aa*n/(n+1), n+1))

ans, _ = heapq.heappop(q)
print(math.ceil(-ans))


### FIXED CODE ###

import heapq
import math

n, k = map(int, input().split())
a = list(map(int, input().split()))
a.sort(reverse=True)
if k == 0:
    print(a[0])
    exit(0)
mean_a = sum(a) / k
q = []
for aa in a:
    d = max(math.floor(aa / mean_a), 1)
    q.append((-aa/d, d))
    k -= (d-1)
heapq.heapify(q)

for _ in range(k):
    aa, n = heapq.heappop(q)
    heapq.heappush(q, (aa*n/(n+1), n+1))

ans, _ = heapq.heappop(q)
print(math.ceil(-ans))
### BUGGY CODE ###

#!/usr/bin/env python3
import sys


def solve(X: int, Y: int, Z: int, K: int, A: "List[int]", B: "List[int]", C: "List[int]"):
    C.sort(reverse=True)
    
    count = 0
    AB = []

    for i in range(X):
        for j in range(Y):
            AB.append(A[i]+B[j])
    AB.sort(reverse=True)
    AB = AB[:K]

    ABC = []
    for k in range(Z):
        for ab_index in range(len(AB)):
            ABC.append(C[k]+AB[ab_index])

    ABC.sort(reverse=True)
    ABC = ABC[:K]
    for i in range(len(ABC)):
        print(ABC[i])
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    X = int(next(tokens))  # type: int
    Y = int(next(tokens))  # type: int
    Z = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(X)]  # type: "List[int]"
    B = [int(next(tokens)) for _ in range(Y)]  # type: "List[int]"
    C = [int(next(tokens)) for _ in range(Z)]  # type: "List[int]"
    solve(X, Y, Z, K, A, B, C)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys


def solve(X: int, Y: int, Z: int, K: int, A: "List[int]", B: "List[int]", C: "List[int]"):
    AB = []

    for i in range(X):
        for j in range(Y):
            AB.append(A[i]+B[j])
    AB.sort(reverse=True)
    AB = AB[:K]

    ABC = []
    for k in range(Z):
        for ab_index in range(len(AB)):
            ABC.append(C[k]+AB[ab_index])

    ABC.sort(reverse=True)
    ABC = ABC[:K]
    for i in range(len(ABC)):
        print(ABC[i])
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    X = int(next(tokens))  # type: int
    Y = int(next(tokens))  # type: int
    Z = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(X)]  # type: "List[int]"
    B = [int(next(tokens)) for _ in range(Y)]  # type: "List[int]"
    C = [int(next(tokens)) for _ in range(Z)]  # type: "List[int]"
    solve(X, Y, Z, K, A, B, C)

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

n=int(input())

def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]

ans=0
for i in range(1,n+1):
    ans+=i*len(make_divisors(i))


print(ans)


        




    






### FIXED CODE ###

n=int(input())

yakusu=[0]*(n+1)

for i in range(1,n+1):
    for j in range(1,n+1):
        if i*j<=n:
            yakusu[i*j]+=1
        else:
            break

ans=0
for i,v in enumerate(yakusu):
    ans+=i*v

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

MOD = 10 ** 9 + 7
INF = 10 ** 10
import sys
sys.setrecursionlimit(100000000)

def main():
    N = int(input())
    G = [[] for _ in range(N)]
    dist = []
    for i in range(N):
        route = [int(i) for i in input()]
        for j in range(N):
            if route[j]:
                G[i].append(j)
            elif i != j:
                route[j] = INF
        dist.append(route)
    
    color = [-1]*N
    color[0] = 0
    stack = [0]
    possible = True
    while stack:
        p = stack.pop()
        for e in G[p]:
            if color[e] >= 0:
                if color[e] == color[p]:
                    possible = False
            else:
                color[e] = color[p]^1
                stack.append(e)
        if not possible:
            break
    
    if possible:
        ans = 0
        for k in range(N):
            for i in range(N):
                for j in range(N):
                    dist[i][j] = min(dist[i][j],dist[i][k] + dist[k][j])
        for i in range(N):
            for j in range(N):
                ans = max(ans,dist[i][j])
        print(ans + 1)
    else:
        print(-1)

if __name__ == '__main__':
    main()

### FIXED CODE ###

MOD = 10 ** 9 + 7
INF = 10 ** 10
import sys
sys.setrecursionlimit(100000000)

def main():
    N = int(input())
    G = [[] for _ in range(N)]
    dist = []
    for i in range(N):
        route = [int(i) for i in input()]
        for j in range(N):
            if route[j]:
                G[i].append(j)
            elif i != j:
                route[j] = INF
        dist.append(route)
    
    color = [-1]*N
    color[0] = 0
    stack = [0]
    possible = True
    while stack:
        p = stack.pop()
        for e in G[p]:
            if color[e] >= 0:
                if color[e] == color[p]:
                    possible = False
            else:
                color[e] = color[p]^1
                stack.append(e)
        if not possible:
            break
    
    if possible:
        ans = 0
        for k in range(N):
            for i in range(N):
                for j in range(N):
                    dist[i][j] = min(dist[i][j],dist[i][k] + dist[k][j])
        for i in range(N):
            for j in range(N):
                ans = max(ans,dist[i][j])
        print(ans + 1)
    else:
        print(-1)

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

N = int(input())
V = list(map(int,input().split()))
nums = [v for v in V if V.count(v) != int(N/2)]
print(int(len(nums)/2))


### FIXED CODE ###

N = int(input())
V = list(map(int,input().split()))
even = [0] * (10 ** 5 + 10)
odd = [0] * (10 ** 5 + 10)
for v in V[1::2]:
  even[v] += 1
for v in V[::2]:
  odd[v] += 1
max_even = max(even)
max_odd = max(odd)
if(even.index(max_even) != odd.index(max_odd)):
  print(N - max_even - max_odd)
else:
  even.sort(reverse = True)
  odd.sort(reverse = True)
  print(min(N - even[0] - odd[1], N - even[1] - odd[0]))
### BUGGY CODE ###

S = input()
L = len(S)
cnt = 0

li = [0]
for i in range(L):
    li.append(li[-1]+int(S[i]))

li.append(li[-1])

for i in range(0,L-4):
    for j in range(i+5,L+1):
        if (li[j]-li[i]) % 3 == 0:
            integer = int(S[i:j])
            if integer % 673 == 0:
                cnt += 1

print(cnt)


### FIXED CODE ###

from collections import Counter

S = input()
n = len(S)

dp = [0]*(n+1)

dp[n-1] = int(S[-1])

for i in range(n-2,-1,-1):
    dp[i] = (dp[i+1]+pow(10,n-i-1,2019)*int(S[i]))%2019

ans = Counter(dp)
cnt = 0
for i in ans.values():
    cnt += i*(i-1)//2
    
print(cnt)
### BUGGY CODE ###

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

"""
参考：https://img.atcoder.jp/abc106/editorial.pdf
　　　https://www.hamayanhamayan.com/entry/2018/08/18/234325
・累積和
"""

N, M, Q = map(int, input().split())
lM, rM = [0] * M, [0] * M
pQ, qQ = [0] * Q, [0] * Q
LR = [[0] * N for i in range(N)]
# 都市番号を0-indexed
for i in range(M):
    l, r = map(int, input().split())
    lM[i], rM[i] = l-1, r-1
    LR[l-1][r-1] += 1
for i in range(Q):
    p, q = map(int, input().split())
    pQ[i], qQ[i] = p-1, q-1

# 始点固定で終点を動かした累積和を出す
cnt = [[0] * N for i in range(N)]
for i in range(N):
    cnt[i][i] = LR[i][i]
    for j in range(1, N):
        cnt[i][j] = cnt[i][j-1] + LR[i][j]

for i in range(Q):
    ans = 0
    for j in range(pQ[i], qQ[i]+1):
        # ある終点についてもう和が出てるので、
        # ここでは始点を動かして最終的な合計にする
        ans += cnt[j][qQ[i]]
    print(ans)


### FIXED CODE ###

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

"""
参考：https://img.atcoder.jp/abc106/editorial.pdf
　　　https://www.hamayanhamayan.com/entry/2018/08/18/234325
・累積和
"""

N, M, Q = map(int, input().split())
lM, rM = [0] * M, [0] * M
pQ, qQ = [0] * Q, [0] * Q
LR = [[0] * N for i in range(N)]
# 都市番号を0-indexed
for i in range(M):
    l, r = map(int, input().split())
    lM[i], rM[i] = l-1, r-1
    LR[l-1][r-1] += 1
for i in range(Q):
    p, q = map(int, input().split())
    pQ[i], qQ[i] = p-1, q-1

# 始点固定で終点を動かした累積和を出す
cnt = [[0] * N for i in range(N)]
for i in range(N):
    cnt[i][i] = LR[i][i]
    for j in range(1, N):
        cnt[i][j] = cnt[i][j-1] + LR[i][j]

for i in range(Q):
    ans = 0
    for j in range(pQ[i], qQ[i]+1):
        # ある終点についてもう和が出てるので、
        # ここでは始点を動かして最終的な合計にする
        ans += cnt[j][qQ[i]]
    print(ans)
### BUGGY CODE ###

N, M = map(int, input().split())
l = [[int(a) for a in input().split()] for i in range(N)]
l = sorted(l, key=lambda x: (-1*x[1], -1*x[0]))
ans = 0
j = 0
M += 1
for i in range(1, M+1):
    for k in range(j, N):
        a, b = l[j]
        if a + i <= M:
            ans += b
            j += 1
            break

print(ans)

### FIXED CODE ###

import heapq
N, M = map(int, input().split())

L = [[int(i) for i in input().split()] for i in range(N)]
L = sorted(L, key=lambda x: -x[0])

h = []
ans = 0
j = N-1
for i in range(M-1, -1, -1):
    while j >= 0 and L[j][0] <= M - i:
        heapq.heappush(h, -L[j][1])
        j -= 1
    if len(h) == 0:
        continue
    ans += -heapq.heappop(h)
print(ans)
### BUGGY CODE ###

# seishin.py
from collections import deque
N = int(input())
*P, = map(int, input().split())
MOD = 10**9 + 7

G = [[] for i in range(N+1)]
U = [0]*(N+1)
C = [0]*(N+1)
for i, p in enumerate(P):
    G[p].append(i+1)
    U[i+1] = u = U[p]+1
    C[u] += 1
Q = [None]*(N+1)
PP = {}
def pp(k):
    if k not in PP:
        PP[k] = p = pow(2, k, MOD)
        return p
    return PP[k]
L = [0]*(N+1)

for i in range(N, -1, -1):
    g = G[i]
    if not g:
        continue

    # 子ノードのdequeを集める
    g.sort(key=L.__getitem__, reverse=1)
    k = len(g)
    e = [pp(k) - k, k, 0]

    g0 = g[0]
    L[i] = L[g0] + 1
    if L[g0] == 0:
        Q[i] = deque([e])
        continue
    R = Q[g0]
    for j in g[1:]:
        S = Q[j]
        if not S:
            break

        # dequeの小さい方から大きい方へマージする処理
        for (a0, a1, a2), r in zip(S, R):
            b0, b1, b2 = r
            r[0] = a0*b0 % MOD
            r[1] = (a0*b1 + a1*b0) % MOD
            r[2] = (a0*b2 + a1*b1 + a2*b0 + a1*b2 + a2*b2 + a2*b1) % MOD

    # a0 <- a2
    for r in R:
        r[0] += r[2]
        r[2] = 0
    R.appendleft(e)
    Q[i] = R
ans = pp(N)
for (a0, a1, a2), c in zip(Q[0], C[1:]):
    ans += pp(N+1-c) * a1 % MOD
print(ans % MOD)

### FIXED CODE ###

# seishin.py
from collections import deque
N = int(input())
*P, = map(int, input().split())
MOD = 10**9 + 7

G = [[] for i in range(N+1)]
U = [0]*(N+1)
C = [0]*(N+1)
for i, p in enumerate(P):
    G[p].append(i+1)
    U[i+1] = u = U[p]+1
    C[u] += 1
Q = [None]*(N+1)
PP = {}
def pp(k):
    if k not in PP:
        PP[k] = p = pow(2, k, MOD)
        return p
    return PP[k]
L = [0]*(N+1)

ept = []
sz = L.__getitem__
for i in range(N, -1, -1):
    g = G[i]
    if not g:
        continue

    # 子ノードのdequeを集める
    g.sort(key=sz, reverse=1)
    k = len(g)
    e = [pp(k) - k, k, 0]

    g0 = g[0]
    L[i] = L[g0] + 1
    if L[g0] == 0:
        Q[i] = deque([e])
        continue
    Q[i] = R = Q[g0]
    if k > 1:
        # a0 <- a2
        for s, r in zip(Q[g[1]] or ept, R):
            r[0] += r[2]; r[2] = 0

        for j in g[1:]:
            S = Q[j]
            if not S:
                break

            # dequeの小さい方から大きい方へマージする処理
            for (a0, a1, a2), r in zip(S, R):
                b0, b1, b2 = r; a0 += a2
                r[0] = a0*b0 % MOD
                r[1] = (a0*b1 + a1*b0) % MOD
                r[2] = ((a0+a1)*b2 + a1*b1) % MOD
    R.appendleft(e)
print((pp(N) + sum(pp(N+1-c) * a1 % MOD for (a0, a1, a2), c in zip(Q[0], C[1:]))) % MOD)
### BUGGY CODE ###

import  collections

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

H_count = collections.defaultdict(int)
W_count = collections.defaultdict(int)
points = set()
for m in range(M):
    h, w = map(int, input().split())
    H_count[h] += 1
    W_count[w] += 1
    points.add((h, w))

H_count_sort = sorted(H_count.items(), key=lambda x: x[1])
W_count_sort = sorted(W_count.items(), key=lambda x: x[1])

max_count = 0
for h_count in reversed(H_count_sort):
    for w_count in reversed(W_count_sort):
        count = h_count[1] + w_count[1]
        if (h_count[0], w_count[0]) in points:
            count -= 1

        if max_count > count:
            break
        max_count = max(max_count, count)

print(max_count)

### FIXED CODE ###

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

cnt_h = [0] * (H + 1)
cnt_w = [0] * (W + 1)
points = set()
for m in range(M):
    h, w = map(int, input().split())
    cnt_h[h] += 1
    cnt_w[w] += 1
    points.add((h, w))

H_max = max(cnt_h)
W_max = max(cnt_w)

H_max_num = [i for i, cnt in enumerate(cnt_h) if cnt == H_max]
W_max_num = [i for i, cnt in enumerate(cnt_w) if cnt == W_max]

flag = 0
for h_num in H_max_num:
    for w_num in W_max_num:
        if (h_num, w_num) not in points:
            print(H_max + W_max)
            exit()

print(H_max + W_max -1)
### BUGGY CODE ###

import sys

sys.setrecursionlimit(50000)


waru = 10**9 + 7

memo_ind = []
memo_val = []

def ball_narabe(n, k, i):
    if i == 0:
        if k == 0:
            return 1
        else:
            return 0
    if i > k:
        return 0
    if n < k:
        return 0
    if n == k:
        if i == 1:
            return 1
        else:
            return 0
            
    if i==1:
        # (n-k+1)C(1) を求める
        return n-k+1
    
    put_ball = k - (i-1)
    sum_of_patterns = 0
    while put_ball >= 1:
        sum_of_patterns += ball_narabe(n-put_ball-1, k-put_ball, i-1)
        put_ball -= 1
    
    return (ball_narabe(n-1, k, i) + sum_of_patterns) % waru
    
_n, _k = map(int, input().split())
memo_ind = []
for _i in range(1, _k+1):
    print(ball_narabe(_n, _k, _i))
            

### FIXED CODE ###

import math

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

def count(n, k, i):
    if n-k+1 < i:
        return 0
    return combi(n-k+1, i) * combi(k-1, i-1)

n, k = map(int, input().split())
for i in range(1, k+1):
    print(count(n, k, i) % (10**9+7))
### BUGGY CODE ###

n=int(input())
a=[input().split() for i in range(n)]
import collections as c
import itertools
d=list(itertools.combinations(range(n),2))
cnt=0
for i in d:
    x=c.Counter(a[i[0]][0])
    y=c.Counter(a[i[1]][0])
    if x==y:
        cnt+=1
print(cnt)

### FIXED CODE ###

n=int(input())
import math
d={}
for i in range(n):
    a="".join(sorted(input()))
    if a not in d:
        d[a]=1
    else:
        d[a]+=1
ans=0
for i in d.values():
  ans+=i*(i-1)//2
print(ans)
### BUGGY CODE ###

K,S= list(map(int, input().split()))
ans=0
for i in range(K+1):
    for j in range(K+1):
        if i+j>S:
            break
        for k in range(K+1):
            if i+j+k==S:
                ans+=1
                break
print(ans)

### FIXED CODE ###

K,S= list(map(int, input().split()))
ans=0
for i in range(S//3,K+1):
    for j in range(i+1):
        if i+j>S:
            break
        if i+j*2<S:
            continue
        if S-i-j<=j:
            k=S-i-j
            if i==j==k:
                ans+=1
            elif i==j or j==k:
                ans+=3
            else:
                ans+=6
print(ans)
### BUGGY CODE ###

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

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
from collections import deque
from fractions import gcd
from functools import lru_cache


#############
# Constants #
#############

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

#############
# Functions #
#############

######INPUT######
def inputI(): return int(input().strip())
def inputS(): return input().strip()
def inputIL(): return list(map(int,input().split()))
def inputSL(): return list(map(str,input().split()))
def inputILs(n): return list(int(input()) for _ in range(n))
def inputSLs(n): return list(input().strip() for _ in range(n))
def inputILL(n): return [list(map(int, input().split())) for _ in range(n)]
def inputSLL(n): return [list(map(str, input().split())) for _ in range(n)]

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])
    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])
    return arr

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#############
# Main Code #
#############

N,M = inputIL()
A = inputIL()

R = [A[0]%M]

for i in range(1,N):
  R.append((R[-1]+A[i])%M)
  
dic = [0 for _ in range(M)]
for item in R:
  dic[item]+=1

ans = dic[0]*(dic[0]+1)/2
for i in range(1,M):
  ans += dic[i]*(dic[i]-1)/2

  
print(int(ans))

### FIXED CODE ###

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

R = [A[0]%M]


for i in range(1,N):
  R.append((R[-1]+A[i])%M)



import collections
c = collections.Counter(R)


ans = 0
for key in c:
  if key == 0:
    ans += (c[key]*(c[key]+1))/2
  else:
    ans += (c[key]*(c[key]-1))/2
  



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

n,k=map(int,input().split())
p=list(map(int,input().split()))
sum1=0
max1=0
for i in range(n-k+1):
    sum1=0
    max1=max1
    for j in range(i,i+k):
        sum1=sum1+((1+p[j])/2)
        if sum1>max1:
          max1=sum1
print(max1)

### FIXED CODE ###

n,k=map(int,input().split())
p=list(map(int,input().split()))
sum1=0
a=[]
for j in range(k):
    sum1=sum1+((1+p[j])/2)
a.append(sum1)
for i in range(1,n-k+1):
    sum1=sum1-((1+p[i-1])/2)+((1+p[i+k-1])/2)
    a.append(sum1)
ans=max(a)
print(ans)
### BUGGY CODE ###

k=int(input())
s=input()
ans=0
mod=1000000007
x=2200000
fact=[0]*x
invfact=[0]*x
fact[0]=1
for i in range(1,x):
    fact[i]=fact[i-1]*i%mod
invfact[x-1]=pow(fact[x-1],mod-2,mod)
for i in range(x-2,-1,-1):
    invfact[i]=invfact[i+1]*(i+1)%mod
def nCk(n,k):
    return(fact[n]*invfact[k]*invfact[n-k])%mod
for i in range(0,k+1):
    # print(nCk(len(s)+i-1,i),pow(25,i,mod),pow(26,k-i,mod))
    ans+=nCk(len(s)+i-1,i)*pow(25,i,mod)*pow(26,k-i,mod)
print(ans%mod)

### FIXED CODE ###

k=int(input())
s=input()
ans=0
mod=1000000007
x=2200000
fact=[0]*x
invfact=[0]*x
fact[0]=1
for i in range(1,x):
    fact[i]=fact[i-1]*i%mod
invfact[x-1]=pow(fact[x-1],mod-2,mod)
for i in range(x-2,-1,-1):
    invfact[i]=invfact[i+1]*(i+1)%mod
def nCk(n,k):
    return(fact[n]*invfact[k]*invfact[n-k])%mod
for i in range(0,k+1):
    # print(nCk(len(s)+i-1,i),pow(25,i,mod),pow(26,k-i,mod))
    ans+=nCk(len(s)+i-1,i)*pow(25,i,mod)*pow(26,k-i,mod)
print(ans%mod)
### BUGGY CODE ###

def main():
    import sys
    from collections import deque
    input=sys.stdin.readline

    h,w,k=map(int,input().split())
    sy,sx,gy,gx=map(int,input().split())

    #maze=[]
    #for _ in range(h):
    #    maze.append(tuple(input()))

    maze=[tuple(input()) for _ in range(h)]

    sy-=1
    sx-=1
    gy-=1
    gx-=1

    #maze[sy][sx]="S"

    dis=[[-1]*w for _ in range(h)]



    dis[sy][sx]=0



    d = deque([(sx,sy)])
    while len(d)>0:
        (x,y)=d.popleft()
        if x==gx and y==gy:
            print(dis[gy][gx])
            #maze[gy][gx]="G"

            #pri(dis)
            #pri(maze)

            exit()

        for (mx,my) in ((0,1),(1,0),(-1,0),(0,-1)):
            #print(mx,my,d)
            for j in range(1,k+1):
                nx=x+mx*j
                ny=y+my*j
                #print(y,x,">>",ny,nx)
                if 0<=nx<w and 0<=ny<h:
                    if maze[ny][nx]=="." and (dis[ny][nx]==-1 or dis[ny][nx]==dis[y][x]+1):
                        dis[ny][nx]=dis[y][x]+1
                        d.append((nx,ny))
                        #pri(dis)
                    else:
                        break
                else:
                    break

    print(-1)
        
if __name__ == '__main__':
    main()


                










### FIXED CODE ###

def main():
    import sys
    from collections import deque
    input=sys.stdin.readline

    h,w,k=map(int,input().split())
    sy,sx,gy,gx=map(int,input().split())

    #maze=[]
    #for _ in range(h):
    #    maze.append(tuple(input()))

    maze=[tuple(input()) for _ in range(h)]

    sy-=1
    sx-=1
    gy-=1
    gx-=1

    #maze[sy][sx]="S"

    dis=[[-1]*w for _ in range(h)]



    dis[sy][sx]=0



    d = deque([(sx,sy)])
    while len(d)>0:
        (x,y)=d.popleft()
        if x==gx and y==gy:
            print(dis[gy][gx])
            #maze[gy][gx]="G"

            #pri(dis)
            #pri(maze)

            exit()

        for (mx,my) in ((0,1),(1,0),(-1,0),(0,-1)):
            #print(mx,my,d)
            for j in range(1,k+1):
                nx=x+mx*j
                ny=y+my*j
                #print(y,x,">>",ny,nx)
                if 0<=nx<w and 0<=ny<h:
                    if maze[ny][nx]=="." and (dis[ny][nx]==-1 or dis[ny][nx]==dis[y][x]+1):
                        if dis[ny][nx]==-1:
                            d.append((nx,ny))
                        dis[ny][nx]=dis[y][x]+1
                        
                        #pri(dis)
                    else:
                        break
                else:
                    break

    print(-1)
        
if __name__ == '__main__':
    main()