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

import numpy as np
import heapq
import sys
sys.setrecursionlimit(10**6)

H,W = map(int,input().split())
INF = 10**18
q = []

d = np.full((H,W),INF,dtype=np.int64) # '#'からの距離

for i in range(H):
  txt = input()
  for j,c in enumerate(txt):
    if c == '#':
      d[i,j] = 0
      heapq.heappush(q,(0,i,j))

while q:
  dv,x,y = heapq.heappop(q)
  for dx,dy in [(0,1),(0,-1),(1,0),(-1,0)]:
    xx = x+dx
    yy = y+dy
    if xx == -1 or xx == H:
      continue
    if yy == -1 or yy == W:
      continue
    if d[xx,yy] == INF:
      d[xx,yy] = dv+1
      heapq.heappush(q,(dv+1,xx,yy))

ans = d.max()
print(ans)

### FIXED CODE ###

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

H,W = map(int,input().split())
INF = 10**18
q = []

visited = [[True]*(W+2)]
visited += [[True] + [x == '#' for x in input().rstrip()] + [True] for _ in range(H)]
visited.append([True]*(W+2))
  
for i in range(1,H+1):
  for j in range(1,W+1):
    if visited[i][j]:
      q.append((i,j))

moves = [(0,1),(0,-1),(1,0),(-1,0)]

ans = -1
while q:
  qq = []
  ans += 1
  for x,y in q:
    if not visited[x-1][y]:
      visited[x-1][y] = True
      qq.append((x-1,y))
    if not visited[x+1][y]:
      visited[x+1][y] = True
      qq.append((x+1,y))
    if not visited[x][y-1]:
      visited[x][y-1] = True
      qq.append((x,y-1))
    if not visited[x][y+1]:
      visited[x][y+1] = True
      qq.append((x,y+1))
  q = qq
  
print(ans)
### BUGGY CODE ###

# 整数の入力
N = int(input())
l = list(map(int, input().split(" ")))

l_ = []
for i in range(N):
    l_.append(l[i] - i - 1)

# print(l_)


count_list = []
for j in range(min(l_), max(l_) + 1):
    # print(j)
    count = 0
    for num in l_:
        count += abs(num - j)

    count_list.append(count)

# print("===")
print(min(count_list))




### FIXED CODE ###

from statistics import median

# 整数の入力
N = int(input())
l = list(map(int, input().split(" ")))
l_ = [num - i - 1 for i, num in enumerate(l)]
l_ = sorted(l_)

b = median(l_)

print(int(sum([abs(i-b) for i in l_])))
### BUGGY CODE ###

import itertools,sys
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
N,W = LI()
wv = [LI() for _ in range(N)]
dp = [[0]*(W+1) for _ in range(N+1)] #1_indexed
for i,j in itertools.product(range(N),range(W+1)):
    w,v = wv[i]
    if j-w>=0:
        dp[i+1][j] = max(dp[i+1][j],dp[i][j-w]+v)
    dp[i+1][j] = max(dp[i+1][j],dp[i][j])
print(dp[-1][-1])


### FIXED CODE ###

import itertools,sys
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
N,W = LI()
wv = [LI() for _ in range(N)]
dp = [[0]*(W+1) for _ in range(N+1)] #1_indexed
for i,j in itertools.product(range(N),range(W+1)):
    w,v = wv[i]
    if j-w>=0:
        dp[i+1][j] = max(dp[i+1][j],dp[i][j-w]+v)
    dp[i+1][j] = max(dp[i+1][j],dp[i][j])
print(dp[-1][-1])
### BUGGY CODE ###

#!/usr/bin/env pypy3


M = 10 ** 9 + 7


def naive_inv_num(xs):
    n = len(xs)
    res = 0
    for i in range(n - 1):
        for j in range(i + 1, n):
            if xs[i] > xs[j]:
                res += 1
    return res


def rep_inv_num(k, xs, mod=M):
    c1 = naive_inv_num(xs)
    c2 = naive_inv_num(xs * 2)
    c3 = naive_inv_num(xs * 3)
    d1 = c2 - c1
    f = c3 - 2 * c2 + c1
    res = c1
    res += (k - 1) * d1
    res %= mod
    res += f * (k - 1) * k // 2
    res %= mod
    res -= f * (k - 1)
    res %= mod
    return res


def main():
    _, k = (int(z) for z in input().split())
    xs = [int(x) for x in input().split()]
    res = rep_inv_num(k, xs)
    print(res)


if __name__ == "__main__":
    main()


### FIXED CODE ###

#!/usr/bin/env pypy3


M = 10 ** 9 + 7


def naive_inv_num(xs):
    n = len(xs)
    res = 0
    for i in range(n - 1):
        for j in range(i + 1, n):
            if xs[i] > xs[j]:
                res += 1
    return res


def rep_inv_num(k, xs, mod=M):
    c1 = naive_inv_num(xs)
    c2 = naive_inv_num(xs * 2)
    c3 = naive_inv_num(xs * 3)
    d1 = c2 - c1
    f = c3 - 2 * c2 + c1
    res = c1
    res += (k - 1) * d1
    res %= mod
    res += f * (k - 1) * k // 2
    res %= mod
    res -= f * (k - 1)
    res %= mod
    return res


def main():
    _, k = (int(z) for z in input().split())
    xs = [int(x) for x in input().split()]
    res = rep_inv_num(k, xs)
    print(res)


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

def inN():
    return int(input())
def inL():
    return list(map(int,input().split()))
def inNL(n):
    return [list(map(int,input().split())) for i in range(n)]

s = input()
n = int(s)
l = len(s)
cnt = 0
mod = [[0]*(l-3) for i in range(l-3)]
#print(mod)
for w in range(4,l+1):
    for i in range(l+1-w):
        j = i + w
        if (w == 4):
            m = int(s[i:j])%2019
            mod[w-4][i] = m
            if m == 0:
                cnt += 1
        else:
            m = (int(s[i])*pow(10,w-1,2019)+mod[w-5][i+1])%2019
            mod[w-4][w-4+i] = m
            if m == 0:
                cnt += 1
#print(mod)
print(cnt)

### FIXED CODE ###

def inN():
    return int(input())
def inL():
    return list(map(int,input().split()))
def inNL(n):
    return [list(map(int,input().split())) for i in range(n)]

s = input()
n = int(s)
l = len(s)
cnt = 0
mod = [0]*2019
m = 0
for i in range(l):
    m = (int(s[l-1-i])*pow(10,i,2019) + m)%2019
    mod[m] += 1

cnt += mod[0]

for i in range(2019):
    if mod[i] > 1:
        cnt += (mod[i]*(mod[i]-1))/2
        #print(i)
print(int(cnt))
### BUGGY CODE ###


def kari():
    N = list(map(int, input().split()))
    A, B = map(int, input().split())

ans_num = 0

# def check(a_sum, b_sum, data, max_length):
#     global ans_num
#     c_sum = sum(data)
#     if c_sum >= max_length:
#         return
#     ans_num += 1


def serch(data, a_sum, max_length, num):
    b_sum = 0
    for i in range(len(data) - 1):
        b_sum += data[i]
        if b_sum >= max_length:
            break
        check(a_sum, b_sum, data[i + 1:], max_length)

def final_check(a_sum, b_sum, c_sum, max_length):
    global ans_num
    if a_sum == 0 or b_sum == 0 or c_sum == 0:
        return
    if a_sum < max_length and b_sum < max_length and c_sum < max_length:
        ans_num += 1


    # print(ans_num)

def check(nex_ind, data, max_length, num, a_sum, b_sum, c_sum):
    if nex_ind >= num:
        final_check(a_sum, b_sum, c_sum, max_length)
        return

    now_point = data[nex_ind]

    a_sum += now_point

    if a_sum >= max_length:
        pass
    else:
        check(nex_ind + 1, data, max_length, num, a_sum, b_sum, c_sum)
    a_sum -= now_point

    b_sum += now_point
    if b_sum >= max_length:
        pass
    else:
        check(nex_ind + 1, data, max_length, num, a_sum, b_sum, c_sum)
    b_sum -= now_point

    c_sum += now_point
    if c_sum >= max_length:
        pass
    else:
        check(nex_ind + 1, data, max_length, num, a_sum, b_sum, c_sum)
    c_sum -= now_point



def main():
    num = int(input())
    data = [int(input()) for i in range(num)]
    sum_data = sum(data)

    if sum_data % 2 == 0:
        max_length = sum_data // 2
    else:
        max_length = (sum_data + 1) // 2

    # print(sum_data, max_length)

    # check([data[0]], [], [], 1, data[1:], max_length, num, data[0], 0, 0)
    # check([], [data[0]], [], 1, data[1:], max_length, num, 0, data[0], 0)
    # check([], [], [data[0]], 1, data[1:], max_length, num, 0, 0, data[0])

    check(1, data, max_length, num, data[0], 0, 0)
    check(1, data, max_length, num, 0, data[0], 0)
    check(1, data, max_length, num, 0, 0, data[0])

    global ans_num
    print(ans_num % 998244353)


if __name__ == '__main__':
    main()


### FIXED CODE ###

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

import numpy as np
MOD = 998244353

N = int(input())
A = [int(input()) for _ in range(N)]
S = sum(A)

# 赤の和がS/2以上となるものを求めて3倍
# 和に対して何通りあるのか

dp = np.zeros(S+1, dtype=np.int64)
dp[0] = 1
for a in A:
    prev = dp
    dp = prev * 2 # 赤以外を採用
    dp[a:] += prev[:-a] # 赤
    dp %= MOD

answer = pow(3,N,MOD) - dp[(1+S)//2:].sum() * 3
# 2色が反例となる場合を引きすぎている
if S % 2 == 0:
    dp = np.zeros(S+1, dtype=np.int64)
    dp[0] = 1
    for a in A:
        dp[a:] += dp.copy()[:-a]
        dp %= MOD
    answer += dp[S//2] * 3
answer %= MOD
print(answer)
### BUGGY CODE ###

import sys, re
from math import ceil, floor, sqrt, pi, factorial, gcd
from copy import deepcopy
from collections import Counter, deque
from heapq import heapify, heappop, heappush
from itertools import accumulate, product, combinations, combinations_with_replacement
from bisect import bisect, bisect_left, bisect_right
from functools import reduce
from decimal import Decimal, getcontext
# input = sys.stdin.readline 
def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_row_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_str(N): return [s_list() for _ in range(N)]
def s_row_list(N): return [list(s_input()) for _ in range(N)]
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 6)
INF = float('inf')
MOD = 10 ** 9 + 7
num_list = []
str_list = []

def main():
    n = i_input()
    s = list(s_input())

    r_count = s.count('R')
    w_count = n - r_count

    if r_count == n or w_count == n:
        print(0)
        exit()

    r_s = s[::-1]

    count = 0

    index = 0
    for i in range(len(s)):
        if r_s[i] == 'W':
            continue
        for j in range(index, n - i - 1):
            if s[j] == 'R':
                continue
            index = j + 1
            r_s[n-index] = 'R'
            r_s[i] = 'W'
            count += 1
            break

    print(min(count, min(r_count, w_count)))

if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys, re
def i_input(): return int(input())
def s_input(): return input()
sys.setrecursionlimit(10 ** 6)

def main():
    n = i_input()
    s = list(s_input())

    r_count = s.count('R')
    w_count = n - r_count

    if r_count == n or w_count == n:
        print(0)
        exit()

    r_s = s[::-1]

    count = 0

    index = 0
    for i in range(len(s)):
        if r_s[i] == 'W':
            continue
        for j in range(index, n - i - 1):
            if s[j] == 'R':
                index = j + 1
                continue
            index = j + 1
            count += 1
            break

    print(min(count, min(r_count, w_count)))

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

# -*- coding: utf-8 -*-
# from collections import deque
from sys import setrecursionlimit

setrecursionlimit(1000000)


# INF = float("inf")

# d = deque()
# ---Input---#
n = int(input())
# n, k = map(int, input().split())
p = list(map(float, input().split()))
p = [-1] + p

memo = [[-1 for _ in [0] * (n + 1)] for _ in [0] * (n + 1)]
memo[0][0] = 1
for i in range(len(p))[1:]:
    memo[0][i] = 0
    memo[i][0] = memo[i - 1][0] * (1 - p[i])
memo[0][0] = 1


def dp(i, j):
    if memo[i][j] == -1:
        memo[i][j] = dp(i - 1, j) * (1 - p[i]) + dp(i - 1, j - 1) * p[i]
    return memo[i][j]


ans = 0
tar = int(n / 2) + 1
for i in range(n + 1)[tar:]:
    ans += dp(n, i)


print("{}".format(ans))


### FIXED CODE ###

# -*- coding: utf-8 -*-
# from collections import deque
from sys import setrecursionlimit

setrecursionlimit(1000000)


# INF = float("inf")

# d = deque()
# ---Input---#
n = int(input())
# n, k = map(int, input().split())
p = list(map(float, input().split()))
p = [-1] + p

memo = [[-1 for _ in [0] * (n + 1)] for _ in [0] * (n + 1)]
memo[0][0] = 1
for i in range(len(p))[1:]:
    memo[0][i] = 0
    memo[i][0] = memo[i - 1][0] * (1 - p[i])
memo[0][0] = 1


def dp(i, j):
    if memo[i][j] == -1:
        memo[i][j] = dp(i - 1, j) * (1 - p[i]) + dp(i - 1, j - 1) * p[i]
    return memo[i][j]


ans = 0
tar = int(n / 2) + 1
for i in range(n + 1):
    dp(i, i)
    dp(i, n)

for i in range(n + 1)[tar:]:
    ans += dp(n, i)


print("{}".format(ans))
### BUGGY CODE ###

from collections import deque
h, w = map(int, input().split())

field = [] # 白黒情報を持つリスト
mark = [] # 操作回数を保持するリスト
INF = 10**6

for i in range(h):
    field.append(list(input()))
    mark.append([0 for i in range(w)])

dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]

queue = deque()
for i in range(h):
    for j in range(w):
        if field[i][j] == "#":
            queue.append([i, j])

while len(queue) > 0:
    y, x = queue.popleft()
    for k in range(4):
        nx = x + dx[k]
        ny = y + dy[k]
        if 0 <= ny < h and 0 <= nx < w:
            if field[ny][nx] == ".":
                mark[ny][nx] = mark[y][x] + 1
                queue.append([ny, nx])
                field[ny][nx] = "#"

ans=0

for i in mark:
    ans = max(ans, max(i))

print(ans)


### FIXED CODE ###

from collections import deque
h, w = map(int, input().split())

field = [] # 白黒情報を持つリスト
mark = [] # 操作回数を保持するリスト
INF = 10**6

for i in range(h):
    field.append(list(input()))
    mark.append([0 for i in range(w)])

dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]

queue = deque()
for i in range(h):
    for j in range(w):
        if field[i][j] == "#":
            queue.append([i, j])

while len(queue) > 0:
    y, x = queue.popleft()
    for k in range(4):
        nx = x + dx[k]
        ny = y + dy[k]
        if 0 <= ny < h and 0 <= nx < w:
            if field[ny][nx] == ".":
                mark[ny][nx] = mark[y][x] + 1
                queue.append([ny, nx])
                field[ny][nx] = "#"

ans=0

for i in mark:
    ans = max(ans, max(i))

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

from heapq import heappop, heappush, heapify
N, M = map(int, input().split())
A = list(map(int, input().split()))
BC = []
for _ in range(M):
    B, C = map(int, input().split())
    BC.append((B, C))
heapify(A)
BC = sorted(BC, key = lambda x: -x[1])

for b, c in BC:
    for j in range(b):
        a = heappop(A)
        if a < c:
            heappush(A, c)
        else:
            heappush(A, a)

print(sum(A))

### FIXED CODE ###

from heapq import heappop, heappush, heapify
N, M = map(int, input().split())
A = list(map(int, input().split()))
BC = []
for _ in range(M):
    B, C = map(int, input().split())
    BC.append((B, C))
heapify(A)
BC = sorted(BC, key = lambda x: -x[1])

for b, c in BC:
    for j in range(b):
        a = heappop(A)
        if a < c:
            heappush(A, c)
        else:
            heappush(A, a)
            break

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

import heapq as hq

mod = 10**9+7

def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
def coco():
    n = onem()

    a = l()

    b = l()

    t = []

    for i in range(n):
        if b[i] != a[i]:
            hq.heappush(t,[-b[i],i])
    co = 0
    while t:
        k = hq.heappop(t)
        k = [-k[0],k[1]]
        if k[1] == 0:
            ppp = (k[0]-a[k[1]]) // (b[-1] + b[1])
            if ppp == 0:
                return -1
                
            co += ppp
            k[0] = (k[0]-a[k[1]]) % (b[-1] + b[1]) + a[k[1]]
        elif k[1] == n-1:
            ppp = (k[0]-a[k[1]]) // (b[-2] + b[0])
            if ppp == 0:
                return -1
            co += ppp
            k[0] = (k[0]-a[k[1]]) % (b[-2] + b[0]) + a[k[1]]
        else:
            ppp = (k[0]-a[k[1]]) // (b[k[1]+1] + b[k[1]-1])
            if ppp == 0:
                return -1
            co += ppp
            k[0] = (k[0]-a[k[1]]) % (b[k[1]+1] + b[k[1]-1]) + a[k[1]]
        b[k[1]] = k[0]
        if b[k[1]] != a[k[1]]:
            hq.heappush(t,[-b[k[1]],k[1]])
    return co

print(coco())


### FIXED CODE ###

import heapq as hq
mod = 10**9+7
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())

def onon():
    n = onem()

    a = l()

    b = l()

    t = []

    for i in range(n):
        if b[i] != a[i]:
            hq.heappush(t,(-b[i],i))
    co = 0
    while t:
        k = hq.heappop(t)
        k = (-k[0],k[1])
        q,w = divmod(k[0] - a[k[1]], b[(k[1] - 1) % n] + b[(k[1] + 1) % n])
        co += q
        if q == 0:
            return -1
        w = a[k[1]] + w
        b[k[1]] = w
        if b[k[1]] != a[k[1]]:
            hq.heappush(t,(-w,k[1]))
    return co
print(onon())
### BUGGY CODE ###

from collections import Counter
n = int(input())
st = input()
l = []
stc = Counter(st)
ma = [Counter(st[:0])["W"] + Counter(st[1:])["E"]]
previous = st[0]
for i in range(1,n):
    temp = ma[::-1][0]
    if(previous == "W"):
        temp+=1
    previous = st[i]
    if(st[i] == "E"):
        temp-=1
    ma.append(temp)
print(min(ma))

### FIXED CODE ###

from collections import Counter
n = int(input())
st = input()
l = []
stc = Counter(st)
ma = [Counter(st[:0])["W"] + Counter(st[1:])["E"]]
previous = st[0]
for i in range(1,n):
    temp = ma[-1]
    if(previous == "W"):
        temp+=1
    previous = st[i]
    if(st[i] == "E"):
        temp-=1
    ma.append(temp)
print(sorted(ma)[0])
### BUGGY CODE ###

import math
n, k = map(int, input().strip().split())
A = list(map(int, input().strip().split()))

for _ in range(min(k,int(math.log(n,2)))):
    start=[0]*n
    end=[0]*n
    
    for i in range(n):
        start[max(0,i-A[i])]+=1
        end[min(n-1,i+A[i])]+=1
    if start[0]==n:
        break
    # update ans
    cnt=0
    for i in range(n):
        cnt+=start[i]
        A[i]=cnt
        cnt-=end[i]

print(*A)

### FIXED CODE ###

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

def main():
    n, k = map(int, input().split())
    A = [*map(int, input().split())]
    
    # for _ in range(min(k,int(math.log(n,2)))):
    
    for _ in "_"*k:
        b=[0]*(n)
        
        for i,v in enumerate(A):
            if i>v:
            # b[max(0,i-v)]+=1
                b[i-v]+=1
            else:
                b[0]+=1
            j=i-~v
            # if i+v+1<n:
            #     b[i+v+1]-=1
            if j<n:
                b[j]-=1
        
        # update ans
        # cnt=0
        # for i in range(1,n):
        #     b[i]+=b[i-1]
        A=[*accumulate(b)]
        
        if min(A)==n:
            break
    print(" ".join(map(str,A)))

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

###### Importing Libraries ######
import math
import operator as op
from functools import reduce
from fractions import Fraction as frac
#################################
##### User defined function #####

############ NCR ###############
def ncr(n, r):
    r = min(r, n-r)
    numer = reduce(op.mul, range(n, n-r, -1), 1)
    denom = reduce(op.mul, range(1, r+1), 1)
    return numer / denom
    
############ READ ###############
def rd(p):
    if(p==0):
        return input()
    if(p==1):
        return int(input())
    if(p==2):
        return map(int,input().split())
    if(p==3):
        return list(map(int,input().split()))


############ DSU ###############
global par
par=[-1 for i in range(100001)]
# t=rd(1)
def find(u):
    if(par[u]<0):
        return u
    else:
        return find(par[u])
def uni(x,y):
    u=find(x)
    v=find(y)
    if u==v:
        return
    if(par[u]<par[v]):
        par[u]+=par[v]
        par[v]=u
    else:    
        par[v]+=par[u]
        par[u]=v
################################        
        

t=1
for term in range(1,t+1):
    h,n=rd(2)
    P=[rd(3) for i in range(n)]
    x=max(a for a,b in P)
    DP=[0 for i in range(h+x)]
    for i in range(1,h+x):
        DP[i]=min(DP[max(i-a,0)]+b for a,b in P)
    print(DP[h])
    
    
    
    
    
    
    
    
    
    
    
    

### FIXED CODE ###

###### Importing Libraries ######
import math
import operator as op
from functools import reduce
from fractions import Fraction as frac
#################################
##### User defined function #####

############ NCR ###############
def ncr(n, r):
    r = min(r, n-r)
    numer = reduce(op.mul, range(n, n-r, -1), 1)
    denom = reduce(op.mul, range(1, r+1), 1)
    return numer / denom
    
############ READ ###############
def rd(p):
    if(p==0):
        return input()
    if(p==1):
        return int(input())
    if(p==2):
        return map(int,input().split())
    if(p==3):
        return list(map(int,input().split()))


############ DSU ###############
global par
# par=[-1 for i in range(100001)]
# t=rd(1)
def find(u):
    if(par[u]<0):
        return u
    else:
        return find(par[u])
def uni(x,y):
    u=find(x)
    v=find(y)
    if u==v:
        return
    if(par[u]<par[v]):
        par[u]+=par[v]
        par[v]=u
    else:    
        par[v]+=par[u]
        par[u]=v
################################        
        

t=1
for term in range(1,t+1):
    h,n=rd(2)
    P=[list(map(int,input().split())) for i in range(n)]
    x=max(a for a,b in P)
    DP=[0]*(h+x)
    for i in range(1,h+x):
        DP[i]=min(DP[i-a]+b for a,b in P)
    print(DP[h])
### BUGGY CODE ###

N,K=map(int,input().split())
h=list(map(int,input().split()))
DP=[float('inf')]*N
DP[0]=0
for i in range(1,N):
  j=1
  while j<=K and j<=i:
    DP[i]=min(DP[i],abs(h[i]-h[i-j])+DP[i-j])
    j+=1
print(DP[-1])




### FIXED CODE ###

def main():
  #import sys
  #input = sys.stdin.readline
  N,K=map(int,input().split())
  h=list(map(int,input().split()))
  DP=[0]*N
  DP[0]=0
  for i in range(1,N):
  #j=1
  #while j<=K and j<=i:
  #  DP[i]=min(DP[i],abs(h[i]-h[i-j])+DP[i-j])
  #for j in range(max(0, i-K),i):
    #DP[i]=min(DP[i],abs(h[i]-h[j])+DP[j])
    r=max(0, i-K)
    DP[i]=min([abs(h[i]-h[j])+DP[j] for j in range(r,i)])
  print(DP[-1])
if __name__ == '__main__':
  main()
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**9)

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

ans = 0


def shouka(s: str, pa, pb, total):
    global ans
    if s == "a":
        total += a[pa]
        if total > k:
            ans = max(ans, pa + pb)
            return
        pa += 1
    else:
        total += b[pb]
        if total > k:
            ans = max(ans, pa + pb)
            return
        pb += 1
    if pa < n:
        shouka("a", pa, pb, total)
    if pb < m:
        shouka("b", pa, pb, total)

    ans = max(ans, pa+pb)


shouka("a", 0, 0, 0)
shouka("b", 0, 0, 0)
print(ans)


### FIXED CODE ###

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

a, b = [0], [0]

for i in range(n):
    a.append(a[i]+A[i])

for i in range(m):
    b.append(b[i]+B[i])

ptr = m
ans = 0

for i in range(n + 1):
    if a[i] > k:
        break
    while a[i] + b[ptr] > k:
        ptr -= 1
    ans = max(ans, i + ptr)

print(ans)