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

import sys
I = lambda:map(int,sys.stdin.readline().split())
pr = lambda x:sys.stdout.write(f'{x}\n')
sys.setrecursionlimit(2000000001)
ab = abs
n = k = ar = dp = 0

def solve(x):
	global n,k,ar,dp
	if x>=n-2: return dp[x]
	if dp[x] != -1: return dp[x]
	m = 1e9
	for i in range(x+1,min(n,x+k+1)):
		t = ab(ar[x]-ar[i])+solve(i)
		m = t if t<m else m
	dp[x] = m
	# pr(f'{x} => {dp[x]}')
	return dp[x]

def main():
	global n,ar,k,dp
	n,k, ar = *I(), [*I()]
	dp = [-1]*(n-2) + [ab(ar[-2]-ar[-1]),0]
	# pr((n,k,ar,dp))
	pr(solve(0))

main()


### FIXED CODE ###

import sys
from functools import reduce
sys.setrecursionlimit(2000000001)

def solve(n,k,ar,dp,x):
	ab = abs; mn = min
	if x>=n-2: return dp[x]
	if not dp[x] is -1: return dp[x]
	# t = [ for i in range(x+1,mn(n,x+k+1))]
	t = map(lambda i:ab(ar[x]-ar[i])+solve(n,k,ar,dp,i), range(x+1,mn(n,x+k+1)))
	dp[x] = reduce(lambda a,b : a if a < b else b,t)
	return dp[x]

def main():
	I = lambda:map(int,sys.stdin.readline().split())
	pr = lambda x:sys.stdout.write(f'{x}\n')
	n,k, ar = *I(), [*I()]
	dp = [-1]*(n-2) + [abs(ar[-2]-ar[-1]),0]
	pr(solve(n,k,ar,dp,0))

main()
### BUGGY CODE ###

n, k = map(int, input().split())
a = [0] + list(map(int, input().split()))
b = [1]
c = a[1]
d = 0
e=1
length = 0
first = 0
ans = 0


while c not in b:
    b += [c]
    c = a[c]
    d = c
    e+=1

if d != 0:
    length = e - b.index(d)
    first = b.index(d)
if k <= first:
    ans = b[k]
elif d == 0:
    ans = 1
else:
    ans = b[(k - first) % length + first]
print(ans)


### FIXED CODE ###

n, k = map(int, input().split())
a = [0] + list(map(int, input().split()))
t = [0 for i in range(n+1)]
b = [1]
c = a[1]
d = 0
e=1
length = 0
first = 0
ans = 0


while t[d] < 1:
    t[d]=e
    b += [c]
    c = a[c]
    d = c
    e+=1

if d != 0:
    length = e - t[d]
    first = b.index(d)
if k <= first:
    ans = b[k]
elif d == 0:
    ans = 1
else:
    ans = b[(k - first) % length + first]
print(ans)
### BUGGY CODE ###

def solve():
    N = int(input())
    Ass = [tuple(map(lambda x: int(x)-1, input().split())) for _ in range(N)]

    games = []
    for i in range(N):
        for j in range(i+1, N):
            games.append((i, j))
    adjL = dict([(game, []) for game in games])

    indegs = dict([(game, 0) for game in games])
    for i, As in enumerate(Ass):
        for j in range(len(As)-1):
            p1, p2, p3, p4 = i, As[j], i, As[j+1]
            if p1 > p2:
                p1, p2 = p2, p1
            if p3 > p4:
                p3, p4 = p4, p3
            adjL[(p1, p2)].append((p3, p4))
            indegs[(p3, p4)] += 1

    gameTodays = set()
    for game in games:
        if indegs[game] == 0:
            gameTodays.add(game)

    ans = 0
    numDone = 0
    while gameTodays:
        gameTomorrows = set()
        for game in gameTodays:
            numDone += 1
            for game2 in adjL[game]:
                indegs[game2] -= 1
                if indegs[game2] == 0:
                    gameTomorrows.add(game2)
        ans += 1
        gameTodays = gameTomorrows

    if numDone == N*(N-1)//2:
        print(ans)
    else:
        print(-1)

solve()


### FIXED CODE ###

def solve():
    N = int(input())
    Ass = []
    for _ in range(N):
        As = list(map(lambda x: int(x)-1, input().split()))
        Ass.append(As+[N])

    games = []
    numReadyss = [[0]*(N) for _ in range(N)]
    iAs = [0] * N
    for i in range(N):
        j = Ass[i][iAs[i]]
        if j > i: i, j = j, i
        numReadyss[i][j] += 1
        if numReadyss[i][j] >= 2:
            games.append((i, j))
    ans = 1
    numOK = 0
    while True:
        if not games:
            print(-1)
            return
        game2s = []
        for i, j in games:
            iAs[i] += 1
            i2 = Ass[i][iAs[i]]
            if i2 == N:
                numOK += 1
            else:
                if i2 > i: i, i2 = i2, i
                numReadyss[i][i2] += 1
                if numReadyss[i][i2] >= 2:
                    game2s.append((i, i2))
            iAs[j] += 1
            j2 = Ass[j][iAs[j]]
            if j2 == N:
                numOK += 1
            else:
                if j2 > j: j, j2 = j2, j
                numReadyss[j][j2] += 1
                if numReadyss[j][j2] >= 2:
                    game2s.append((j, j2))
        if numOK >= N:
            print(ans)
            return
        ans += 1
        games = game2s


solve()
### BUGGY CODE ###

from collections import deque
INF = int(1e9) + 7
h, w = map(int, input().split())
s = [list(input()) for i in range(h)]
d = [[INF] * w for i in range(h)]
dx = [1,0]
dy = [0,1]
if s[0][0] == '#':
    d[0][0] = 1
else:
    d[0][0] = 0
que = deque([(0, 0)])

while len(que) != 0:
    val = que.popleft()
    for i in range(2):
        nx = val[0] + dx[i]
        ny = (val[1] + dy[i])
        if nx < w and ny < h:

            que.append((nx, ny))
            if (s[nx][ny] == '#') and (d[nx][ny] > d[val[0]][val[1]]):
                d[nx][ny] = d[val[0]][val[1]] + 1
            elif s[nx][ny] != '#' and d[nx][ny] < d[val[0]][val[1]]:
                d[nx][ny] = d[nx][ny]

            else:
                d[nx][ny] = d[val[0]][val[1]]
print(d[h-1][w-1])

### FIXED CODE ###

INF = int(1e9) + 7
h, w = map(int, input().split())
s = []
for i in range(h):
    s.append(list(input()))

dp = [[INF] * w for i in range(h)]
if s[0][0] == '#':
    dp[0][0] = 1
else:
    dp[0][0] = 0
#print(dp)

for i in range(h):
    for j in range(w):
        if i == 0 and j == 0:
            continue
        val1 = dp[i-1][j]
        if s[i][j] == '#' and s[i-1][j] == '.':
            val1 += 1
        val2 = dp[i][j-1]
        if s[i][j] == '#' and s[i][j-1] == '.':
            val2 += 1
        dp[i][j] = min(val1, val2)
        #print(i, j,val1, val2)
print(dp[h-1][w-1])
#print(dp)
### BUGGY CODE ###


import sys
input = sys.stdin.readline

def main():
  N = int(input())
  X = input()

  if N == 1:
    if X.count("1"):
      print(0)
    else:
      print(1)
    return True

  base_1_count = X.count("1")
  if base_1_count == 0:
    for _ in range(N):
      print(1)
    return True

  X_int = int(X, 2)
  X_int_p = X_int%(base_1_count + 1)

  # RE 対策
  if base_1_count == 1:
    for i in range(N):
      if X[i] == "1":
        print(0)
      else:
        if i == N - 1:
          Xi = X_int_p + 1
        else:
          Xi = X_int_p
        count = 1
        while Xi != 0:
          Xi %= bin(Xi).count("1")
          count += 1
        print(count)
    return True

  X_int_m = X_int%(base_1_count - 1)
  for i in range(N):
    # 初期値計算を高速にやる
    if X[i] == "1":
      temp_1_count = base_1_count-1
      pow_2 = 2**(N-i-1)%(base_1_count-1)
      if X_int_m <= pow_2:
        Xi = X_int_m - pow_2 + base_1_count-1
      else:
        Xi = X_int_m - pow_2
    else:
      temp_1_count = base_1_count+1
      Xi = X_int_p + 2**(N-i-1)%(base_1_count+1)
      while Xi >= base_1_count+1:
        Xi %= base_1_count+1

    # print("1_c={0}".format(temp_1_count))
    if temp_1_count == Xi:
      print(1)
      continue

    count = 1
    while Xi != 0:
      num_of_1 = bin(Xi).count("1")
      Xi %= num_of_1
      count += 1
    print(count)
if __name__ == '__main__':
    main()

### FIXED CODE ###

def resolve():
  N = int(input())
  X = input()

  if N == 1:
    if X.count("1"):
      print(0)
    else:
      print(1)
    return True

  base_1_count = X.count("1")
  if base_1_count == 0:
    for _ in range(N):
      print(1)
    return True

  X_int = int(X, 2)
  X_int_p = X_int%(base_1_count + 1)

  # RE 対策
  if base_1_count == 1:
    for i in range(N):
      if X[i] == "1":
        print(0)
      else:
        if i == N - 1:
          Xi = X_int_p + 1
        else:
          Xi = X_int_p
        count = 1
        while Xi != 0:
          Xi %= bin(Xi).count("1")
          count += 1
        print(count)
    return True

  X_int_m = X_int%(base_1_count - 1)
  for i in range(N):
    # 初期値計算を高速にやる
    if X[i] == "1":
      temp_1_count = base_1_count-1
      pow_2 = pow(2, N-i-1, base_1_count-1)
      if X_int_m <= pow_2:
        Xi = X_int_m - pow_2 + base_1_count-1
      else:
        Xi = X_int_m - pow_2
    else:
      temp_1_count = base_1_count+1
      Xi = X_int_p + pow(2, N-i-1, base_1_count+1)
      while Xi >= base_1_count+1:
        Xi %= base_1_count+1

    # print("1_c={0}".format(temp_1_count))
    if temp_1_count == Xi:
      print(1)
      continue

    count = 1
    while Xi != 0:
      num_of_1 = bin(Xi).count("1")
      Xi %= num_of_1
      count += 1
    print(count)

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

n, k = map(int, input().split())
a = list(map(int, input().split()))
f = list(map(int, input().split()))
a.sort(reverse=True)
f.sort()
m = [i * j for i, j in zip(a, f)]
for i in range(k):
    l = m.index(max(m))
    a[l] -= 1
    m[l] = a[l] * f[l]
    if max(m) <= 0:
        print(0)
        break
else:
    print(max(m))



### FIXED CODE ###

import math
def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    f = list(map(int, input().split()))
    a.sort(reverse=True)
    f.sort()
    hi = a[0] * f[-1]
    lo = 0
    def caneat(m):
        t = 0
        for i, j in zip(a, f):
            if i * j > m:
                t += math.ceil((i*j - m)/j)
            if t > k:
                return False
        return True
    while hi != lo:
        m = (hi + lo) // 2
        if caneat(m):
            hi = m
        else:
            lo = m + 1
    return hi
print(main())
### BUGGY 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)

    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 = []

    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 idx < Q and i == Query[idx][1]:
            (le, ri, j) = Query[idx]
            ans.append((j, sum(bit, ri) - sum(bit, le-1)))
            idx += 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 ###

def n_gram(target,n):
    return [int(target[idx:idx + n]) for idx in range(len(target) - n + 1)]

count = 0
s = input()
n = 4
num_list = []
while n <= len(s):
    num_list.extend(n_gram(s,n))
    n += 1

for num in num_list:
    if num % 2019 == 0:
        count += 1
print(count)

### FIXED CODE ###

s = input()[::-1]

count = [0]*2019
count[0] = 1  # そもそもあまりが0ってことは2019の倍数確定なので

num, d = 0, 1  # 初期化

for char in s:
    num += int(char)*d
    num %= 2019
    d *= 10
    d %= 2019
    count[num] += 1  # 2019で割ったあまりをキーとして値を追加していく

ans = 0
for c in count:
    ans += c*(c-1)//2
print(ans)
### BUGGY CODE ###

s=input()
q=int(input())
n=0
for i in range(q):
    l=input()
    if l[0]=='1':
        n+=1
    else:
        if (l[2]=='1' and n%2==0) or (l[2]=='2' and n%2==1):
            s=l[4]+s
        else:
            s=s+l[4]
if n%2==0:
    print(s)
else:
    print(s[::-1])


### FIXED CODE ###

from collections import deque
s=input()
q=int(input())
n=0
que=deque(s)
for i in range(q):
    l=input()
    if l[0]=='1':
        n+=1
    else:
        if (l[2]=='1' and n%2==0) or (l[2]=='2' and n%2==1):
            que.appendleft(l[4])
        else:
            que.append(l[4])

ans=''.join(que)
if n%2==0:
    print(ans)
else:
    print(ans[::-1])
### BUGGY CODE ###

t=int(input())
for _ in range(t):
    a,b,c,d=map(int,input().split())
    e=b*(max((a-c)//b,1))
    a-=e
    while a>c:
        a-=b
    if a<0:
        print('No')
        continue
    if d<b:
        print('No')
        continue
    if c<=b and d>b:
        """
        while a<=c:
            a+=(d-b)
        """
        a+=(d-b)*(min(0,c//(d-b)-10000))
        while a<=c:
            a+=(d-b)
        while a-(d-b)>c:
            a-=(d-b)
        if a<b:
            print('No')
            continue
    print('Yes')

### FIXED CODE ###

from fractions import*
_,*t=open(0)
for t in t:
  a,b,c,d=map(int,t.split())
  g=gcd(b,d)
  print('YNeos'[b>min(a,d)or b-g+a%g>c::2])
### BUGGY CODE ###

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

mod = 10 ** 9 + 7
ans = 0
b = [0] * len(a)

for i in range(61):
    for j in range(n):
        b[j] = (a[j] >> i) & 1
    x = len(b) - sum(b)
    y = n - x
    z = x * y
    z *= 2 ** i
    z %= mod
    ans += z
ans %= mod

print(ans)


### FIXED CODE ###

import numpy as np
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

n = int(readline())
a = np.array(read().split(), np.int64)

mod = 10 ** 9 + 7
ans = 0

for i in range(61):
    b = a >> i & 1
    x = np.count_nonzero(b)
    y = n - x
    z = x * y
    z *= 2 ** i
    z %= mod
    ans += z
ans %= mod

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

import sys
input = sys.stdin.readline
def main():
    N, M = map(int, input().split())
    # C = [list(map(int, input().split())) for i in range(N)]
    V, W = [0]*N, [0]*N
    for i in range(N):
        W[i], V[i] = map(int, input().split())
    dp = [[0]*(M+1) for i in range(N+1)]
    # print(dp)
    # print(W)
    
    for i in range(N):
        for w in range(M+1):
            if w - W[i] >= 0:
               dp[i+1][w] = max(dp[i+1][w], dp[i][w-W[i]] + V[i]) 
            dp[i+1][w] = max(dp[i+1][w], dp[i][w])
    print(dp[N][M])    


if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
input = sys.stdin.readline
def main():
    N, M = map(int, input().split())
    # C = [list(map(int, input().split())) for i in range(N)]
    V, W = [0]*N, [0]*N
    for i in range(N):
        W[i], V[i] = map(int, input().split())
    dp = [[0]*(M+1) for i in range(N+1)]
    # print(dp)
    # print(W)
    
    for i in range(N):
        for w in range(M+1):
            if w - W[i] >= 0:
               dp[i+1][w] = max(dp[i+1][w], dp[i][w-W[i]] + V[i]) 
            dp[i+1][w] = max(dp[i+1][w], dp[i][w])
    print(dp[N][M])    


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

from collections import defaultdict
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
AtoZ = [chr(i) for i in range(65,65+26)]
atoz = [chr(i) for i in range(97,97+26)]

def inpl(): return list(map(int, input().split()))
def inpl_s(): return list(input().split())

N,K = inpl()
xys = []
xx = []
yy = []
ans = INF

for i in range(N):
	x,y = inpl()
	xys.append([x,y])

xys.sort()
for x,y in xys:
	xx.append(x)
	yy.append(y)



for i1 in range(N):
	for j1 in range(N):
		for i2 in range(i1+1,N):
			for j2 in range(j1+1,N):
				x1,x2 = xx[i1],xx[i2]
				y1,y2 = yy[j1],yy[j2]
				if y1 > y2:
					y1,y2 = y2,y1
				tmp = 0
				for ix in range(i1,i2+1):
					y = xys[ix][1]
					if y1 <= y <= y2:
						tmp += 1
				if tmp == K:
					S = abs(x1-x2)*abs(y1-y2)
					ans = min(ans,S)

print(ans)

### FIXED CODE ###

from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())

N,K = inpl()
xys = []
xx = set()
for i in range(N):
    x,y = inpl()
    xys.append([x,y])
    xx.add(x)

ans = INF
xx = sorted(list(xx))
Lx = len(xx)
xys.sort(key = lambda x: x[1])
for i1 in range(Lx):
    x1 = xx[i1]
    for i2 in range(i1,Lx):
        x2 = xx[i2]
        yy = []
        for x,y in xys:
            if x1 <= x <= x2:
                yy.append(y)
        Ly = len(yy)
        if Ly < K:
            continue
        else:
            for l in range(Ly-K+1):
                r = l+K-1
                ans = min((yy[r]-yy[l])*(x2-x1),ans)

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

import math

a, b = map(int, input().split())
n = min(a, b)
def primes(x):
    if x < 2: return []

    primes = [i for i in range(x)]
    primes[1] = 0 # 1は素数ではない

    # エラトステネスのふるい
    for prime in primes:
        if prime > math.sqrt(x): break
        if prime == 0: continue
        for non_prime in range(2 * prime, x, prime): primes[non_prime] = 0

    return [prime for prime in primes if prime != 0]
l = primes(n)
count = 1
for p in l:
    if a % p == 0 and b % p == 0:
        count += 1
print(count)

### FIXED CODE ###

a, b = map(int, input().split())

def gcd(a, b):
    while b > 0:
        a, b = b, a%b
    return a
n = gcd(a, b)

def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

ans = set(prime_factorize(n))
print(len(ans)+1)
### BUGGY CODE ###

# https://atcoder.jp/contests/abc074/tasks/arc083_b

import sys
input = sys.stdin.buffer.readline

def floyd_warshall(V, dist):                                               # 動的計画法。頂点 k まで経由することが可能な場合の最短距離という部分問題を考えて、k = 0 から漸化式的に計算する
    res = 0
    for i in range(V):
        for j in range(i+1,V):
            flg = 0
            for k in range(V):
                if k==i or k==j:
                    continue
                if dist[i][j] > dist[i][k] + dist[k][j]:
                    return -1
                if dist[i][j] < dist[i][k] + dist[k][j]:
                    flg += 1
                if flg == V-2:
                    res += dist[i][j]
    return res

N = int(input())

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

if N ==2:
    print(dist[0][1])
else:
    print(floyd_warshall(N, dist))

### FIXED CODE ###

# https://atcoder.jp/contests/abc074/tasks/arc083_b

import sys
input = sys.stdin.buffer.readline

def floyd_warshall(V, dist):                                               # 動的計画法。頂点 k まで経由することが可能な場合の最短距離という部分問題を考えて、k = 0 から漸化式的に計算する
    res = 0
    for i in range(V):
        for j in range(i+1,V):
            flg = 0
            for k in range(V):
                if k==i or k==j:
                    continue
                if dist[i][j] > dist[i][k] + dist[k][j]:
                    return -1
                if dist[i][j] < dist[i][k] + dist[k][j]:
                    flg += 1
                if flg == V-2:
                    res += dist[i][j]
    return res

N = int(input())

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

if N ==2:
    print(dist[0][1])
else:
    print(floyd_warshall(N, dist))
### BUGGY CODE ###

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

import numpy as np

"""
それぞれの隣接2列ごとに、可能な摩擦の最小値を実現する → 小問題に分割。
"""

H,W = map(int,input().split())
C = np.array([list(input().rstrip()) for _ in range(H)])

def score_between(col1,col2):
    col1 = np.concatenate([['*'],col1])
    col2 = np.concatenate([['#'],col2])
    # まず、その瞬間のスコアを求める
    # L+R,R-L+H
    dp_1 = np.zeros((H+H+1,H+H+1),dtype=np.int64)
    for n in range(H+H+1):
        # R-L+H=n
        if n <= H:
            R0,L0 = 1,H-n+1
            R1,L1 = n,H
        else:
            L0,R0 = 1,n-H+1
            L1,R1 = H+H-n,H
        dp_1[n][L0+R0:L1+R1+2:2] = (col1[L0:L1+1] == col2[R0:R1+1])
        np.cumsum(dp_1[n],out=dp_1[n])
    
    INF = 10**18
    # R-L+H -> min cost
    dp = np.full(H+H+1,INF,dtype=np.int64)
    dp[H] = 0
    for n in range(1,H+H+1):
        # n個目を置く
        prev = dp
        dp = np.full(H+H+1,INF,dtype=np.int64)
        dp[1:] = np.minimum(dp[1:],prev[:-1])
        dp[:-1] = np.minimum(dp[:-1],prev[1:])
        dp += dp_1[:,n]
    return dp[H]

answer = sum(score_between(C[:,n],C[:,n+1]) for n in range(W-1))
print(answer)

### FIXED CODE ###

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

import numpy as np

"""
それぞれの隣接2列ごとに、可能な摩擦の最小値を実現する → 小問題に分割。
"""

buffer = sys.stdin.buffer
H,W = map(int,buffer.readline().split())
C = np.frombuffer(buffer.read(),dtype='S1').reshape(H,-1)[:,:W].T

dp_1 = np.zeros((W-1,H+H+1,H+1),dtype=np.int64)
for r in range(H):
    dp_1[:,r+2:r+H+2,r+1] = (C[:-1] == C[1:,r][:,None])

INF = 10**18
# R-L+H -> min cost
dp = np.full((W-1,H+1),INF,dtype=np.int64)
dp[:,0] = 0
for n in range(1,H+H+1):
    if n >= 2:
        dp_1[:,n,1:] += dp_1[:,n-2,:-1]
    # n個目を置く
    prev = dp
    dp = np.full((W-1,H+1),INF,dtype=np.int64)
    dp[:,1:] = np.minimum(dp[:,1:],prev[:,:-1])
    dp[:,:] = np.minimum(dp[:,:],prev[:,:])
    dp += dp_1[:,n,:]
answer = dp[:,H].sum()
print(answer)
### BUGGY CODE ###

N, M = map(int, input().split())
LR = [None]*M

for i in range(M):
    l, r = map(int, input().split())
    if i==0:
        ans = set(range(l, r+1))
    else:
        ans = ans & set(range(l, r+1))

print(min(len(ans), N))

### FIXED CODE ###

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

for i in range(M):
    l, r = map(int, input().split())
    
    if i==0:
        left = l
        right = r

    else:
        if l>left:
            left = l
        if r<right:
            right = r

print(0) if left>right else print(right-left+1)
### BUGGY CODE ###

import math

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

min = 0
for x in range(1, N+1):
    ans = math.floor(A*x/B) - A*math.floor(x/B)
    if min < ans:
        min = ans

print(min)

### FIXED CODE ###

# -*- coding: utf-8 -*-
A,B,N = map(int, input().split())
 
def function(x):
  return (A*x)//B-A*(x//B)
 
if B-1<=N:
  print(function(B-1))
else:
  print(function(N))