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

import numpy as np


def count_pair(A, x):
    # A内のペアで積がxより小さいものの個数
    N = len(A)
    cnt = 0
    for n in range(N - 1):
        if A[n] < 0:
            y = x // A[n]
            # n+1番以降でyより大きいものの個数
            cnt += N-max(n+1, np.searchsorted(A, y, side='right'))
        elif A[n] > 0:
            y = -(-x // A[n])
            # n+1番以降でyより小さいものの個数
            cnt += max(n+1, np.searchsorted(A, y, side='left')) - (n + 1)
        else:  # A[n]==0
            if x > 0:
                cnt += N - n - 1
    return cnt


# count_pair(x)<Kをみたすxの最大値を求める
N, K = map(int, input().split())
* A, = map(int, input().split())
A.sort()
inf = 10**18+1
l, r = -inf, inf
while r - l > 1:
    c = (l + r) // 2
    if count_pair(A, c) < K:
        l = c
    else:
        r = c
print(l)


### FIXED CODE ###

import numpy as np


def count_pair(x):
    # A内のペアで積がxより小さいものの個数
    # まず(i,j)と(j,i)を重複して数える
    cnt = 0
    # A[i]<0なる各iに対してA[j]>x/A[i]なるjの個数
    cnt += (N-np.searchsorted(A, x//A_nega, side='right')).sum()
    if x > 0:
        # 各iに対してA[j]=0なるjの個数
        cnt += len(A_zero)*N
    # A[i]>0なる各iに対してA[j]<x/A[i]なるjの個数
    cnt += np.searchsorted(A, -(-x//A_posi), side='left').sum()
    # i=jを除いてから2で割る
    cnt = (cnt-(A**2 < x).sum())//2
    return cnt


# count_pair(x)<Kをみたすxの最大値を二分探索で求める
N, K = map(int, input().split())
* A, = map(int, input().split())
A = np.array(A)
A = np.sort(A)
A_posi = A[A > 0]
A_zero = A[A == 0]
A_nega = A[A < 0]
inf = 10**18+1
l, r = -inf, inf
while r - l > 1:
    c = (l + r) // 2
    if count_pair(c) < K:
        l = c
    else:
        r = c
print(l)
### BUGGY CODE ###

s = input()
n = len(s)
res = dict()
res[0] = 1

for i in range(n):
    T = int(s[-i-1:])%2019
    if res.get(T) == None:
        res[T] = 1
    else:
        res[T] += 1
cnt = 0
for d in res:
    if not res[d] == 1:
        cnt += int(res[d]*(res[d]-1)/2)
print(cnt)

### FIXED CODE ###

import collections
s = input()
n = len(s)
mod_list = [0]

T = 0
for i in range(n):
    T += int(s[-1-i])*pow(10, i, 2019)%2019
    T = T%2019
    mod_list.append(T)

res = collections.Counter(mod_list)
cnt = 0
for d in res.values():
    cnt += int(d*(d-1)/2)
print(cnt)
### BUGGY CODE ###

n=int(input())
p=list(map(int,input().split()))
x=0
for i in range(n):
  if min(p[0:i+1])==p[i]:
    x+=1
print(x)

### FIXED CODE ###

n=int(input())
p=list(map(int,input().split()))
x=0
s=p[0]
for i in range(n):
  if p[i]<=s:
    s=p[i]
    x+=1
print(x)
### BUGGY CODE ###

num = int(input())
table = list(map(int, input().split()))
count = 0

for i in range(num):
    for j in range(i+1, num):
        if table[i] == table[j]:
            count += 1
        else:
            continue
if count == 0:
    print('YES')
else:
    print('NO')

### FIXED CODE ###

num = int(input())
table = list(map(int, input().split()))
count = 0
list.sort(table)
if num == 2:
        if table[0] == table[1]:
            count += 1
else:
    for i in range(1, num-1):
        if num == 2:
            if table[0] == table[1]:
                count += 1
        elif table[i] == table[i+1] or table[i-1] == table[i]:
            count += 1
        else:
            continue
if count == 0:
    print('YES')
else:
    print('NO')
### BUGGY CODE ###

n, k = [int(x) for x in input().split()]
hs = [int(x) for x in input().split()]
dp = {}
dp[0] = 0 # start

for i in range(n):
    for j in range(1, k + 1):
        to = i + j
        if to >= n:
            break
        cost = abs(hs[to] - hs [i]) + dp[i]
        if to in dp:
            if dp[to] > cost:
                dp[to] = cost
        else:
            dp[to] = cost

print(dp[n-1])


### FIXED CODE ###

n, k = [int(x) for x in input().split()]
hs = [int(x) for x in input().split()]
dp = {}
dp[0] = 0 # start

for i in range(n):
    for j in range(1, k + 1):
        to = i + j
        if to >= n:
            break
        cost = abs(hs[to] - hs [i]) + dp[i]
        if to in dp:
            if dp[to] > cost:
                dp[to] = cost
        else:
            dp[to] = cost

print(dp[n-1])
### BUGGY CODE ###

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

count=0
l=sorted(L)

for i in range(N-2):
    for j in range(i+1,N-1):
        for k in range(1,N-j):
            if l[i]+l[j]>l[N-k]:
                count+=N-k-j
                break



print(count)

### FIXED CODE ###

import bisect as bi
N=int(input())
L=list(map(int,input().split()))

count=0
l=sorted(L)
#print(l)
for i in range(N-2):
    for j in range(i+1,N-1):
        count+=bi.bisect_left(l,l[i]+l[j],j+1)-j-1
         
print(count)
### BUGGY CODE ###

from collections import deque

def BellmanFord(adjList, vSt, INF):
    numV = len(adjList)
    negINF = -INF
    costs = [INF] * numV
    costs[vSt] = 0
    vNows = set([vSt])

    for _ in range(numV):
        vChangeds = set()
        for vFr in vNows:
            costFr = costs[vFr]
            for vTo, wt in adjList[vFr]:
                c2 = costFr + wt
                if c2 < costs[vTo]:
                    costs[vTo] = c2
                    vChangeds.add(vTo)
        if not vChangeds:
            return costs
        vNows = vChangeds

    for v in vNows:
        costs[v] = negINF

        Q = deque(vNows)
    while Q:
        vFr = Q.popleft()
        for vTo, wt in adjList[vFr]:
            if costs[vTo] == negINF: continue
            costs[vTo] = negINF
            Q.append(vTo)

    return costs


N, M, P = map(int, input().split())
adjL = [[] for _ in range(N)]
for _ in range(M):
    A, B, C = map(int, input().split())
    A, B = A-1, B-1
    adjL[A].append((B, -(C-P)))

costs = BellmanFord(adjL, 0, float('inf'))

if costs[N-1] == -float('inf'):
    print(-1)
else:
    print(max(0, -costs[N-1]))


### FIXED CODE ###

from collections import deque

def BellmanFord(adjList, vSt, INF):
    numV = len(adjList)
    negINF = -INF
    costs = [INF] * numV
    costs[vSt] = 0
    vNows = set([vSt])

    for _ in range(numV):
        vChangeds = set()
        for vFr in vNows:
            costFr = costs[vFr]
            for vTo, wt in adjList[vFr]:
                c2 = costFr + wt
                if c2 < costs[vTo]:
                    costs[vTo] = c2
                    vChangeds.add(vTo)
        if not vChangeds:
            return costs
        vNows = vChangeds

    for v in vNows:
        costs[v] = negINF

        Q = deque(vNows)
    while Q:
        vFr = Q.popleft()
        for vTo, wt in adjList[vFr]:
            if costs[vTo] == negINF: continue
            costs[vTo] = negINF
            Q.append(vTo)

    return costs


N, M, P = map(int, input().split())
adjL = [[] for _ in range(N)]
for _ in range(M):
    A, B, C = map(int, input().split())
    A, B = A-1, B-1
    adjL[A].append((B, -(C-P)))

costs = BellmanFord(adjL, 0, float('inf'))

if costs[N-1] == -float('inf'):
    print(-1)
else:
    print(max(0, -costs[N-1]))
### BUGGY CODE ###

#create date: 2020-04-12 21:15

import sys
stdin = sys.stdin

def ns(): return stdin.readline().rstrip()
def ni(): return int(ns())
def na(): return list(map(int, stdin.readline().split()))

def main():
    n = ni()
    s = ns()
    r = s.count("R")
    g = s.count("G")
    b = s.count("B")
    ans = r*g*b
    for i in range(0, n-2):
        for j in range(1, (n-1)//+1):
            if i + 2*j < n:
                if len(set([s[i], s[i+j], s[i+2*j]]))==3:
                    ans -= 1
    print(ans)

if __name__ == "__main__":
    main()

### FIXED CODE ###

#create date: 2020-04-12 21:15

import sys
stdin = sys.stdin

def ns(): return stdin.readline().rstrip()
def ni(): return int(ns())
def na(): return list(map(int, stdin.readline().split()))

def main():
    n = ni()
    s = ns()
    r = s.count("R")
    g = s.count("G")
    b = s.count("B")
    ans = r*g*b
    for i in range(0, n-2):
        for j in range(1, (n-1)//+1):
            if i + 2*j < n:
                if len(set([s[i], s[i+j], s[i+2*j]]))==3:
                    ans -= 1
    print(ans)

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

s = input()

l = []
n = len(s)

for i in range(n):
    tmp = int(s[i:]) % 2019
    l.append(tmp)
l.append(0)
res = 0
for i in range(2018):
    count = l.count(i)
    res += count * (count-1) // 2

print(res)

### FIXED CODE ###

s = input()
s = s[::-1]

l = [0 for i in range(2019)]
n = len(s)
l[0] = 1
prev = 0
digit = 1
for c in s:
    t = (int(c) * digit + prev) % 2019
    l[t] += 1
    digit = (digit * 10) % 2019
    prev = t

res = 0
for i in l:
    res += i * (i-1) // 2

print(res)
### BUGGY CODE ###

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

count = 0
isBigger = True

for i in range(len(P)):
	for j in range(i):
		isBigger = True
		if not (P[i] <= P[j]):
			isBigger = False
			break
	if isBigger:
		count += 1

print(count)

### FIXED CODE ###

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

count = 0
min_value = 2e5+1

for p in P:
	if p <= min_value:
		min_value = p
		count += 1

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

N, Q = map(int, input().split())
S = input()

for _ in range(Q):
    li, ri = map(int, input().split())
    sliced_S = str(S[li-1:ri])
    sliced_S = sliced_S.replace("AC", "@")
    print(sliced_S.count("@"))


### FIXED CODE ###

N, Q = map(int, input().split())
S = input()
memo = [0]*N
tmp = 0
for i in range(1, len(S)):
    if S[i-1] == "A" and S[i] == "C":
        tmp += 1
        memo[i] = tmp
    else:
        memo[i] = tmp

for _ in range(Q):
    li, ri = map(int, input().split())
    ans = memo[ri-1] - memo[li-1]
    print(ans)
### BUGGY CODE ###

import math

def is_prime_sqrt(q): #合成数xはp<=sqrt(x)を満たす素因子pを持つ
    if q == 1: #1は素数ではない
        return False
    if q == 2: #2は素数
        return True
    elif q % 2 == 0: #2以外の偶数は合成数
        return False
    for divisor in range(3, math.floor(math.sqrt(q))+1, 2): #繰り返しの上限は平方根
        if q % divisor == 0: #平方根までに約数があれば合成数
            return False
    return True

def mark(s, x):
    for i in range(x + x, len(s), x):
        s[i] = False

def sieve(n): #nまでの素数をエラトステネスの篩で列挙
    s = [True] * n
    for x in range(2, int(n**0.5) + 1):
        if s[x]: mark(s, x)
    return [i for i in range(0,n) if s[i] and i > 1]

Q = int(input())
qs = sieve(100000)

for i in range(Q):
    l, r = map(int, input().split())
    n = 0
    for q in range(l,r+1,2):
        if q in qs and ((q+1)/2) in qs:
            n += 1
    print(n)


### FIXED CODE ###

import math

def is_prime_sqrt(q): #合成数xはp<=sqrt(x)を満たす素因子pを持つ
    if q == 1: #1は素数ではない
        return False
    if q == 2: #2は素数
        return True
    elif q % 2 == 0: #2以外の偶数は合成数
        return False
    for divisor in range(3, math.floor(math.sqrt(q))+1, 2): #繰り返しの上限は平方根
        if q % divisor == 0: #平方根までに約数があれば合成数
            return False
    return True

def mark(s, x):
    for i in range(x + x, len(s), x):
        s[i] = False

def sieve(n): #nまでの素数をエラトステネスの篩で列挙＝戻り値は各要素が素数のリスト
    s = [True] * n
    for x in range(2, int(n**0.5) + 1):
        if s[x]: mark(s, x)
    return [i for i in range(0,n) if s[i] and i > 1]

def sieveyn(n): #nまでの素数をエラトステネスの篩で列挙＝戻り値は各要素が素数のリスト
    s = [True] * n
    for x in range(2, int(n**0.5) + 1):
        if s[x]: mark(s, x)
    return s


Q = int(input())
A = [0] * 100001 #A[0]からA[100000]までのリスト
A[3] = 1
S = sieveyn(100000)

for i in range(5,100001,4):
    if S[i] and S[int((i+1)/2)]:
        A[i] = 1
for i in range(4,100001):
    A[i] += A[i-1]

#print(A[:100])

for i in range(Q):
    l, r = map(int, input().split())
    print(A[r]-A[l-1])
### BUGGY CODE ###

from collections import defaultdict

def f(n):
    yakusu = []
    for i in range(1, int(n ** 0.5) + 1):
        if n % i == 0:
            yakusu.append(i)
            if i != n // i:
                yakusu.append(n // i)
    for i in yakusu:
        if i != 1:
            d[i] += 1

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

for i in range(N):
    f(A[i])

cnt = 1
for i, v in d.items():
    if v != 1:
        cnt = max(cnt, v)
        
if cnt == N:
    print('not coprime')
elif cnt == 1:
    print('pairwise coprime')
else:
    print('setwise coprime')


### FIXED CODE ###

from collections import defaultdict
import math

INF = 10 ** 6 + 1
is_prime = [1] * INF

def eratorasu():
    is_prime[0] = 0
    is_prime[1] = 0
    for i in range(2, INF):
        if is_prime[i] == 0:
            continue
        for j in range(i * 2, INF, i):
            is_prime[j] = 0
    return

def f(n):
    yakusu = []
    if is_prime[n]:
        yakusu.append(n)
    else:
        for i in range(2, int(n ** 0.5) + 1):
            if n % i == 0:
                yakusu.append(i)
                if i != n //i:
                    yakusu.append(n // i)
                break

    for i in yakusu:
        if i != 1:
            d[i] += 1

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

tmp = A[0]
for i in range(1, N):
    tmp = math.gcd(tmp, A[i])
    f(A[i])

if tmp != 1:
    print('not coprime')
    exit()
eratorasu()
f(A[0])

for i, v in d.items():
    if v != 1:
        print('setwise coprime')
        exit()

print('pairwise coprime')
### BUGGY CODE ###

n = int(input())
a = [int(i) for i in input().split()]
a.sort()
xor = []
for i in range(len(a)):
	for k in range(i,len(a)):
		xor.append(int(bin(a[i]^a[k]),0))
xor = list(set(xor))
for i in range(len(a)):
	if i not in xor:
		print("No")
		exit()
print("Yes")

### FIXED CODE ###

n = int(input())
a = [int(i) for i in input().split()]
sum = 0
for i in a:
	sum^=i
if sum == 0:
	print("Yes")
else:
	print("No")
### BUGGY CODE ###

# coding: utf-8
# Your code here!
#########行列読み込み ##############################################
"""
from sys import stdin
n = int(stdin.readline().rstrip())
data = [stdin.readline().rstrip().split() for _ in range(n)]
print(data)
print(*data, sep='\n')
"""
##################################################################
#########入力系####################################################
"""
s =input()
s=list(input())
a=int(input())
x,y = map(int,input().split())	
li = input().split()	
li = list(map(int,input().split()))	
li = input().split('T')	
"""
##################################################################
import numpy as np
l ={}
N,K = map(int,input().split())
#P = list(map(int,input().split()))
P = np.asarray(list(map(int,input().split())))
#print(P)
P_ = []
#print(P_)

def kitai(num):
    x = 0
    for j in range(num):
        x += num-j
    return x/num
for i in P:
    P_.append(kitai(i))
#print(type(P_))


#print(P)
for i in range(0,N-K+1):
    #print(P[i:i+K])
    l[sum(P_[i:i+K])]=i
#print(l)
max = max(l.keys())
print(max)
import sys
def input():
    return sys.stdin.readline()[:-1]







### FIXED CODE ###

#########行列読み込み ##############################################
"""
from sys import stdin
n = int(stdin.readline().rstrip())
data = [stdin.readline().rstrip().split() for _ in range(n)]
print(data)
print(*data, sep='\n')
"""
##################################################################
#########入力系####################################################
"""
s =input()
s=list(input())
a=int(input())
x,y = map(int,input().split())	
li = input().split()	
li = list(map(int,input().split()))	
li = input().split('T')	
"""
##################################################################

N,K = map(int,input().split())
def kitai(num):
    return (1+int(num))/2
P = list(map(kitai,input().split()))	  

S = [0]*(N+1)
ans = 0
for i in range(N):
    S[i+1]=S[i]+P[i]
for i in range(N-K+1):
    ans = max(ans,S[i+K]-S[i])
print(ans)
### BUGGY CODE ###

from collections import deque

H, W = map(int, input().split())
A = []
D = [[-1 for _ in range(W)] for _ in range(H)]
q = deque([])
for i in range(H):
    S = input()
    for j in range(W):
        if S[j] == "#":
            q.append((i, j))
            D[i][j] = 0
    A.append(S)

ans = 0
while q:
    pos = q.popleft()
    py, px = pos[0], pos[1]
    for (y, x) in [(0, -1), (0, 1), (-1, 0), (1, 0)]:
        ny = py + y
        nx = px + x
        if nx < 0 or W <= nx or ny < 0 or H <= ny:
            continue
        if D[ny][nx] < 0:
            D[ny][nx] = D[py][px] + 1
            ans = max(ans, D[ny][nx])
            q.append((ny, nx))
print(ans)


### FIXED CODE ###

from collections import deque

H, W = map(int, input().split())
A = []
D = [[-1 for _ in range(W)] for _ in range(H)]
q = deque([])
for i in range(H):
    S = input()
    for j in range(W):
        if S[j] == "#":
            q.append((i, j))
            D[i][j] = 0
    A.append(S)

while q:
    pos = q.popleft()
    py, px = pos[0], pos[1]
    for (y, x) in [(0, -1), (0, 1), (-1, 0), (1, 0)]:
        ny = py + y
        nx = px + x
        if nx < 0 or W <= nx or ny < 0 or H <= ny:
            continue
        if D[ny][nx] < 0:
            D[ny][nx] = D[py][px] + 1
            q.append((ny, nx))

ans = 0
for i in range(H):
    for j in range(W):
        ans = max(ans, D[i][j])
print(ans)
### BUGGY CODE ###

class DisjointSet():
    def __init__(self, n):
        self._p = [x for x in range(n)]
        self._size = [-1 for x in range(n)]
    
    def find(self, p):
        while p != self._p[p]:
            p = self._p[p]
        return p

    def union(self, p, q):
        pp, qq = self.find(p), self.find(q)
        if pp != qq:
            if self._size[pp] > self._size[qq]:
                self._p[qq] = pp
                self._size[pp] += self._size[qq]
            else:
                self._p[pp] = qq
                self._size[qq] += self._size[pp]
    
    def size(self, p):
        return self._size[self.find(p)]


n, m = [int(x) for x in input().split()]
b =  [tuple(map(lambda x: int(x) - 1, input().split())) for _ in range(m)]
b.reverse()
r = []
t = n*(n-1)//2
ds = DisjointSet(n)
for q, p in b:
  r.append(t)
  qq, pp = ds.find(p), ds.find(q)
  if pp != qq:
    t -= ds.size(pp) * ds.size(qq)
  ds.union(p, q)
for x in reversed(r):
  print(x)

### FIXED CODE ###

class Unionfind():
    def __init__(self, progsize):
        self.table = [-1 for _ in range(progsize)]
        self.size = [1 for _ in range(progsize)]

    def find(self, x):
        while(self.table[x] >= 0):
            x = self.table[x]
        return x

    def union(self, x, y):
        xl = self.find(x)
        yl = self.find(y)
        if xl != yl:
            if self.table[xl] <= self.table[yl]:
                self.table[yl] = xl
                self.table[xl] -= 1
                self.size[xl] += self.size[yl]
            else:
                self.table[xl] = yl
                self.table[yl] -= 1
                self.size[yl] += self.size[xl]

n, m = map(int, input().split())
bridge = [tuple(map(int, input().split())) for _ in range(m)]
bridge.reverse()
uf = Unionfind(n)
cur = n * (n-1) // 2
ans = [cur]
for a, b in bridge:
    ap = uf.find(a-1)
    bp = uf.find(b-1)
    if ap != bp:
        cur -= uf.size[ap] * uf.size[bp]
    uf.union(a-1, b-1)
    ans.append(cur)
for a in reversed(ans[0:m]):
    print(a)
### BUGGY CODE ###

n = int(input())
str = []
for i in range(n):
  str.append(input())

ana = []
for i in range(n):
  alpha = {}
  for j in range(10):
    if alpha.get(str[i][j]) == None:
      alpha[str[i][j]] = 1
    else:
      alpha[str[i][j]] += 1
  ana.append(sorted(alpha.items(), key=lambda x:x[0]))

ans = 0
for i in range(n-1):
  for j in range(i+1, n):
    if ana[i] == ana[j]:
      ans += 1

print(ans)

### FIXED CODE ###

n = int(input())
map = {}
for i in range(n):
  str = ''.join(sorted(input()))
  if str in map:
    map[str] += 1
  else:
    map[str] = 1

ans = 0
for value in map.values():
  ans += value * (value - 1) // 2

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

def main():
  n=int(input())
  a=list(map(lambda x:bin(int(x))[2:],input().split()))
  mod=pow(10,9)+7
  ans=0
  len_ai=[]
  for ai in a:
    len_ai.append(len(ai))
  for i in range(61):# 2^iの位
    bit1=0
    for j in range(n):
      if len_ai[j]>=i+1:
        bit1+=int(a[j][-i-1])
    ans+=pow(2,i)*bit1*(n-bit1)
    ans%=mod
  print(ans)
if __name__=='__main__':
  main()

### FIXED CODE ###

import sys
input = sys.stdin.readline
def main():
  n=int(input())
  a=list(map(int,input().split()))
  mod=pow(10,9)+7
  ans=0
  bit=[0]*61 #bit[i]:2^iの位が1である物の個数
  for ai in a:
    for j in range(61):
      if ((ai>>j) & 1):
        bit[j]+=1
  for i in range(61):
    ans+=(pow(2,i)%mod)*bit[i]*(n-bit[i])
    ans%=mod
  print(ans)
if __name__=='__main__':
  main()
### BUGGY CODE ###

s = input()
q = int(input())
for i in range(q):
    t = input()
    if t == '1':
        s = s[::-1]
    else:
        t2, f, c = t.split()
        if f == '1':
            s = c+s
        else:
            s += c
print(s)            

### FIXED CODE ###

s = input()
q = int(input())
cnt = 0
l = ''
r = ''
for i in range(q):
    t = input()
    if t == '1':
        cnt = 1 - cnt
    else:
        t2, f, c = t.split()
        if cnt == 0:
            if f == '1':
                l = c + l
            else:
                r += c
        else:
            if f == '1':
                r += c
            else:
                l = c + l
                
if cnt == 0:
    print(l+s+r)
else:
    print(r[::-1]+s[::-1]+l[::-1])
### BUGGY CODE ###

s=input()
q=int(input())
dir=True
ans=s
for i in range(q):
  temp=input()
  if temp[0] == "1":
    dir = dir ^ True
  if temp[0] == "2":
    t,f,c = temp.split()
    ff = False
    if dir:
      if f == "1":
        ans=c+ans
      else:
        ans=ans+c
    else:
      if f == "1":
        ans=ans+c
      else:
        ans=c+ans

if dir:
  print(ans)
else:
  print(ans[::-1])

### FIXED CODE ###

s=input()
q=int(input())
dir=True
ans=s
right=""
left=""
query=[]
for i in range(q):
  temp=input()
  if temp[0] == "1":
    dir = dir ^ True
  if temp[0] == "2":
    t,f,c = temp.split()

    if (f == "1" and dir) or (f=="2" and not dir):
      left=c+left
    else:
      right=right+c

def reverse(s):
  t=""
  for i in range(len(s)-1,-1,-1):
    t+=s[i]
  return t

if dir:
  print(left+ans+right)
else:
  t=reverse(right)+reverse(ans)+reverse(left)
  print(t)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(400000000)
def main():
    n,k=map(int,input().split())
    h=tuple(map(int,input().split()))
    flog=[-1]*n
    for i in range(n):#dest=i 0が１
        if i<k+1:#0~k
            flog[i]=abs(h[i]-h[0])
        else:
            min=10**9
            for j in range(1,k+1):#1~k
                tmp=flog[i-j]+abs(h[i]-h[i-j])
                if tmp<min:
                    min=tmp
            flog[i]=min
    print(flog[n-1])
   # print(flog)
if __name__=="__main__":
    main()

### FIXED CODE ###

import sys
sys.setrecursionlimit(400000000)
def main():
    n,k=map(int,input().split())
    h=tuple(map(int,input().split()))
    flog=[-1]*n
    for i in range(n):#dest=i 0が１
        if i<k+1:#0~k
            flog[i]=abs(h[i]-h[0])
        else:
            min=10**9
            for j in range(1,k+1):#1~k
                tmp=flog[i-j]+abs(h[i]-h[i-j])
                if tmp<min:
                    min=tmp
            flog[i]=min
    print(flog[n-1])
   # print(flog)
if __name__=="__main__":
    main()
### BUGGY CODE ###

R, C, K = map(int, input().split())

V = [[0]*(C+1) for _ in range(R+1)]
for _ in range(K):
    r, c, v = map(int, input().split())
    V[r][c] = v

pre = [[0]*(3+1) for _ in range(C+1)]
for i in range(R+1):
    now = [[0]*(3+1) for _ in range(C+1)]
    for j in range(C+1):
        for k in range(3+1):
            if i-1 >= 0:
                now[j][0] = max(now[j][0], pre[j][k])
                now[j][1] = max(now[j][1], pre[j][k] + V[i][j])

            if j-1 >= 0:
                now[j][k] = max(now[j][k], now[j-1][k])
                if k-1 >= 0:
                    now[j][k] = max(now[j][k], now[j-1][k-1] + V[i][j])
    pre = now

print(max(now[C]))


### FIXED CODE ###

R, C, K = map(int, input().split())

V = [[0]*(C+1) for _ in range(R+1)]
for _ in range(K):
    r, c, v = map(int, input().split())
    V[r][c] = v

pre = [[0]*(3+1) for _ in range(C+1)]
for i in range(R+1):
    now = [[0]*(3+1) for _ in range(C+1)]
    for j in range(C+1):
        for k in range(3+1):
            if i-1 >= 0:
                now[j][0] = max(now[j][0], pre[j][k])
                now[j][1] = max(now[j][1], pre[j][k] + V[i][j])

            if j-1 >= 0:
                now[j][k] = max(now[j][k], now[j-1][k])
                if k-1 >= 0:
                    now[j][k] = max(now[j][k], now[j-1][k-1] + V[i][j])
    pre = now

print(max(now[C]))