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

#2分探索
#md/cで交点が定まらない時の対案
n,k = map(int, input().split( ))
m = [tuple(map(int, input().split( ))) for i in range(n)]
#そもそも設定はn枚すべて焼く必要はない
mx = 10**15
mn = 0
from math import sqrt
def solve(x1, y1, r1, x2, y2, r2):
    rr0 = (x2 - x1)**2 + (y2 - y1)**2
    xd = x2 - x1
    yd = y2 - y1
    rr1 = r1**2; rr2 = r2**2
    cv = (rr0 + rr1 - rr2)
    if max(r1,r2,sqrt(rr0))*2>r1+r2+sqrt(rr0):
        return (x1,y1),(x2,y2)
    sv = sqrt(4*rr0*rr1 - cv**2)
    return (
        (x1 + (cv*xd - sv*yd)/(2.*rr0), y1 + (cv*yd + sv*xd)/(2.*rr0)),
        (x1 + (cv*xd + sv*yd)/(2.*rr0), y1 + (cv*yd - sv*xd)/(2.*rr0)),
    )

#flag で breakしてたのが煩雑すぎて追えていなかったらしい
while mx-mn>10**(-6) or mx-mn>10**(-7)*mx:#mx大きい時に安易に設定すると到達しない？
    md = (mx+mn)/2
    cnt = 0
    for i in range(n):##中心選ぶケースが抜けてる
        pi0,pi1 = m[i][0],m[i][1]
        tmp = 0
        for l in range(n):#kはすでに使っている変数
            if m[l][2]*sqrt(((pi0-m[l][0])**2) + ((pi1-m[l][1])**2))<=md+0.000000001:
                tmp += 1
        if cnt<tmp:
            cnt = tmp

    for i in range(n):
        for j in range(i+1,n):##range(i)だとi=0で止まって何もしない

            p = solve(m[i][0],m[i][1],md/m[i][2], m[j][0],m[j][1],md/m[j][2])

            for pi in p:
                tmp = 0
                for l in range(n):#kはすでに使っている変数
                    if (((pi[0]-m[l][0])**2) + ((pi[1]-m[l][1])**2))**(1/2)<=md/m[l][2]+0.000000001:##ここで誤差認めなかったせいらしい
                        tmp += 1
                if cnt<tmp:
                    cnt = tmp

    if cnt>=k:
        mx = md
    else:
        mn = md
print(mx)


### FIXED CODE ###

#2分探索
#md/cで交点が定まらない時の対案
n,k = map(int, input().split( ))
m = [tuple(map(int, input().split( ))) for i in range(n)]
#そもそも設定はn枚すべて焼く必要はない
mx = 10**15
mn = 0
from math import sqrt
def solve(x1, y1, r1, x2, y2, r2):
    rr0 = (x2 - x1)**2 + (y2 - y1)**2
    xd = x2 - x1
    yd = y2 - y1
    rr1 = r1**2; rr2 = r2**2
    cv = (rr0 + rr1 - rr2)
    if max(r1,r2,sqrt(rr0))*2>r1+r2+sqrt(rr0):
        return (x1,y1),(x2,y2)
    sv = sqrt(4*rr0*rr1 - cv**2)
    return (
        (x1 + (cv*xd - sv*yd)/(2.*rr0), y1 + (cv*yd + sv*xd)/(2.*rr0)),
        (x1 + (cv*xd + sv*yd)/(2.*rr0), y1 + (cv*yd - sv*xd)/(2.*rr0)),
    )

#flag で breakしてたのが煩雑すぎて追えていなかったらしい
while mx-mn>10**(-6) and mx-mn>10**(-7)*mx:#mx大きい時に安易に設定すると到達しない？
    md = (mx+mn)/2
    cnt = 0
    for i in range(n):##中心選ぶケースが抜けてる
        pi0,pi1 = m[i][0],m[i][1]
        tmp = 0
        for l in range(n):#kはすでに使っている変数
            if m[l][2]*sqrt(((pi0-m[l][0])**2) + ((pi1-m[l][1])**2))<=md+0.000000001:
                tmp += 1
        if cnt<tmp:
            cnt = tmp

    for i in range(n):
        for j in range(i+1,n):##range(i)だとi=0で止まって何もしない

            p = solve(m[i][0],m[i][1],md/m[i][2], m[j][0],m[j][1],md/m[j][2])

            for pi in p:
                tmp = 0
                for l in range(n):#kはすでに使っている変数
                    if (((pi[0]-m[l][0])**2) + ((pi[1]-m[l][1])**2))**(1/2)<=md/m[l][2]+0.000000001:##ここで誤差認めなかったせいらしい
                        tmp += 1
                if cnt<tmp:
                    cnt = tmp

    if cnt>=k:
        mx = md
    else:
        mn = md
print(mx)
### BUGGY CODE ###

import sys
import math
import fractions
import bisect
import queue
import heapq
import collections
import itertools
sys.setrecursionlimit(4100000)

MOD = int(1e9+7)
PI = 3.14159265358979323846264338327950288
INF = 1e18

'''
1行のint=====================================
N, K = map(int, input().split())
N, M = map(int, input().split())
A, B = map(int, input().split())

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

L, R = map(int, input().split())

1行のstring=================================
S, T = input().split()

1行の整数配列================================
P = list(map(int,input().split()))

A = list(map(int,input().split()))
B = list(map(int,input().split()))
C = list(map(int,input().split()))
D = list(map(int,input().split()))

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

T = list(map(int,input().split()))

改行あり整数==================================
X = []
Y = []
for i in range(N):
    x1,y1=[int(i) for i in input().split()]
    X.append(x1)
    Y.append(y1)

A = []
for i in range(N):
    a=int(input())
    A.append(a)

Pair = []
for i in range(N):
    x1,y1=[int(i) for i in input().split()]
    Pair.append((x1, y1))
    
2次元整数配列=====================================
A = []
for i in range(N):
    tmp = list(map(int,input().split()))
    A.append(tmp)


N行M列の初期化====================================
dp = [[VAL] * RETU for i in range(GYO)]

'''

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

common = 1
for i in range(len(A)):
    common = common * A[i] // math.gcd(common, A[i])

ans = 0
for i in range(len(A)):
    ans += common // A[i]
    ans %= MOD

print(ans)




### FIXED CODE ###

import sys
sys.setrecursionlimit(4100000)
import math




N = int(input())


import fractions
a = list(map(int, input().split()))
koubai = a[0]
small = []
for i in range(0, N//2):
    small.append(a[2*i + 1] * a[2*i] // fractions.gcd(a[2*i + 1], a[2*i]))

small.append(a[-1])
for i in range(len(small)):
    koubai = koubai * small[i] // fractions.gcd(koubai, small[i])


ans = int(0)
for i in range(N):
    ans += koubai // a[i]
    
ans %= 1000000007

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

import heapq
n, k = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
f = list(map(int, input().split()))
f.sort(reverse=True)

asum = sum(a)

def test(x):
    t = [min(a[i], x//f[i]) for i in range(n)]
    return asum - sum(t)


ng = -1
ok = 10**13
while abs(ok-ng)>1:
    mid = (ok+ng)//2
    if test(mid) <= k:
        ok = mid
    else:
        ng = mid

print(ok)

### FIXED CODE ###

import heapq
n, k = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
f = list(map(int, input().split()))
f.sort(reverse=True)

asum = sum(a)

def test(x):
    t = [min(a[i], x//f[i]) for i in range(n)]
    return asum - sum(t)


ng = -1
ok = 10**13
while abs(ok-ng)>1:
    mid = (ok+ng)//2
    if test(mid) <= k:
        ok = mid
    else:
        ng = mid

print(ok)
### BUGGY CODE ###

import numpy as np
A,B,Q=map(int,input().split())
s=[int(input()) for i in range(A)]
t=[int(input()) for i in range(B)]
x=[int(input()) for i in range(Q)]
s=np.array(s)
t=np.array(t)
x=np.array(x)
for X in x:
    l1=min(abs(X-t))
    if -l1 in X-t:
        l1=-l1
    l2=min(abs(X-s))
    if -l2 in X-s:
        l2=-l2
    print(min(min(abs(X-t))+min(abs(X-l1-s)),min(abs(X-s))+min(abs(X-l2-t))))



### FIXED CODE ###

import bisect
INF=10**18
A,B,Q=map(int,input().split())
s=[int(input()) for i in range(A)]
t=[int(input()) for i in range(B)]
s=[-INF]+s+[INF]
t=[-INF]+t+[INF]
for q in range(Q):
    X=int(input())
    t1=bisect.bisect_right(t,X)
    s1=bisect.bisect_right(s,X)
    res=INF
    for T in [t[t1],t[t1-1]]:
        for S in [s[s1],s[s1-1]]:
            ans1=abs(X-T)+abs(S-T)
            ans2=abs(X-S)+abs(S-T)
            res=min(res,ans1,ans2)
    print(res)
### BUGGY CODE ###

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

A = [[0]*W for i in range(H)]
data = [0]*(H*W+1)

for i in range(H):
    A[i] = list(map(int,input().split()))

for i in range(H):
    for j in range(W):
        data[A[i][j]] = [i,j]

Q = int(input())

L = [0] * Q
R = [0] * Q

for i in range(Q):
    L[i],R[i] = map(int,input().split())


for i in range(Q):
    ans = 0
    x = L[i]
    while x != R[i]:
        ans += abs(data[x+D][0]-data[x][0])
        ans += abs(data[x+D][1]-data[x][1])
        x += D
    print(ans)

### FIXED CODE ###

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

A = [[0]*W for i in range(H)]
data = [0]*(H*W+1)

for i in range(H):
    A[i] = list(map(int,input().split()))

for i in range(H):
    for j in range(W):
        data[A[i][j]] = [i,j]

Q = int(input())

L = [0] * Q
R = [0] * Q

for i in range(Q):
    L[i],R[i] = map(int,input().split())

X = [0]*(H*W+1)

for i in range(D):
    x = H*W-D-i
    count = 0
    while x > 0:
        count += abs(data[x][0]-data[x+D][0])+abs(data[x][1]-data[x+D][1])
        X[x] += count
        x -= D

for i in range(Q):
    print(X[L[i]]-X[R[i]])
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
d = {}
for ai in a:
  if not ai in d:
    d[ai] = a.count(ai)

cnt = 0
for key, value in d.items():
  if value > key:
    cnt = cnt + value - key
  elif key > value:
    cnt = cnt + value

print(cnt)
  

### FIXED CODE ###

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

d = {}
for ai in a:
  if ai in d:
    d[ai] = d[ai] + 1
  else:
    d[ai] = 1

cnt = 0
for key, value in d.items():
  if key > value:
    cnt = cnt + value
  elif key < value:
    cnt = cnt + value - key

print(cnt)
### BUGGY CODE ###

N = int(input())
a = []
b = 0

for i in range(N):
    a.append(int(input()))

for i in range(N):
    b = a[i]
    a[i] = 0
    print(max(a))
    a[i] = b


### FIXED CODE ###

N = int(input())
a = []
b = []
a_max = 0
a_second = 0

for i in range(N):
    a.append(int(input()))

b = a[:]
a.sort(reverse=True)

a_max = a[0]
a_second = a[1]

for i in range(N):
    if b[i] == a_max:
        print(a_second)
    else:
        print(a_max)
### BUGGY CODE ###

N=int(input())
alist=[0]+list(map(int,input().split()))

blist=[0]*(N+1)
for i in reversed(range(1,N+1)):
  blist[i]^=alist[i]
  for j in range(2,N+1):
    if i%j==0:
      blist[i//j]^=blist[i]
    
#print(blist)
answer=sum(blist)
print(answer)
if answer>0:
  print(" ".join(["1"]*answer))

### FIXED CODE ###

N=int(input())
alist=[0]+list(map(int,input().split()))
#print(alist)

blist=[0]*(N+1)
for i in reversed(range(1,N+1)):
  blist[i]=alist[i]
  for j in range(2*i,N+1,i):
    blist[i]+=blist[j]
  blist[i]%=2
  
#print(blist[1:])
answer_list=[i for i in range(1,N+1) if blist[i]==1]
print(len(answer_list))
print(*answer_list)
### BUGGY CODE ###

nkq = list(map(int, input().split()))
n, k, q = nkq[0], nkq[1], nkq[2]
attendees = dict()
for i in range(n):
    attendees[i] = k

attendees = [(i, k) for i in range(n)]

respondents = [int(input()) for i in range(q)]

for r in respondents:
    r_index = r - 1
    for a in attendees:
        i, p = a
        if i != r_index:
            attendees[i] = (i, p - 1)

for a in attendees:
    i, p = a
    if p > 0:
        print("Yes")
    else:
        print("No")


### FIXED CODE ###

nkq = list(map(int, input().split()))
n, k, q = nkq[0], nkq[1], nkq[2]
attendees = dict()
for i in range(n):
    attendees[i] = 0

respondents = [int(input()) for i in range(q)]

for r in respondents:
    r_index = r - 1
    attendees[r_index] += 1

for i, p in attendees.items():
    point = p + k - q
    if point > 0:
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

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

se = set()
dic = dict()
for i in range(N):
    if A[i] in se:
        dic[A[i]] += 1
    else:
        se.add(A[i])
        dic.update({A[i]: 1})

for i in range(N):
    result = 0
    for k in dic.keys():
        if A[i] == k:
            result += (dic[k]-1)*(dic[k]-2)//2
        else:
            result += (dic[k])*(dic[k]-1)//2
    print(result)


### FIXED CODE ###

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

se = set()
dic = dict()

for i in range(N):
    if A[i] in se:
        dic[A[i]] += 1
    else:
        se.add(A[i])
        dic.update({A[i]: 1})

c = 0
for k in dic.keys():
    c += (dic[k])*(dic[k]-1)//2

result = [0]*N
for i in range(N):
    result[i] = c - (dic[A[i]])*(dic[A[i]]-1)//2 + (dic[A[i]]-1)*(dic[A[i]]-2)//2

print("\n".join(list(map(str, result))))
### BUGGY CODE ###

import sys

sys.setrecursionlimit(10 ** 7)


def func(l, r, taro_turn):
    # [l,r]
    # return taro - jiro

    if l == r:
        return a[l] * (-1 if taro_turn is None else 1)

    if memo[l][r] is not None:
        return memo[l][r]

    if taro_turn is None:
        # jiro_turn
        res = min(func(l, r - 1, True) - a[r], func(l + 1, r, True) - a[l])
    else:
        # taro_turn
        res = max(func(l, r - 1, None) + a[r], func(l + 1, r, None) + a[l])

    memo[l][r] = res
    return res


n = int(input())
a = tuple(int(x) for x in input().split())

memo = [[None] * n for _ in range(n)]

print(func(0, n - 1, True))


### FIXED CODE ###

n = int(input())
a = tuple(int(x) for x in input().split())

memo = tuple([None] * n for _ in range(n))
for i, aa in enumerate(a):
    memo[i][i] = aa

for l in range(n - 1, -1, -1):
    for r in range(l, n):
        if memo[l][r] is None:
            memo[l][r] = max(a[r] - memo[l][r - 1], a[l] - memo[l + 1][r])

print(memo[0][n - 1])
### BUGGY CODE ###

N =int(input())
keihin =[]
ans = 0
for _ in range(N):
    S = input()
    if S in keihin:
        continue
    else:
        keihin.append(S)
        ans+=1

print(ans)

### FIXED CODE ###

N =int(input())
keihin ={}
ans = 0
for _ in range(N):
    S = input()   
    keihin[S] = 1


print(sum(keihin.values()))
### BUGGY CODE ###

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

saeki = []
maxsaeki = 0
ans = 0
maxringo = max(a)

for i in range(len(a)-1):
    if a[i] == maxringo:
        maxringo = max(a[i+1:])
    s = maxringo - a[i]
    if s == maxsaeki:
        ans += 1
    if s > maxsaeki:
        ans = 1
        maxsaeki = s

print(ans)

### FIXED CODE ###

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

ma = a[-1]
m = 1
maxsaeki = 0
ans = 0

for i in range(n-2,-1,-1):
    if a[i] > ma:
        ma = a[i]
        m = 1
    elif a[i] < ma:
        if (ma - a[i]) > maxsaeki:
            maxsaeki = ma-a[i]
            ans = 1
        elif (ma - a[i]) == maxsaeki:
            ans += 1

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

### ----------------
### ここから
### ----------------

import sys
from io import StringIO
import unittest

def yn(b):
    print("Yes" if b==1 else "No")
    return

def bin_search(arr,c):
    l = -1
    r = len(arr)
    while (r-l) > 1:
        m = l + (r-l)//2
        if arr[m] >= c:
            r = m
        else:
            l = m
    return l+1

def resolve():
    readline=sys.stdin.readline

    n=int(readline())
    arr=list(map(int, readline().rstrip().split()))
    arr.sort()
    ans=0
    for i in range(n-2):
        for j in range(i+1,n-1):
            c = arr[i] + arr[j]
            l = arr[j+1:]
            ans += bin_search(l,c)
    print(ans)
    return

if 'doTest' not in globals():
    resolve()
    sys.exit()

### ----------------
### ここまで 
### ----------------

### FIXED CODE ###

### ----------------
### ここから
### ----------------

import sys
from io import StringIO
import unittest

def yn(b):
    print("Yes" if b==1 else "No")
    return

def bin_search(arr,ls,c):
    l=ls-1
    r = len(arr)
    while (r-l) > 1:
        m = l + (r-l)//2
        if arr[m] >= c:
            r = m
        else:
            l = m
    return l-ls+1

def resolve():
    readline=sys.stdin.readline

    n=int(readline())
    arr=list(map(int, readline().rstrip().split()))
    arr.sort()
    ans=0
    for i in range(n-2):
        for j in range(i+1,n-1):
            c = arr[i] + arr[j]
            ans += bin_search(arr,j+1,c)
    print(ans)
    return

if 'doTest' not in globals():
    resolve()
    sys.exit()

### ----------------
### ここまで 
### ----------------
### BUGGY CODE ###

n = int(input())
tmp = 1
 
for i in range(1,10**10):
  if n%i == 0:
    if i <= n//i:
      tmp  = i
    else:
      break
  elif tmp == 1 and i >= n/i:
    break
    
   
    
      
print(tmp + (n//tmp) -2)

### FIXED CODE ###

n = int(input())
tmp = 1
 
for i in range(1,10**6+1):
  if n%i == 0 and i<= n//i:
    tmp = i
   
      
print(tmp + (n//tmp) -2)
### BUGGY CODE ###

n=int(input())
pw=1
e=10**9+7
for i in range(1,n+1):
    pw*=i
print(pw%e)

### FIXED CODE ###

import math
n=int(input())
pw=1
e=10**9+7
'''
for i in range(1,n+1):
    pw*=i
    print(i,pw)
'''
pw=math.factorial(n)
print(pw%e)
### BUGGY CODE ###

L, R= map(int, input().split())
ans = []
for i in range(L, R):
    for j in range(i+1, R+1):
        ans.append((i*j)%2019)
print(min(ans))

### FIXED CODE ###

import sys
L, R= map(int, input().split())
ans = []
for i in range(L, R):
    for j in range(i+1, R+1):
        if (i*j)%2019 == 0:
            print(0)
            sys.exit()
        else:
            ans.append((i*j)%2019)
print(min(ans))
### BUGGY CODE ###

n = int(input())
h = list(map(int, input().split()))
a = []
for i in range(n):
    ans = 0
    for j in range(i+1, n):
        if h[j-1]>=h[j]:
            ans+=1
        else:
            break
    a.append(ans)
    ans = 0
a.sort(reverse=True)
print(a[0])

### FIXED CODE ###

n = int(input())
h = list(map(int, input().split()))
a = [0]
ans = 0
for i in range(1,n):
    if h[i-1]>=h[i]:
        ans+=1
    else:
        a.append(ans)
        ans=0
    if i==n-1:
        a.append(ans)
a.sort(reverse=True)
print(a[0])
### BUGGY CODE ###

pnum, default, correct = map(int, input().split())
pep = [default]*pnum
a = list()
for i in range(correct):
    a.append(int(input()))
for i in a:
    for j in range(pnum):
        pep[j] -= 1
    pep[i-1] += 1
for i in pep:
    if i > 0:
        print("Yes")
    else:
        print("No")

### FIXED CODE ###

n, shoki, correct = map(int, input().split())
b = list()
for i in range(correct):
    b.append(int(input()))
a = [shoki]*n
a = [i-correct for i in a]
for i in b:
    a[i-1] += 1
for i in range(n):
    if a[i] <= 0:
        print("No")
    else:
        print("Yes")
### BUGGY CODE ###

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

b = 1
for j in range(K):
    b *= A[j]

for i in range(1, N-K+1):
    a = 1
    for j in range(K):
        a *= A[i+j]
    print('Yes' if a > b else 'No')
    b = a




### FIXED CODE ###

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

for i in range(1, N-K+1):
    print('Yes' if A[i - 1] < A[i+K - 1] else 'No')
### BUGGY CODE ###

N = int(input())
# = map(int, input().split())
P = list(map(int, input().split()))
# = [int(input()) for i in range(N)]
# = [list(map(int, input().split())) for i in range(N)]

count = 0

for i in range(N):
    if P[i] == 1:
        count += 1
        break
    if P[i] == min(P[:i+1]):
        count += 1

print(count)


### FIXED CODE ###

N = int(input())
# = map(int, input().split())
P = list(map(int, input().split()))
# = [int(input()) for i in range(N)]
# = [list(map(int, input().split())) for i in range(N)]

count = 0
minimum = 300000

for i in range(N):
    if P[i] == 1:
        count += 1
        break
    if P[i] < minimum:
        count += 1
        minimum = P[i]

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

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

cnt = 0
for i in range(N): #中段について 
        for j in range(N): #上段について
            for k in range(N): #下段について 
                if A[j] < B[i] < C[k]:
                    cnt += 1
print(cnt)

### FIXED CODE ###

from bisect import bisect_left, bisect

n=int(input())
la=sorted(list(map(int,input().split())))
lb=list(map(int,input().split()))
lc=sorted(list(map(int,input().split())))
ans=0
for i in lb:
    ans+=bisect_left(la,i)*(len(lc)-bisect(lc,i)) #iの挿入点つまりiより小さい値の数×(Cの総数-
print(ans)
### BUGGY CODE ###

n=int(input())
s=input()
sum=0
for k in range(n):
    for j in range(k):
        if s[j]!=s[k]:
            for i in range(j):
                if i!=2*j-k:
                    if s[i]!=s[j] and s[k]!=s[i] and j-i!=k-j:
                        sum=sum+1
print(sum)

### FIXED CODE ###

n=int(input())
s=input()
sum=0
r=int(s.count('R'))
g=int(s.count('G'))
b=int(s.count('B'))
for k in range(n):
    for j in range(k):
        i=2*j-k
        if i+1>0:
            if s[i]!=s[j] and s[j]!=s[k] and s[k]!=s[i]:
                sum=sum+1
print(r*g*b-sum)
### BUGGY CODE ###

import numpy as np
N, K=map(int, input().split())
P=np.array(list(map(int, input().split())))

best=0
bestP=np.array([0]*K)
for i in range(N-K+1):
  if P[i:i+K].sum()>best:
    best=P[i:i+K].sum()
    bestP=P[i:i+K]
    

print(((bestP+1)/2).sum())

### FIXED CODE ###

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

#n面サイコロの出る目の期待値
def n_mean(n):
  return 0.5*(n+1)

Pmean=list(map(lambda x: n_mean(x), P))
Psum=[0]*N
Psum[0]=Pmean[0]
for i in range(1,N):
  Psum[i]=Psum[i-1]+Pmean[i]
#print(Psum)
ans=0
for i in range(N-K+1):
  if i==0:
    ans=Psum[K-1]
  else:
    #1~6 
    ans=max(ans, (Psum[i+K-1]-Psum[i-1]))
  
print(ans)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
"""
Created on Tue Jan 21 16:49:00 2020

@author: matsui
"""

def cost(i,j):
    return abs(int(h[i])-int(h[j]))

N,K=map(int,input().split())
h=input().split()

dp=[0]*N
   
for i in range(1,N):
    mi=cost(i,i-1)+dp[i-1]
    for j in range(2,K+1):
        if i-j < 0 : break
        tmp=cost(i,i-j)+dp[i-j]
        if mi>tmp: mi=tmp
    dp[i]=mi
    
print(dp[N-1])

### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
Created on Tue Jan 21 16:49:00 2020

@author: matsui
"""



N,K=map(int,input().split())
h=[int(num) for num in input().split()]

dp=[0]*N
dp[1]=abs(h[0]-h[1])
   
def cost(h,N,K,dp):
    for i in range(2,N):
        dp[i]=min([abs(h[i]-h[j])+dp[j] for j in range(max(0, i-K), i)])
    return dp[-1]
    
print(cost(h,N,K,dp))
### BUGGY CODE ###

input()
a=list(map(int,input().split()))
m=max(a)
i,f=1,0
while i:
    for j in a:
        if (m*i)%j:break
        if j==a[-1]: f=1
    if f:break
    i+=1
print(m*i)

### FIXED CODE ###

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

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

input()
a=list(map(int,input().split()))
b=1
for i in a:
    b=lcm(b,i)
print(b)
### BUGGY CODE ###

n,k=map(int,input().split())
h=[int(l) for l in input().split()]
dp=[0,abs(h[0]-h[1])]
for i in range(2,n):
    ans=10**15
    num=i-k
    if num<0:
        num=-1
    else:
        num-=1
    for j in range(i-1,num,-1):
        ans=min(abs(h[i]-h[j])+dp[j],ans)
    dp.append(ans)
print(dp[n-1])


### FIXED CODE ###

from sys import stdin,stdout
n,k=map(int,stdin.readline().split())
h=[int(l) for l in stdin.readline().split()]
dp=[0,abs(h[0]-h[1])]
for i in range(2,n):
    ans=10**15
    num=i-k
    if num<0:
        num=-1
    else:
        num-=1
    for j in range(i-1,num,-1):
        ans=min(abs(h[i]-h[j])+dp[j],ans)
    dp.append(ans)
print(dp[n-1])
### BUGGY CODE ###

#!/usr/bin/env python3

import collections
import sys
input=sys.stdin.readline

r,c,k=map(int,input().split())
items=collections.defaultdict(int)
for _ in range(k):
    tr,tc,tv=map(int,input().split())
    items[(tr,tc)]=tv
dp=[[[0]*4 for _ in range(c+1)] for _ in range(r+1)]
for i in range(1,r+1):
    for j in range(1,c+1):
        #上から来るときは取った個数が保持される
        dp[i][j][0]=max(dp[i][j][0],dp[i][j-1][0])
        dp[i][j][1]=max(dp[i][j-1][1],dp[i][j-1][0]+items[(i,j)])
        dp[i][j][2]=max(dp[i][j-1][2],dp[i][j-1][1]+items[(i,j)])
        dp[i][j][3]=max(dp[i][j-1][3],dp[i][j-1][2]+items[(i,j)])
        #左から来るときは取った個数をリセットする
        dp[i][j][0]=max(dp[i][j][0],max(dp[i-1][j]))
        dp[i][j][1]=max(dp[i][j][1],max(dp[i-1][j])+items[(i,j)])
print(max(dp[r][c]))

### FIXED CODE ###

#!/usr/bin/env python3

import sys
input=sys.stdin.readline

r,c,k=map(int,input().split())
items=[0]*(r*c)
for _ in range(k):
    tr,tc,tv=map(int,input().split())
    items[c*(tr-1)+tc-1]=tv
dp=[0]*(4*r*c)
for i in range(1,r+1):
    for j in range(1,c+1):
        tv=items[c*(i-1)+j-1]
        change_pos=4*(c*(i-1)+j-1)
        left_pos=4*(c*(i-2)+j-1)
        up_pos=4*(c*(i-1)+j-2)
        if i!=1:
          left_max=max(dp[left_pos],dp[left_pos+1],dp[left_pos+2],dp[left_pos+3])
        else:
          left_max=0
        if j!=1:
          dp[change_pos]=max(dp[up_pos],left_max)
          dp[change_pos+1]=max(dp[up_pos+1],dp[up_pos]+tv,left_max+tv)        
          dp[change_pos+2]=max(dp[up_pos+2],dp[up_pos+1]+tv)
          dp[change_pos+3]=max(dp[up_pos+3],dp[up_pos+2]+tv)
        else:
          dp[change_pos]=left_max
          dp[change_pos+1]=left_max+tv
print(max(dp[-1],dp[-2],dp[-3],dp[-4]))