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

import heapq
from collections import defaultdict
class UnionFind():
    def __init__(self, num):
        self.par = [-1 for _ in range(num)]
    
    def find(self, x):
        if self.par[x] < 0:
            return x
        else:
            x = self.par[x]
            return self.find(x)
    
    def union(self, x, y):
        rx = self.find(x)
        ry = self.find(y)
        if rx != ry:
            if self.par[rx] < self.par[ry]:
                self.par[ry] = rx
            if self.par[rx] > self.par[ry]:
                self.par[rx] = ry
            else:
                self.par[rx] -= 1
                self.par[ry] = rx
        return
def f(nb, nc):
    if nb != N-1:
        return (nb+1, nc)
    return 0
def g(nb, nc):
    if nc != N-1:
        return (nb, nc+1)
    return 0
def inpl(): return [int(i) for i in input().split()]

N, D = inpl()
A = inpl()
B = [(i*D + v, i) for i, v in enumerate(A, 1)]
C = [(-i*D + v, i) for i, v in enumerate(A, 1)]
B.sort()
C.sort()
Z = UnionFind(N+1)
Q = []
ctr = 0
ans = 0
H = defaultdict(lambda: False)
heapq.heappush(Q, (C[0][0] + B[0][0], (0, 0)))
H[(0, 0)] = True
H[0] = True
while ctr < N-1:
    v, (bi, ci) = heapq.heappop(Q)
    _, bj = B[bi]
    _, cj = C[ci]
    if not H[f(bi, ci)]:
        H[(bi+1, ci)] = True
        heapq.heappush(Q, (B[bi+1][0] + C[ci][0], (bi+1, ci)))
    if not H[g(bi, ci)]:
        H[(bi, ci+1)] = True
        heapq.heappush(Q, (B[bi][0] + C[ci+1][0], (bi, ci+1)))
    if bj <= cj:
        continue
    if Z.find(bj) == Z.find(cj):
        continue
    Z.union(bj, cj)
    ans += v
    ctr += 1
print(ans)

### FIXED CODE ###

from operator import itemgetter
import itertools
def inpl(): return list(map(int, input().split()))
def cost(x, y):
    if x == y:
        return float('inf')
    return D * abs(x - y) + A[x] + A[y]
N, D = inpl()
A = inpl()
Right = [(v - i*D, i) for i, v in enumerate(A)]
Left = [(v + i*D, i) for i, v in enumerate(A)][::-1]
Right = list(map(itemgetter(1), itertools.accumulate(Right, min)))
Left = list(map(itemgetter(1), itertools.accumulate(Left, min)))[::-1]
ans = 0
hub = []
for i, (l, r) in enumerate(zip(Left, Right)) :
    if i == l == r:
        hub.append(i)
    else:
        ans += min(cost(i, r), cost(i, l))
print(ans + sum([cost(i, j) for i, j in zip(hub, hub[1:])]))
### BUGGY CODE ###

N = int(input())
mod = 0
if N == 1:
  print(0)
else:
  print(sum(range(2,N))+1)
  

### FIXED CODE ###

N = int(input())
mod = 0
if N == 1:
  print(0)
else:
  print(N+N*(N-1)//2-N)
### BUGGY CODE ###

import itertools as iter
import math as m
from collections import deque

def main():
    N, M = list(map(int, input().split()))
    R = []
    for _ in range(M):
        R.append(list(map(int, input().split())))
    
    q = deque()
    s = set()
    r = [0] * (N+1)
    q.append(1)
    while any(q):
        x = q.popleft()
        s.add(x)
        for i in R:
            if i[0] == x and i[1] not in s and i[1] not in q:
                if r[i[1]] == 0:
                    r[i[1]] = i[0]
                q.append(i[1])
            if i[1] == x and i[0] not in s and i[0] not in q:
                if r[i[0]] == 0:
                    r[i[0]] = i[1]
                q.append(i[0])
        #print(r)
    #print(len(s))
    if len(s) == N:
        print("Yes")
        for i in r[2:]:
            print(i)
    else:
        print("No")
    
        

if __name__ == '__main__':
    main()

### FIXED CODE ###

from collections import deque

def main():
    N, M = list(map(int, input().split()))
    R = [set() for _ in range(N+1)]
    for _ in range(M):
        x = list(map(int, input().split()))
        R[x[0]].add(x[1])
        R[x[1]].add(x[0])
    
    q = deque()
    #s = set()
    r = [0] * (N+1)
    q.append(1)
    while any(q):
        x = q.popleft()
        #s.add(x)
        ro = R[x]
        for i in ro:
            #if r[i] == 0 and i not in s and i not in q:
            if r[i] == 0: 
                r[i] = x
                q.append(i)
    #if len(s) == N:
    print("Yes")
    print("\n".join(map(str, r[2:])))
    #else:
    #    print("No")

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

n, q = map(int,input().split())
s = list(input())
lr = [list(map(int,input().split())) for i in range(q)]
ans = []

for i in range(n-1):
    if s[i] == "A" and s[i+1] == "C":
        s[i] = "*"

for i in range(n):
    ans.append(s[:i].count("*"))

for i in lr:
    l = i[0]
    r = i[1]
    print(ans[r-1] - ans[l-1])


### FIXED CODE ###

n, q = map(int,input().split())
s = list(input())
lr = [list(map(int,input().split())) for i in range(q)]
ans = [0]
x = 0

for i in range(n-1):
    if s[i] == "A" and s[i+1] == "C":
        x += 1
    ans.append(x)

for i in lr:
    l = i[0]
    r = i[1]
    print(ans[r-1] - ans[l-1])
### BUGGY CODE ###

H, W=map(int, input().split())
S=[input() for _ in range(H)]

tate=[[0]*W for _ in range(H)]
yoko=[[0]*W for _ in range(H)]

for i in range(W):
  j=0
  while j<H:
    x=0
    while j+x<H and S[j+x][i]=='.':
      x+=1
    if x==0:
      tate[j][i]=0
      j+=1
    else:
      for t in range(x):
        tate[j+t][i]=x
      j+=x

for i in range(H):
  j=0
  while j<W:
    x=0
    while j+x<W and S[i][j+x]=='.':
      x+=1
    if x==0:
      yoko[i][j]=0
      j+=1
    else:
      for t in range(x):
        yoko[i][j+t]=x
      j+=x
      
print(max([max([tate[i][j]+yoko[i][j]-1 for j in range(W)]) for i in range(H)]))

### FIXED CODE ###

H, W=map(int, input().split())
S=[input() for _ in range(H)]

tate=[[0]*W for _ in range(H)]
yoko=[[0]*W for _ in range(H)]

for i in range(W):
  j=0
  while j<H:
    x=0
    while j+x<H and S[j+x][i]=='.':
      x+=1
    if x==0:
      tate[j][i]=0
      j+=1
    else:
      for t in range(x):
        tate[j+t][i]=x
      j+=x

for i in range(H):
  j=0
  while j<W:
    x=0
    while j+x<W and S[i][j+x]=='.':
      x+=1
    if x==0:
      yoko[i][j]=0
      j+=1
    else:
      for t in range(x):
        yoko[i][j+t]=x
      j+=x
      
print(max([max([tate[i][j]+yoko[i][j]-1 for j in range(W)]) for i in range(H)]))
### BUGGY CODE ###

N, Q = map(int, input().split())
S = input()
lr = [[int(_) for _ in input().split()] for _ in range(Q)]

for l,r in lr:
    Smoji = S[l - 1 :r]
    ans = Smoji.count("AC")

    print(ans)

### FIXED CODE ###

N, Q = map(int, input().split())
S = [ _ for _ in input()]
lr = [[int(_) for _ in input().split()] for _ in range(Q)]
ans = [0] * (N + 1)

for i, data in enumerate(S, 1):
    if data == "A":
        if i >= N:
            break

        if S[i] == "C":
            ans[i] = ans[i - 1] + 1
            continue

    ans[i] = ans[i - 1]

for l, r in lr:
    print(ans[r - 1] - ans[l - 1])
### BUGGY CODE ###

def solve():
  n,k = map(int,input().split())
  h = list(map(int,input().split()))
  dp = [float("inf")]*n
  dp[0] = 0
  for i in range(0,n-1):
    for j in range(1,k+1):
      if (i-j)>=-1:
        dp[i+1]=min(dp[i+1],dp[i+1-j]+abs(h[i+1]-h[i+1-j]))
  print(dp[-1])
solve()

### FIXED CODE ###

def solve():
  n,k = map(int,input().split())
  h = list(map(int,input().split()))
  dp = [float("inf")]*n
  dp[0] = 0
  for i in range(0,n-1):
    for j in range(1,k+1):
      if (i-j)>=-1:
        dp[i+1]=min(dp[i+1],dp[i+1-j]+abs(h[i+1]-h[i+1-j]))
  print(dp[-1])
solve()
### BUGGY CODE ###

n, k = [int(i) for i in input().split()]
h = [int(i) for i in input().split()]
dp = [float('inf')] * n
dp[0] = 0

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

print(dp[n - 1])

### FIXED CODE ###

#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007

#A
def A():
    n = II()
    h = LI()
    dp = [0 for i in range(n)]
    dp[1] = abs(h[0] - h[1])
    for i in range(2,n):
        dp[i] = min(dp[i - 1] + abs(h[i - 1] - h[i]), dp[i - 2] + abs(h[i - 2] - h[i]))
    print(dp[n-1])
    return

#B
def B():
    n, K = LI()
    h = LI()
    dp = [float("INF") for i in range(n + K + 1)]
    dp[0] = 0
    for i in range(n):
        for k in range(1, K + 1):
            if i + k >= n:
                break
            dp[i + k] = min(dp[i + k], dp[i] + abs(h[i] - h[i + k]))
    print(dp[n-1])
    return

#C
def C():
    return

#D
def D():
    return

#E
def E():
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#I
def I():
    return 
#J

#K

#L

#M
#N
# O
# P
# Q
# R
# S
# T
# U
# V
# W
# X
# Y
# Z


#Solve
if __name__ == '__main__':
    B()
### BUGGY CODE ###

import sys

N = int(sys.stdin.readline())
TXY = [
    tuple(map(int, sys.stdin.readline().split())) for _ in range(N)
]

def check(st, sx, sy, et, ex, ey):
    if abs(sx - ex) + abs(sy - ey) > et - st:
        return False
    points = [(sx, sy)]
    for _ in range(et - st):
        new_points = set()
        for px, py in points:
            new_points.add((px + 1, py))
            new_points.add((px - 1, py))
            new_points.add((px, py + 1))
            new_points.add((px, py - 1))
        points = list(new_points)
    if (ex, ey) in points:
        return True
    return False


def main():
    TXY.insert(0, (0, 0, 0))
    for i in range(len(TXY) - 1):
        args = TXY[i] + TXY[i + 1]
        if not check(*args):
            print('No')
            return
    print('Yes')

main()

### FIXED CODE ###

import sys

N = int(sys.stdin.readline())
TXY = [
    tuple(map(int, sys.stdin.readline().split())) for _ in range(N)
]

def check(st, sx, sy, et, ex, ey):
    timespan = et - st
    diff = abs(sx - ex) + abs(sy - ey)
    if diff > timespan:
        return False
    if (timespan - diff) % 2 == 0:
        return True
    return False


def main():
    TXY.insert(0, (0, 0, 0))
    for i in range(len(TXY) - 1):
        args = TXY[i] + TXY[i + 1]
        if not check(*args):
            print('No')
            return
    print('Yes')

main()
### BUGGY CODE ###

import sys
HK,WK,M = map(int, input().split())
hw_s = [list(map(int, input().split())) for _ in range(M)]
W = [0 for _ in range(WK+1)]
H = [0 for _ in range(HK+1)]
HW = [[0 for i in range(WK+1)] for _ in range(HK+1)]
# 3*10^5

for i, hw in enumerate(hw_s):
    h=hw[0]
    w=hw[1]

    H[h] += 1
    W[w] += 1

    HW[h][w] = 1

HMAXES = []
WMAXES = []
answer = 0
HMAX = max(H)
WMAX = max(W)


# 3*10^5
for i, h in enumerate(H):
    if h == HMAX:
        HMAXES.append(i)
for i, w in enumerate(W):
    if w == WMAX:
        WMAXES.append(i)
# 3*10^5
answer = HMAX + WMAX
for i, h in enumerate(HMAXES):
    for j, w in enumerate(WMAXES):
        if HW[h][w] == 0:
            print(answer)
            sys.exit(0)
print(answer-1)

### FIXED CODE ###

import sys
HK,WK,M = map(int, input().split())
W = [0] * (WK + 1)
H = [0] * (HK + 1)
HW = {}
# 3*10^5

for i in range(M):
    h, w = map(int, input().split())

    H[h] += 1
    W[w] += 1

    HW[(h,w)] = 1

answer = 0
HMAX = max(H)
WMAX = max(W)

HEMAX = H.count(HMAX)
WEMAX = W.count(WMAX)
if HEMAX * WEMAX > M:
    print(HMAX + WMAX)
    sys.exit(0)

HMAXES = [i for i, _ in enumerate(H) if _ == HMAX]
WMAXES = [i for i, _ in enumerate(W) if _ == WMAX]

# 3*10^5
answer = HMAX + WMAX
for h in HMAXES:
    for w in WMAXES:
        if not (h,w) in HW:
            print(answer)
            sys.exit(0)
print(answer-1)
### BUGGY CODE ###

N = int(raw_input())
A = [int(raw_input()) - 1 for _ in range(N)]

ans = 0
i = 0
while True:
    if ans != 0 and i in [0, 1]:
        break
    i = A[i]
    ans += 1
if i == 0:
    ans = -1
print ans


### FIXED CODE ###

N = int(raw_input())
A = [int(raw_input()) - 1 for _ in range(N)]

ans = 0
i = 0
used = set([0, 1])
while True:
    if ans != 0 and i in used:
        break
    used.add(i)
    i = A[i]
    ans += 1
if i != 1:
    ans = -1
print ans
### BUGGY CODE ###

def MAIN():
    T = input()
    Q = int(input())
    P = ""
    for _ in range(Q):
        P = input()
        print(1 if P in T else 0)
MAIN()



### FIXED CODE ###

base = 127
mask = (1 << 32) - 1
def calc_hash(f, pl, tl):
    dl = tl - pl
    tmp = set()
    t = 1
    for _ in range(pl):
        t = (t * base) & mask
    e = 0
    for i in range(pl):
        e = (e * base + f[i]) & mask
    for i in range(dl):
        tmp.add(e)
        e = (e * base - t * f[i] + f[i + pl]) & mask
    tmp.add(e)
    return tmp
t = tuple(ord(c) for c in input())
tl = len(t)
q = int(input())
h = dict()
c = dict()
a = []
for _ in range(q):
    p = input()
    if p in c:
        a.append(c[p])
        continue
    p = tuple(ord(c) for c in p)
    pl = len(p)
    if pl > tl:
        a.append("0")
        continue
    bs = min(19, pl)
    keys = calc_hash(p, bs, pl)
    if bs not in h:
        h[bs] = calc_hash(t, bs, tl)
    a.append("1" if keys <= h[bs] else "0")
print('\n'.join(a))
### BUGGY CODE ###

#!/usr/bin/env python3
# -*- coding: utf-8 -*-

import math

N, K = map(int, input().split())
P = list(map(int, input().split()))

def expected(x):
    s = 0
    if x % 2 == 1:
        s = x * math.ceil(x / 2)
    else:
        s = (x + 1) * (x / 2)

    return s / x

b = {}
bb = {}
mx = 0

for i in range(N - K + 1):
    t = ''

    for j in range(K):
        k = i + j
        t += str(k)

    if not t in bb:
        s = 0
        for j in range(K):
            k = i + j
            if not P[k] in b:
                b[P[k]] = expected(P[k])
            s += b[P[k]]
        bb[t] = s

    mx = max(mx, bb[t])

print(mx)


### FIXED CODE ###

#!/usr/bin/env python3
# -*- coding: utf-8 -*-

import math
from collections import deque

N, K = map(int, input().split())
P = list(map(int, input().split()))

def expected(x):
    s = 0
    if x % 2 == 1:
        s = x * math.ceil(x / 2)
    else:
        s = (x + 1) * (x / 2)

    return s / x

b = {}
mx = 0
# 前回分
q = deque()
p = 0

for i in range(N - K + 1):
    s = 0
    # 初回は全部計算
    if i == 0:
        for j in range(K):
            k = i + j
            if not P[k] in b:
                b[P[k]] = expected(P[k])
            s += b[P[k]]
            # 順番に保持
            q.append(b[P[k]])
    else:
        # 追加分
        k = i + (K - 1)
        if not P[k] in b:
            b[P[k]] = expected(P[k])
        # シフト
        f = q.popleft()
        q.append(b[P[k]])

        # 計算
        s = p - f + b[P[k]]

    # 最大更新
    mx = max(mx, s)
    # 前回分として保持
    p = s

print(mx)
### BUGGY CODE ###

import sys
 
n = int(sys.stdin.readline())
 
li = list(map(int, sys.stdin.readline().split()))
 
ans = [0]*n
for i in range(n):
    li2 = li.copy()
    del li2[i]
    for j in range(n-1):
        for k in range(j+1, n-1):
            if li2[j] == li2[k]:
                ans[i] += 1
for l in range(len(ans)):
    print(ans[l])

### FIXED CODE ###

N=int(input())
K=list(map(int, input().split()))
from collections import Counter
ans = 0
C = Counter(K)
for k, v in C.items():
    ans += v*(v-1)//2

for a in K:
    e = C[a]
    print(ans-e*(e-1)//2+(e-1)*(e-2)//2)
### BUGGY CODE ###

from queue import deque
N,M=map(int, input().split())
f=deque()
x=deque()
mx=0
for _ in range(M):
    a,b = map(int, input().split())
    for i in f:
        if a in i[0]:
            if b not in i[0]:
                i[0].add(b)
                i[1]+=1
                mx=max(mx,i[1])
            break
        elif b in i[0]:
            i[0].add(a)
            i[1]+=1
            mx=max(mx,i[1])
            break
    else:
        f.append([set((a,b)),2])
        mx=max(mx,2)

if M == 0:
    mx = 1
print(mx)


### FIXED 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)

N,M=map(int, input().split())
mx=0
uf = UnionFind(N+1)
for i in range(M):
	a,b = map(int, input().split())
	uf.union(a,b)
for i in uf.parents:
	mx = max(mx, uf.size(i))
if M == 0:
	mx = 1
print(mx)
### BUGGY CODE ###

n=int(input())
a=[int(i) for i in input().split()]
a.sort()

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    divisors.sort()
    return divisors

l=make_divisors(a[0])
l2=make_divisors(a[1])
le=len(l)
le2=len(l2)         
an=[0]*le
an2=[0]*le2
for i in range(n):
    for j in range(le):
        if a[i]%l[j]==0:
            an[j]+=1
    for j in range(le2):
        if a[i]%l2[j]==0:
            an2[j]+=1
ans=1
ans2=1
for i in range(le):
    if an[i]>=n-1:
        ans=max(ans,l[i])
for i in range(le2):
    if an2[i]>=n-1:
        ans2=max(ans2,l2[i])

print(max(ans,ans2))




### FIXED CODE ###

n=int(input())
a=[int(i) for i in input().split()]
a.sort()

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    divisors.sort()
    return divisors

l=make_divisors(a[0])
l2=make_divisors(a[1])
le=len(l)
le2=len(l2)         
an=[0]*le
an2=[0]*le2
for i in range(n):
    for j in range(le):
        if a[i]%l[j]==0:
            an[j]+=1
    for j in range(le2):
        if a[i]%l2[j]==0:
            an2[j]+=1
ans=1
ans2=1
for i in range(le):
    if an[i]>=n-1:
        ans=max(ans,l[i])
for i in range(le2):
    if an2[i]>=n-1:
        ans2=max(ans2,l2[i])

print(max(ans,ans2))
### BUGGY CODE ###

# https://atcoder.jp/contests/abc157/tasks/abc157_f

from itertools import combinations

EPS = 1e-8

N, K, *XYC = map(int, open(0).read().split())
PC = [(complex(x, y), c) for x, y, c in zip(*[iter(XYC)] * 3)]


def intersection(A, r, B, s):
    D = B - A
    d = abs(D)

    cos_t = (d * d + r * r - s * s) / (2 * d * r)
    sin_t = max(1 - cos_t * cos_t, 0.0) ** 0.5

    R = r * complex(cos_t, sin_t)
    D /= d

    return (
        A + D * R,
        A + D * R.conjugate(),
    )


def is_ok(T):
    A = [p for p, _ in PC]
    for (p1, c1), (p2, c2) in combinations(PC, 2):
        A += intersection(p1, T / c1, p2, T / c2)

    return any(K <= sum(1 for p, c in PC if c * abs(a - p) < T + EPS) for a in A)


ng, ok = 0, 1000000
for _ in range(80):
    md = (ng + ok) / 2
    if is_ok(md):
        ok = md
    else:
        ng = md

print(ok)

### FIXED CODE ###

from math import hypot
from collections import deque

N, K, *XYC = map(int, open(0).read().split())
XYC = list(zip(*[iter(XYC)] * 3))

Q = deque([(0, 0, 1000.0)])

ans = float("inf")
while Q:
    X, Y, r = Q.popleft()
    if ans * 0.9999995 > sorted(c * hypot(max(abs(X - x) - r, 0), max(abs(Y - y) - r, 0)) for x, y, c in XYC)[K - 1]:
        ans = min(ans, sorted(c * hypot(X - x, Y - y) for x, y, c in XYC)[K - 1])
        for dx, dy in [(-0.5, -0.5), (-0.5, 0.5), (0.5, -0.5), (0.5, 0.5)]:
            Q.append((X + dx * r, Y + dy * r, r / 2))

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

def main():
    n = int(input())
    a = [int(x) for x in input().split()]
    cnt = 0
    while n > 1:
        a_max = max(a[:n])
        a_max_i = a.index(a_max)
        if a_max_i != n-1:
            cnt += (n - a_max_i) * a_max - sum(a[a_max_i:n])
        n = a_max_i
    print(cnt)

if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    n = int(input())
    A = [int(x) for x in input().split()]
    maxv = 0
    ans = 0
    for a in A:
        if maxv > a:
            ans += maxv - a
        else:
            maxv = a  
    print(ans)

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

import sys
readline = sys.stdin.buffer.readline
from collections import deque
INF = float('inf')


def main():
    H, W, K = map(int, readline().split())
    # いつものパターンと問題文のi,jが逆なので、
    # 問題文のxを変数yに、問題文のyを変数xに代入している
    sy, sx, gy, gx = map(int, readline().split())
    lake = [['@' for _ in range(W+2)]]

    for _ in range(H):
        c = ['@'] + list(readline().decode('utf-8').strip()) + ['@']
        lake.append(c)
    lake.append(['@' for _ in range(W+2)])

    dist = [[INF] * (W+2) for _ in range(H+2)]
    dx = (1, 0, -1, 0)
    dy = (0, 1, 0, -1)
    Q = deque()
    Q.append((sy, sx, 0))
    dist[sy][sx] = 0
    while Q:
        y,x,d = Q.popleft()
        if y == gy and x == gx:
            print(d)
            sys.exit()
        for i in range(4):
            for k in range(1,K+1):
                n_y = y + dy[i] * k
                n_x = x + dx[i] * k

                if lake[n_y][n_x] == '.':
                    if dist[n_y][n_x] == INF:
                        dist[n_y][n_x] = d + 1
                        Q.append((n_y,n_x,d+1))
                    else:
                        continue

                else:
                    break
    print('-1')

if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
from collections import deque
 
H, W, K = map(int,readline().split())
x1, y1, x2, y2 = map(int,readline().split())
x1 -= 1; y1 -= 1; x2 -= 1; y2 -= 1
C = read().split()

dist = [[-1]*W for i in range(H)]
dist[x1][y1] = 0
d = deque([[x1, y1]])
dxy= [[1, 0], [0, 1], [-1, 0], [0, -1]]
while d:
  x, y = d.popleft()
  if (x, y) == (x2, y2):
    print(dist[x][y])
    quit()
  for dx, dy in dxy:
    xx = x; yy = y
    for i in range(K):
      xx += dx; yy += dy
      if 0<=xx<H and 0<=yy<W and C[xx][yy]!='@':
        if 0 <= dist[xx][yy] <= dist[x][y]:
          break
        if dist[xx][yy] == -1:
           d.append([xx, yy])
        dist[xx][yy] = dist[x][y] + 1
      else:
        break

print(-1)
### BUGGY CODE ###

from math import ceil
def solve(val):
	z = 0
	for i in range(n):
		if h[i] <= val*b:
			pass
		else:
			z += ceil((h[i]-val*b)/float(a-b))
	if z <= val:
		return True
	else:
		return False
n,a,b = map(int,raw_input().split())
h = [input() for i in range(n)]
lo,hi = 1,max(h)+10
while lo < hi:
	mid = lo+(hi-lo)//2
	if solve(mid):
		hi = mid
	else:
		lo = mid+1
print lo

### FIXED CODE ###

from math import ceil
def solve(val):
	z = 0
	for i in range(n):
		if h[i] <= val*b:
			pass
		else:
			z += ((h[i]-val*b-1)/(a-b))+1
	if z <= val:
		return True
	else:
		return False
n,a,b = map(int,raw_input().split())
h = [input() for i in range(n)]
lo,hi = 1,10**9
while lo < hi:
	mid = lo+(hi-lo)//2
	if solve(mid):
		hi = mid
	else:
		lo = mid+1
print lo