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

# -*- coding: utf-8 -*-
import collections


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

if p == 2:
    ret = 0
    for i in range(len(s)):
        if int(s[i]) % 2 == 0:
            ret = ret + i + 1
    print(ret)
elif p == 5:
    ret = 0
    for i in range(len(s)):
        if int(s[i]) % 5 == 0:
            ret = ret + i + 1
    print(ret)
else:
    c_list = [0] * n
    for i in range(len(s)):
        c_list[i] = int(s[-i-1:]) % p
    c_list.append(0)
    c = collections.Counter(c_list)
    ret = 0
    for item in c:
        cnt = c[item]
        if cnt >= 2:
            ret = ret + (cnt * (cnt - 1) // 2)
    print(ret)


### FIXED CODE ###

# -*- coding: utf-8 -*-
n, p = map(int, input().split())
s = input()

if p == 2:
    ret = 0
    for i in range(len(s)):
        if int(s[i]) % 2 == 0:
            ret = ret + i + 1
    print(ret)
elif p == 5:
    ret = 0
    for i in range(len(s)):
        if int(s[i]) % 5 == 0:
            ret = ret + i + 1
    print(ret)
else:
    c_list = [0] * n
    power = 1
    for i in range(len(s)):
        c_list[i] = (c_list[i-1] + (int(s[-i-1]) * power)) % p
        power *= 10
        power = power % p
    c_list.append(0)
    counter = [0] * p
    for i in c_list:
        counter[i] += 1
    ret = 0
    for item in counter:
        if item >= 2:
            ret = ret + (item * (item - 1) // 2)
    print(ret)
### BUGGY CODE ###

import itertools

K, S = map(int,input().split())

count = 0
for x,y,z in itertools.product(range(0,K + 1),range(0,K + 1),range(0,K + 1)):
    if x + y + z == S:
        count += 1

print(count)

### FIXED CODE ###

import itertools
    
K, S = map(int,input().split())

count = 0
for x,y in itertools.product(range(0,K + 1),range(0,K + 1)):
    z = S - x - y
    if 0 <= z <= K:
        count += 1

print(count)
### BUGGY CODE ###

import math,sys,bisect,heapq
from collections import defaultdict,Counter,deque
from itertools import groupby,accumulate
sys.setrecursionlimit(200000000)
input = iter(sys.stdin.buffer.read().decode().splitlines()).__next__
ilele = lambda: map(int,input().split())
alele = lambda: list(map(int, input().split()))
def list2d(a, b, c): return [[c] * b for i in range(a)]
#def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
MOD = 1000000000 + 7
def Y(c):  print(["NO","YES"][c])
def y(c):  print(["no","yes"][c])
def Yy(c):  print(["No","Yes"][c])

    
def fun(A,N,h,t,dp):
    if N < 0:
        return 0
    if N==0:
        if h > t:
            return 1
        return 0
    x = dp.get((N,h,t),-1)
    if x!= -1:
        return x
    else:
        dp[(N,h,t)] = A[N-1]*fun(A,N-1,h+1,t,dp) + (1 - A[N-1])*fun(A,N-1,h,t+1,dp)
        return dp[(N,h,t)]
        
N = int(input())
A = list(map(float, input().split()))
dp = {}
print(fun(A,N,0,0,dp))

### FIXED CODE ###

import math,sys,bisect,heapq
from collections import defaultdict,Counter,deque
from itertools import groupby,accumulate
#sys.setrecursionlimit(200000000)
input = iter(sys.stdin.buffer.read().decode().splitlines()).__next__
ilele = lambda: map(int,input().split())
alele = lambda: list(map(int, input().split()))
def list2d(a, b, c): return [[c] * b for i in range(a)]
#def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
MOD = 1000000000 + 7
def Y(c):  print(["NO","YES"][c])
def y(c):  print(["no","yes"][c])
def Yy(c):  print(["No","Yes"][c])

    
def fun(A,N):
    dp = list2d(3000,3000,0)
    dp[0][0] = 1 - A[0]
    dp[0][1] = A[0]
    for i in range(1,N):
        for j in range(3000):
            #tails
            dp[i][j] += (1-A[i])*dp[i-1][j]
            #heads
            if j > 0:
                dp[i][j] += A[i]*(dp[i-1][j-1])
    ans = 0
    for i in range(N//2 + 1,3000):
        ans += dp[N-1][i]
    return ans
        
N = int(input())
A = list(map(float, input().split()))
print(fun(A,N))
### BUGGY CODE ###

n, k = map(int, input().split())
a_in = list(map(int, input().split()))
if n <= k:
    for _ in range(n):
        print(n, end= ' ')
    
diff_list = [0 for num in range(n)]
diff_list[0] = a_in[0]
for i in range(1, n):
    diff_list[i] = a_in[i] - a_in[i-1]

for i in range(k):
    new_list = [0 for num in range(n)]
    d_sum = 0
    for j, d in enumerate(diff_list):
        d_sum += d
        if j-d_sum > 0:
            new_list[j-d_sum] += 1
        else:
            new_list[0] += 1
        if d_sum+j+1 < n:
            new_list[j+d_sum+1] -= 1
    # print(new_list)
    diff_list = new_list.copy()

ans = 0
for d in diff_list:
    ans += d
    print(ans, end= ' ')


### FIXED CODE ###

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

diff_list = [0 for num in range(n)]
diff_list[0] = a_in[0]
for i in range(1, n):
    diff_list[i] = a_in[i] - a_in[i-1]

itr = k
if k > 41:
    itr = 41
for i in range(itr):
    new_list = [0 for num in range(n)]
    d_sum = 0
    for j, d in enumerate(diff_list):
        d_sum += d
        if j-d_sum > 0:
            new_list[j-d_sum] += 1
        else:
            new_list[0] += 1
        if d_sum+j+1 < n:
            new_list[j+d_sum+1] -= 1
    # print(new_list)
    diff_list = new_list.copy()

ans = 0
for d in diff_list:
    ans += d
    print(ans, end= ' ')
### BUGGY CODE ###

n = int(input())
s = input()

ans = 0
for i in range(1000):
    i = str(i).zfill(3)

    one, two, three = False, False, False
    for j in range(n):
        if one:
            if two:
                if three:
                    break
                else:
                    if s[j] == i[2]:
                        three = True
            else:
                if s[j] == i[1]:
                    two = True
        else:
            if s[j] == i[0]:
                one = True
    if three:
        ans += 1
print(ans)


### FIXED CODE ###

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

ans = 0
for i in range(1000):
    s = str(i).zfill(3)

    index = 0
    for j in range(N):
        if s[index] == S[j]:
            index += 1
        if index == 3:
            ans += 1
            break

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

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy,copy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

def main():
    n, k = MAP()
    p = LIST()

    ans = 0
    tmp = 0

    for i in range(n-k+1):
        if tmp <= sum(p[i:i+k]):
            li = p[i:i+k]
            tmp = sum(p[i:i+k])

    #print(li)

    for x in li:
        ans += sum(range(1,x+1))/x

    print(ans)

if __name__=='__main__':
    main()


### FIXED CODE ###

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy,copy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

def main():
    n, k = MAP()
    p = LIST()
    ans = 0
    tmp = 0
    if n == k:
        k = list(accumulate(range(max(p)+1)))
        for x in p:
            ans += k[x]/x
        
        print(ans)
        sys.exit()

    p_ = list(accumulate(p))
    #print(p_)


    for i in range(n-k):
        #print(i,p_[i+k]-p_[i])
        if tmp <= p_[i+k]-p_[i]:
            l = p[i+1:i+k+1]
            tmp = p_[i+k]-p_[i]

    #print('l:',l)
    k = list(accumulate(range(max(l)+1)))

    for x in l:
        ans += k[x]/x
        
    print(ans)

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

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

left_side = 0
right_side = 0
ans = 1e12

for i in range(1, N):
    left_side = sum(A[:i])
    right_side = sum(A[i:])
    ans = min(ans, abs(left_side-right_side))
print(ans)


### FIXED CODE ###

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

left_side = 0
right_side = 0
ans = 1e12
# 両サイドの累積和が必要
left_wa = [0, A[0]]
right_wa = [A[-1]]

for i in range(1, N):
    left_wa.append(left_wa[-1] + A[i])
for i in range(2, N+1):
    right_wa.append(right_wa[-1] + A[-i])
# right_wa.append(0)
# print(left_wa)
# print(right_wa)
#
# exit()
for i in range(1, N):
    left_side = left_wa[i]
    right_side = right_wa[-(i+1)]
    # print(left_side, right_side)
    ans = min(ans, abs(left_side-right_side))
print(ans)
### BUGGY CODE ###

## coding: UTF-8
N,M = map(int,input().split())
H = list(map(int,input().split()))

path = []
for i in range(M):
    path.append(list(map(int,input().split())))

l = [] 
for i in range(N):
    l.append([0] * N + [H[i]])



highest = [0] + [1] * N
#print(highest)
#print(H)
for i in range(M):
    #print('path[i][0] = {}, path[i][1] = {}'.format(path[i][0], path[i][1]))
    #print('H[path[i][0]-1]:{}, H[path[i][1]-1]:{}'.format(H[path[i][0]-1], H[path[i][1]-1]))
    if( H[path[i][1]-1] >= H[path[i][0]-1] ):
        #print('deny at {}'.format(path[i][0]))
        highest[path[i][0]] = 0
    if(  H[path[i][1]-1] <= H[path[i][0]-1]  ):
        #print('deny at {}'.format(path[i][1]))
        highest[path[i][1]] = 0
    #print('highest:{}'.format(highest))

print(sum(highest))

'''
for i in range(M):
    print('path[i][0] = Ai = {}, path[i][1] = Bi = {}'.format(path[i][0], path[i][1]))
    l[ path[i][0]-1 ][ path[i][1]-1 ] = H[path[i][1]-1]
    l[ path[i][1]-1 ][ path[i][0]-1 ] = H[path[i][0]-1]
    print(l)
'''



'''
m_neigh = []
for i in range(N):
    print(l[i][:N])
    m_neigh.append(  max(l[i][:N] )  )
    print(m_neigh)
'''
'''
cnt = 0
for i in range(N):
    
'''

### FIXED CODE ###

## coding: UTF-8
N,M = map(int,input().split())
H = list(map(int,input().split()))

'''
path = []
for i in range(M):
    path.append(list(map(int,input().split())))
'''
path = [list(map(int,input().split())) for i in range(M)]  # 二次元配列入力　二次元マップみたいな入力のとき

'''
l = [] 
for i in range(N):
    l.append([0] * N + [H[i]])
'''


highest = [0] + [1] * N
#print(highest)
#print(H)
for i in range(M):
    #print('path[i][0] = {}, path[i][1] = {}'.format(path[i][0], path[i][1]))
    #print('H[path[i][0]-1]:{}, H[path[i][1]-1]:{}'.format(H[path[i][0]-1], H[path[i][1]-1]))
    pa = path[i]
    p = pa[1]-1
    q = pa[0]-1
    x = H[p]
    y = H[q]
    if( x >= y ):
        #print('deny at {}'.format(path[i][0]))
        highest[q+1] = 0
    if(  x <= y  ):
        #print('deny at {}'.format(path[i][1]))
        highest[p+1] = 0
    #print('highest:{}'.format(highest))

print(sum(highest))

'''
for i in range(M):
    print('path[i][0] = Ai = {}, path[i][1] = Bi = {}'.format(path[i][0], path[i][1]))
    l[ path[i][0]-1 ][ path[i][1]-1 ] = H[path[i][1]-1]
    l[ path[i][1]-1 ][ path[i][0]-1 ] = H[path[i][0]-1]
    print(l)
'''



'''
m_neigh = []
for i in range(N):
    print(l[i][:N])
    m_neigh.append(  max(l[i][:N] )  )
    print(m_neigh)
'''
'''
cnt = 0
for i in range(N):
    
'''
### BUGGY CODE ###

h,n=map(int,input().split())
INF=10**15
a=[]
b=[]
for i in range(n):
    A,B=map(int,input().split())
    a.append(A)
    b.append(B)
dp=[INF]*20010
dp[0]=0
for i in range(20010):
    for j in range(n):
        if i>=a[j]:
            dp[i]=min(dp[i],dp[i-a[j]]+b[j])
ans=min(dp[h:])
print(ans)


### FIXED CODE ###

h,n=map(int,input().split())
INF=10**12
a=[]
b=[]
for i in range(n):
    A,B=map(int,input().split())
    a.append(A)
    b.append(B)
dp=[INF]*20010
dp[0]=0
for i in range(20010):
    for j in range(n):
        if i>=a[j]:
            dp[i]=min(dp[i],dp[i-a[j]]+b[j])
ans=min(dp[h:])
print(ans)
### BUGGY CODE ###

n, m = map(int, input().split())
can_open = []
cost = []
for _ in range(m):
    a, b = map(int, input().split())
    cost.append(a)
    it = map(int, input().split())
    x = 0
    for c in it:
        x += 1 << (c-1)
    can_open.append(x)

n_bit = 1 << n
INF = 10**18
dp = [INF]*n_bit
dp[0] = 0

for j in range(n_bit):
    for i in range(m):
        dp[j | can_open[i]] = min(dp[j | can_open[i]], dp[j]+cost[i])

print(dp[-1] if dp[-1] != INF else -1)


### FIXED CODE ###

n, m = map(int, input().split())
can_open = []
cost = []
for _ in range(m):
    a, b = map(int, input().split())
    cost.append(a)
    it = map(int, input().split())
    x = 0
    for c in it:
        x += 1 << (c-1)
    can_open.append(x)

n_bit = 1 << n
INF = 10**18
dp = [[INF]*n_bit for _ in range(m+1)]
dp[0][0] = 0

# 配る
for i in range(m):
    for j in range(n_bit):
        dp[i+1][j] = min(dp[i+1][j], dp[i][j])

        if (j | can_open[i]) <= n_bit:
            dp[i+1][j | can_open[i]
                    ] = min(dp[i+1][j | can_open[i]], dp[i+1][j]+cost[i])

print(dp[-1][-1] if dp[-1][-1] != INF else -1)
### BUGGY CODE ###

N, Q = map(int, input().split())
S = input()
LR = [list(map(int, input().split())) for i in range(Q)]

for i in range(Q):
  before_a = False
  ans = 0
  for j in range(LR[i][0]-1, LR[i][1]):
    if before_a and S[j] == 'C':
      ans += 1
      before_a = False
    elif S[j] == 'A':
      before_a = True
    else:
      before_a = False
  print(ans)
    

### FIXED CODE ###

N, Q = map(int, input().split())
S = input()
LR = [list(map(int, input().split())) for i in range(Q)]

P = [0] * (N)
before_a = False
cnt = 0
for i in range(N):
  if before_a and S[i] == 'C':
    cnt += 1
    before_a = False
  elif S[i] == 'A':
    before_a = True
  else:
    before_a = False
  P[i] = cnt
for i in range(Q):
  print(P[LR[i][1]-1] - P[LR[i][0]-1])
### BUGGY CODE ###

L = input()
INF = 10**9+7

count = L.count('1')
ans = 2**count
for i in range(len(L)-1,-1,-1):
  if L[i]=='1':
    count -= 1
    m = 3**(len(L)-i-1)*(2**count)
    ans += m
    ans %= INF
print(ans)

### FIXED CODE ###

L = input()
MOD = 10**9+7

pow_3=[1]
for _ in range(2*10**5):
  pow_3.append((pow_3[-1]*3)%MOD)
  
pow_2=[1]
for _ in range(2*10**5):
  pow_2.append((pow_2[-1]*2)%MOD)
  
count = L.count('1')
ans = pow_2[count]

for i in range(len(L)-1,-1,-1):
  if L[i]=='1':
    count -= 1
    m = pow_3[len(L)-i-1]*pow_2[count]
    ans += m
    ans %= MOD
print(ans)
### BUGGY CODE ###

import sys

def main():
    N = int(input())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))
    AB = list(zip(A, B))

    if sum(A) < sum(B):
        print(-1)
        sys.exit()

    if all(map(lambda ab: ab[0] > ab[1], AB)):
        print(0)
        sys.exit()

    bigger_diff = list(map(lambda ab: max(ab[0] - ab[1], 0), AB))
    lesser_diff = list(map(lambda ab: min(ab[0] - ab[1], 0), AB))
    shortage = sum(map(lambda ab: min(ab[0] - ab[1], 0), AB))


    ans = len(list(filter(lambda d: d<0, lesser_diff)))

    bigger_diff = sorted(bigger_diff, reverse=True)

    for i in range(len(bigger_diff)):
        if sum(bigger_diff[:i]) >= abs(shortage):
            ans += i
            break
    print(ans)



if __name__=='__main__':
    main()


### FIXED CODE ###

import sys

def main():
    N = int(input())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))
    AB = list(zip(A, B))
    bigger_diff = list(map(lambda ab: max(ab[0] - ab[1], 0), AB))
    lesser_diff = list(map(lambda ab: min(ab[0] - ab[1], 0), AB))
    exceeded = sum(bigger_diff)
    shortage = sum(lesser_diff)

    if exceeded < abs(shortage):
        print(-1)
        sys.exit()

    if all(map(lambda ab: ab[0] >= ab[1], AB)):
        print(0)
        sys.exit()



    ans = len(list(filter(lambda d: d<0, lesser_diff)))

    bigger_diff = sorted(bigger_diff, reverse=True)

    ss = 0
    for i in range(len(bigger_diff)):
        ss += bigger_diff[i]
        if ss >= abs(shortage):
            ans += i + 1
            break
    print(ans)



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

h,w,a,b=map(int,input().split())
def n_func(n,mod=10**9+7):
    ans=1
    for i in range(1,n+1):ans=(ans*i)%mod
    return ans
def inv_n(n,mod=10**9+7):return pow(n,mod-2,mod)
def nPr(n,r,mod=10**9+7):return inv_n(n_func(n-r,mod),mod)*n_func(n,mod)%mod
def nCr(n,r,mod=10**9+7):return inv_n(n_func(n-r,mod)*n_func(r,mod)%mod,mod)*n_func(n,mod)%mod

cnt=0
for i in range(h-a):
    cnt=(cnt+nCr(i+b-1,i)*nCr(h+w-b-i-2,h-i-1))%(10**9+7)
print(cnt)

### FIXED CODE ###

h,w,a,b=map(int,input().split())
n_func=[None for _ in [0]*200001]
n_func[0]=1
for i in range(1,200001):
    n_func[i]=(i*n_func[i-1])%(10**9+7)
def inv_n(n,mod=10**9+7):return pow(n,mod-2,mod)
def nCr(n,r,mod=10**9+7):return inv_n(n_func[n-r]*n_func[r]%mod,mod)*n_func[n]%mod

cnt=0
for i in range(h-a):
    cnt=(cnt+nCr(i+b-1,b-1)*nCr(h+w-b-i-2,w-b-1))%(10**9+7)
print(cnt)
### BUGGY CODE ###

n,k=map(int,input().split()) #足場は0番目からn-1番目までのn個
h=list(map(int,input().split())) #h[i]はi番目の足場の高さ
DP=[10**9+1]*n
DP[0]=0 #0番目の足場に到達するのに必要なコストは0
DP[1]=abs(h[1]-h[0]) 

#j番目からi番目まで飛ぶ場合の追加コストはabs(h[i]-h[j])、ただしi-1<=j<=i-k

for i in range(2,n):
    for j in range(max(0,i-k),i):
        DP[i]=min(DP[i],DP[j]+abs(h[i]-h[j]))
print(DP[-1])

### FIXED CODE ###

n,k=map(int,input().split()) #足場は0番目からn-1番目までのn個
h=list(map(int,input().split())) #h[i]はi番目の足場の高さ
DP=[10**9+1]*n
DP[0]=0 #0番目の足場に到達するのに必要なコストは0
DP[1]=abs(h[1]-h[0]) 

#j番目からi番目まで飛ぶ場合の追加コストはabs(h[i]-h[j])、ただしi-1<=j<=i-k

for i in range(2,n):
    for j in range(max(0,i-k),i):
        DP[i]=min(DP[i],DP[j]+abs(h[i]-h[j]))
print(DP[-1])
### BUGGY CODE ###

class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i


def main():
    N, Q = (int(i) for i in input().split())
    C = [int(i) for i in input().split()]
    Query = [([int(i) for i in input().split()], j) for j in range(Q)]
    Query.sort(key=lambda p: p[0][1])
    lastappend = [0]*(N+1)
    bit = Bit(N)

    for i, a in enumerate(C, start=1):
        if i <= Query[0][0][1]:
            lastappend[a] = i
    for la in lastappend[1:]:
        if la != 0:
            bit.add(la, 1)
    pre = Query[0][0][1]
    ans = []
    for (le, ri), j in Query:
        if pre <= N and pre < ri:
            for i in range(pre+1, ri+1):
                pre_i = lastappend[C[i-1]]
                if pre_i != 0:
                    bit.add(pre_i, -1)
                lastappend[C[i-1]] = i
                bit.add(i, 1)
            pre = ri
        ans.append((j, bit.sum(ri) - bit.sum(le-1)))
    ans.sort()
    for _, a in ans:
        print(a)


if __name__ == '__main__':
    main()


### FIXED CODE ###

SHIFT = 1 << 20


def main():
    N, Q = (int(i) for i in input().split())
    C = [int(i) for i in input().split()]
    Query = []
    for j in range(Q):
        le, ri = (int(i) for i in input().split())
        Query.append(ri << 40 | le << 20 | j)
    Query.sort()

    # Query復元
    for i in range(Q):
        j = Query[i] % (SHIFT)
        Query[i] >>= 20
        le = Query[i] % (SHIFT)
        Query[i] >>= 20
        ri = Query[i]
        Query[i] = (le, ri, j)
    Query.append((-1, -1, -1))

    def sum(tree, i):
        s = 0
        while i > 0:
            s += tree[i]
            i -= i & -i
        return s

    def add(tree, i, x):
        while i <= N:
            tree[i] += x
            i += i & -i

    lastappend = [-1] * (N + 1)
    bit = [0] * (N + 1)
    idx = 0  # Queryのindex
    ans = [0]*Q

    for i, a in enumerate(C, start=1):
        if lastappend[a] != -1:
            add(bit, lastappend[a], -1)
        lastappend[a] = i
        add(bit, i, 1)
        while i == Query[idx][1]:
            (le, ri, j) = Query[idx]
            ans[j] = sum(bit, ri) - sum(bit, le-1)
            idx += 1

    print(*ans, sep="\n")


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

from collections import deque
import sys
input = sys.stdin.readline
h, w, k = map(int, input().split())
x1, y1, x2, y2 = [int(a) - 1 for a in input().split()]
c = [input() for _ in range(h)]

inf = 10 ** 8
d = [[inf for _ in range(w)] for _ in range(h)]
move = [(1, 0), (0, 1), (-1, 0), (0, -1)]


que = deque()
for i in range(4):
    d[x1][y1] = 0
    que.append((x1, y1))
    
while len(que):
    cur_x, cur_y = que.popleft()
    if cur_x == x2 and cur_y == y2:
        break
    for dx, dy in move:
        to_x, to_y = cur_x, cur_y
        for _ in range(k):
            to_x += dx
            to_y += dy
            if 0 <= to_x < h and 0 <= to_y < w and c[to_x][to_y] == '.' and d[to_x][to_y] > d[cur_x][cur_y]:
                    d[to_x][to_y] = d[cur_x][cur_y] + 1
                    que.append((to_x, to_y))
            else:
                break


print(-1 if d[x2][y2] == inf else d[x2][y2])

### FIXED CODE ###

from collections import deque
import sys
input = sys.stdin.readline
h, w, k = map(int, input().split())
x1, y1, x2, y2 = [int(a) - 1 for a in input().split()]
c = [input() for _ in range(h)]

inf = 10 ** 8
d = [[inf for _ in range(w)] for _ in range(h)]
move = [(1, 0), (0, 1), (-1, 0), (0, -1)]


que = deque()
for i in range(4):
    d[x1][y1] = 0
    que.append((x1, y1))
    
while len(que):
    cur_x, cur_y = que.popleft()
    if cur_x == x2 and cur_y == y2:
        break
    for dx, dy in move:
        to_x, to_y = cur_x, cur_y
        for _ in range(k):
            to_x += dx
            to_y += dy
            if 0 <= to_x < h and 0 <= to_y < w and c[to_x][to_y] == '.':
                if d[to_x][to_y] > d[cur_x][cur_y] + 1:
                    d[to_x][to_y] = d[cur_x][cur_y] + 1
                    que.append((to_x, to_y))
                elif d[to_x][to_y] == d[cur_x][cur_y] + 1:
                    continue
                else:
                    break
            else:
                break


print(-1 if d[x2][y2] == inf else d[x2][y2])
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**6)

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

from itertools import combinations

l.sort()
ans = 0
seen = set()

for c in list(combinations(l,3)):
    if c not in seen:
        seen.add(c)
        if c[0]+c[1]>c[2] and c[1]+c[2]>c[0] and c[2]+c[0]>c[1]:
            ans += 1

print(ans)

### FIXED CODE ###

"""二分探索"""

import sys
sys.setrecursionlimit(10**6)

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

L.sort()
ans = 0

for i in range(n-2):
    for j in range(i+1,n-1):
        l = j; r = n
        while l+1 < r:
            c = (l+r)//2
            if L[c] < L[i]+L[j]:
                l = c
            else:
                r = c
        ans += l-j
        
print(ans)
### BUGGY CODE ###

H,N = map(int,input().split())
A = []
B = []
for i in range(N):
    a,b = map(int,input().split())
    A.append(a)
    B.append(b)

DP = [float('inf')]*(H+max(A))
DP[0] = 0
for i in range(H):
    if DP[i] != float('inf'):
        for j in range(N):
            DP[i+A[j]] = min(DP[i+A[j]],DP[i]+B[j])

ans = min(DP[H:])

print(ans)


### FIXED CODE ###

H,N = map(int,input().split())
magics = [list(map(int,input().split())) for _ in range(N)]

max_A = max(a for a,b in magics)
INF = 10**10
DP = [INF]*(H+max_A)
DP[0] = 0

for i in range(1,H+max_A):
    DP[i] = min(DP[i-a] + b for a,b in magics)
    
ans = min(DP[H:])
print(ans)