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

#https://atcoder.jp/contests/dp/tasks/dp_i
import math
N = int(input())
P_List = list(map(float,input().split()))
dp = [[] * N for i in range(N+1)]
std = math.ceil(N/2)
for i in range(N+1):
    if i == 0:
        dp[0].append(1)
    else:
        Current_P = P_List[i - 1]
        for j in range(i + 1):
            if (N - i + j) < std:
                dp[i].append(0)
            elif j == 0:
                dp[i].append(round(dp[i - 1][j]*(1 - Current_P),10))
            elif j != i:
                dp[i].append(round((dp[i - 1][j]*(1 - Current_P)) + (dp[i - 1][j - 1]*Current_P),10))
            else:
                dp[i].append(round(dp[i - 1][j - 1]*Current_P,10))
    
print(sum(dp[N]))

### FIXED CODE ###

#https://atcoder.jp/contests/dp/tasks/dp_i
import math
N = int(input())
P_List = list(map(float,input().split()))
dp = [[0 for j in range(N + 1)] for i in range(N+1)]
std = math.ceil(N/2)
for i in range(N+1):
    if i == 0:
        dp[i][0] = 1
    else:
        Current_P = P_List[i - 1]
        for j in range(i + 1):
            if (N - i + j) < std:
                dp[i][j] = 0
            elif j == 0:
                dp[i][j] = dp[i - 1][j]*(1 - Current_P)
            elif j != i:
                dp[i][j] = (dp[i - 1][j]*(1 - Current_P)) + (dp[i - 1][j - 1]*Current_P)
            else:
                dp[i][j] = dp[i - 1][j - 1]*Current_P
    
print(sum(dp[N][math.ceil(std):]))
### BUGGY CODE ###

from bisect import bisect_left
import sys
n = int(input())
tmp=[int(input())]
if n == 1:
  print(1)
  sys.exit()
for i in range(n-1):
  a = int(input())
  idx = bisect_left(tmp,a)
  if idx==0:
    tmp.insert(0,a)
  else:
    tmp[idx-1] =a
print(len(tmp))

### FIXED CODE ###

import bisect
n = int(input())
a = [- int(input()) for i in range(n)]
tmp = [a[0]]
for i in range(1,n):
  idx=bisect.bisect_right(tmp,a[i])
  if idx==len(tmp):
    tmp.append(a[i])
  else:
    tmp[idx] =a[i]
print(len(tmp))
### BUGGY CODE ###

from collections import Counter
N = int(input())
A = list(map(int,input().split()))

primes = []
def primeFinder(n):
    memo = [1]*(n+1)
    memo[0] = 0
    memo[1] = 0
    for i in range(2,n+1):
        if memo[i] == 1:
            primes.append(i)
            for j in range(i*2,n+1,i):
                memo[j] = 0

primeFinder(10**6)
primeNums = primes
"""
各Aiに関して素因数を算出。素因数を集計してカウントが2つある素因数がなければpairwise
"""
count = Counter([])
for i in range(N):
    tmp = []
    a = A[i]
    i = 0
    while a != 1:
        d = primeNums[i]
        if a % d == 0:
            tmp.append(d)
        while a % d == 0:
            a //= d
        i += 1
    count += Counter(tmp)

for v in count.values():
    if v >= 2:
        break
else:
    print("pairwise coprime")
    exit()

def gcd(a,b):
    return a if b==0 else gcd(b,a%b)

#setwise coprimeを判断
g = A[0]
for i in range(1,N):
    g = gcd(g,A[i])
if g == 1:
    print("setwise coprime")
else:
    print("not coprime")


### FIXED CODE ###

from collections import Counter
N = int(input())
A = list(map(int,input().split()))
countA = Counter(A)

#pairwiseかどうかを調べる
memo = [1]*(10**6+1)
memo[0] = 0
memo[1] = 0
for i in range(2,10**6+1):
    if memo[i] == 1:
        flag = False
        if i in countA:
            if countA[i] >= 2:
                break
            flag = True
        for j in range(i*2,10**6+1,i):
            if j in countA:
                if countA[j] >= 2:
                    break
                if flag:
                    break
                else:
                    flag = True
            memo[j] = 0
        else:
            continue
        break
else:
    print("pairwise coprime")
    exit()



#setwise coprimeを判断
def gcd(a,b):
    return a if b==0 else gcd(b,a%b)

g = A[0]
for i in range(1,N):
    g = gcd(g,A[i])
if g == 1:
    print("setwise coprime")
else:
    print("not coprime")
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
B = [0]*(N+1)
S = 0

for i in range(1, N+1):
    B[i] = A.count(i)
    S += int(B[i]*(B[i]-1)/2)

for i in range(N):
    if B[A[i]] < 2:
        print(S)
    else:
        print(S-B[A[i]]+1)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
B = [0]*(N+1)
S = 0

for i in range(N):
    B[A[i]] += 1

for i in range(1, N+1):
    S += B[i]*(B[i]-1)//2

for k in range(N):
    print(S-B[A[k]]+1)
### BUGGY CODE ###

def factorial(n):
    p = 1
    for i in range(1, n+1):
        p *= i
    return p
n, m = map(int, input().split())
ans = 0
if abs(n-m) == 1:
    ans = factorial(n) * factorial(m)
elif n == m:
    ans = 2 * factorial(n) * factorial(m)
print(ans % (10 ** 9 + 7))


### FIXED CODE ###

n, m = map(int, input().split())
ans = 0
d = [0] * (max([n,m])+1)
def factorial(n):
    global d
    d[0] = 1
    for i in range(1, n+1):
        d[i] = ((i+1) * d[i-1]) % (10** 9 +7)
factorial(max(m,n))
if abs(n-m) == 1:
    ans = d[n-1] * d[m-1]
elif n == m:
    ans = 2 * d[n-1] * d[m-1]
print(ans % (10 ** 9 + 7))
### BUGGY CODE ###

s = input()
t = input()

dp = [[0] * (len(t) + 1) for _ in range(len(s) + 1)]

# 数え上げ
for i in range(len(s)):
    for j in range(len(t)):
        if s[i] == t[j]:
            dp[i + 1][j + 1] = dp[i][j] + 1
        else:
            dp[i + 1][j + 1] = max(dp[i + 1][j], dp[i][j + 1])

# 経路復元
ans = ""
i, j = len(s), len(t)

while i > 0 and j > 0:
    if dp[i][j] == dp[i - 1][j]:
        i -= 1
    elif dp[i][j] == dp[i][j - 1]:
        j -= 1
    else:
        ans = s[i - 1] + ans
        i -= 1
        j -= 1

print(ans)

### FIXED CODE ###

s = input()
t = input()

dp = [[0] * (len(t) + 1) for _ in range(len(s) + 1)]

# 数え上げ
for i in range(len(s)):
    for j in range(len(t)):
        if s[i] == t[j]:
            dp[i + 1][j + 1] = dp[i][j] + 1
        else:
            dp[i + 1][j + 1] = max(dp[i + 1][j], dp[i][j + 1])

# 経路復元
ans = ""
i, j = len(s), len(t)

while i > 0 and j > 0:
    if dp[i][j] == dp[i - 1][j]:
        i -= 1
    elif dp[i][j] == dp[i][j - 1]:
        j -= 1
    else:
        ans = s[i - 1] + ans
        i -= 1
        j -= 1

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

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

ans=[0]*(N-K)

tmp=1
before_score=0
for i in range(0,N):
  tmp*=A[i]
  if i>=K-1:
    if i>=K:
      print('Yes' if before_score<tmp else 'No')
      
    before_score=tmp
    tmp//=A[i-K+1]


    

### FIXED CODE ###

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


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

S = input()
K = int(input())
N = len(S)

l = []
for i in range(N):
    for j in range(i+1,N+1):
        s = S[i:j]
        if s not in l:
            l.append(s)
l.sort()
print(l[K-1])

### FIXED CODE ###

S = input()
K = int(input())
N = len(S)

l = []
for i in range(N):
    for j in range(i+1,min(i+K+1,N+1)):
        s = S[i:j]
        l.append(s)
l = list(set(l))
l.sort()
print(l[K-1])
### BUGGY CODE ###

import math
from functools import reduce

k = int(input())

def find_gcd(*numbers):
    return reduce(math.gcd, numbers)

ans = 0
for a in range(1, k+1, 1):
    for b in range(1, k+1, 1):
        for c in range(1, k+1, 1):
            gcd = find_gcd(a, b, c)
            ans += gcd

print(ans)

### FIXED CODE ###

import math
from functools import reduce

k = int(input())

def find_gcd(*numbers):
    return reduce(math.gcd, numbers)

ans = 0
for a in range(1, k+1, 1):
    for b in range(1, k+1, 1):
        for c in range(1, k+1, 1):
            gcd = find_gcd(a, b, c)
            ans += gcd

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

#!/usr/bin/env python3


def main():
    args = input().split()
    N = int(args[0])
    Y = int(args[1])

    for num10000 in range(0, N + 1):
        for num5000 in range(0, N + 1 - num10000):
            for num1000 in range(0, N + 1 - num10000 - num5000):
                if num10000 + num5000 + num1000 != N:
                    continue
                value = 10000 * num10000 + 5000 * num5000 + 1000 * num1000
                if value == Y:
                    print(num10000, num5000, num1000)
                    return

    print(-1, -1, -1)


if __name__ == "__main__":
    main()


### FIXED CODE ###

#!/usr/bin/env python3


def main():
    args = input().split()
    N = int(args[0])
    Y = int(args[1])

    for num10000 in range(0, N + 1):
        for num5000 in range(0, N + 1 - num10000):
            num1000 = N - num10000 - num5000
            value = 10000 * num10000 + 5000 * num5000 + 1000 * num1000
            if value == Y:
                print(num10000, num5000, num1000)
                return

    print(-1, -1, -1)


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

# coding: utf-8
import numpy as np

N, point, correct = [int(x) for x in input().split()]
r_list = [int(1) for x in range(1, N + 1)]
p_list = [point for x in range(1, N + 1)]
range_list = np.array(r_list)
points_list = np.array(p_list)

for i in range(correct):
    answer = int(input()) - 1
    points_list = points_list - range_list
    points_list[answer] += 1
#    print(points_list)

for p in points_list:
    if p <= 0:
        print('No')
    else:
        print('Yes')

### FIXED CODE ###

# coding: utf-8
import numpy as np

N, point, q = [int(x) for x in input().split()]
r_list = [q] * N
p_list = [point] * N
reduce_list = np.array(r_list)
points_list = np.array(p_list)

for i in range(q):
    answer = int(input()) - 1
    points_list[answer] += 1

points_list = points_list - reduce_list

for p in points_list:
    if p <= 0:
        print('No')
    else:
        print('Yes')
### BUGGY CODE ###

import sys
import numpy as np

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
printV = lambda x: print(*x, sep="\n")
printH = lambda x: print(" ".join(map(str,x)))
def IS(): return sys.stdin.readline()[:-1]
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI1(): return list(map(int1, sys.stdin.readline().split()))
def LII(rows_number): return [II() for _ in range(rows_number)]
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def LLI1(rows_number): return [LI1() for _ in range(rows_number)]

def main():
	x,y,a,b,c = MI()
	p = np.array(LI())
	p = np.sort(p)[::-1]
	q = np.array(LI())
	r = np.array(LI())
	r = np.sort(r)[::-1]
	X = a
	ans = 0
	for X in range(min(a,x),-1,-1):
		Cx=0
		if(x > X):
			Cx = x-X
			s = np.concatenate([q,r[Cx-1:]], axis=0)
			s = np.sort(s)[::-1]
			ans = max(ans, np.sum(p[:X])+np.sum(r[:Cx])+np.sum(s[:y]))
		else:
			s = np.concatenate([q,r], axis=0)
			s = np.sort(s)[::-1]
			ans = max(ans, np.sum(p[:X])+np.sum(s[:y+Cx]))
	print(ans)

if __name__ == '__main__':
	main()

### FIXED CODE ###

import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
printV = lambda x: print(*x, sep="\n")
printH = lambda x: print(" ".join(map(str,x)))
def IS(): return sys.stdin.readline()[:-1]
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI1(): return list(map(int1, sys.stdin.readline().split()))
def LII(rows_number): return [II() for _ in range(rows_number)]
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def LLI1(rows_number): return [LI1() for _ in range(rows_number)]

def main():
	x,y,a,b,c = MI()
	p = LI()
	p.sort(reverse=True)
	q = LI()
	q.sort(reverse=True)
	r = LI()

	p = p[:x]
	q = q[:y]
	pqr = p+q+r
	pqr.sort(reverse=True)
	print(sum(pqr[:x+y]))

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

def main():
    import sys
    input = sys.stdin.buffer.readline
    N = int(input())
    edge = [[] for _ in range(N)]
    for i in range(N-1):
        a, b, c = (int(i) for i in input().split())
        edge[a-1].append((c, b-1))
        edge[b-1].append((c, a-1))

    dist = [-1]*N
    color = [-1]*N

    def dfs(v, G):
        todo = []
        dist[v] = 0
        color[v] = 0
        todo.append(v)
        while todo:
            u = todo[-1]
            for c, next_v in G[u]:
                if dist[next_v] != -1:
                    continue
                dist[next_v] = dist[u] + c
                if dist[next_v] % 2 == 1:
                    color[next_v] = 1
                else:
                    color[next_v] = 0
                todo.append(next_v)
                break
            else:
                todo.pop()

    dfs(0, edge)
    print(*color, sep="\n")
    # print("\n", *dist, sep="\n")


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    import sys
    input = sys.stdin.buffer.readline
    N = int(input())
    G = [[] for _ in range(N+1)]
    st = 0
    st_w = 0
    for i in range(N-1):
        u, v, w = (int(i) for i in input().split())
        G[u].append((v, w))
        G[v].append((u, w))
        if i == 0:
            st = u
            st_w = w
    color = [-1] * (N+1)  # 0: white, 1: black, -1: undefined
    from collections import deque

    def coloring(v, w):
        """
        breadth-first search
        a simplified version
        """
        que = deque()
        color[v] = 0
        que.append((v, w))
        while que:
            u, w = que.popleft()
            for v, d in G[u]:
                if color[v] != -1:
                    continue
                if d % 2 != 0:
                    n_col = (color[u] + 1) % 2
                else:
                    n_col = color[u]
                color[v] = n_col
                que.append((v, d))

    coloring(st, st_w)
    for c in color[1:]:
        print(c)


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

import bisect
import sys
sys.setrecursionlimit(10**9)

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()
def deb(text): print("-------\n{}\n-------".format(text))

INF=10**20
def main():
    N,M,Q=mi()
    Ls = []
    Rs = []
    for i in range(M):
        L,R=mi()
        Ls.append((L,i))
        Rs.append((R,i))

    Ls.sort()
    Rs.sort()

    L_indexs = [set()] * (M+1)
    R_indexs = [set()] * (M+1)

    _Ls = []
    _Rs = []
    for i in range(M):
        L,L_i = Ls[M-1-i]
        R,R_i = Rs[i]

        L_indexs[i+1] = L_indexs[i] | set([L_i])
        R_indexs[i+1] = R_indexs[i] | set([R_i])

        _Ls.append(Ls[i][0])
        _Rs.append(R)

        
        
    # print(L_indexs)
    # print(L_indexs,R_indexs)
    for i in range(Q):
        p,q=mi()
        L_i = bisect.bisect_left(_Ls,p)

        # print(L_i)
        
        R_i = bisect.bisect_right(_Rs,q)
        if R_i == M:
            R_i -= 1
        elif Rs[R_i][0] != q:
            R_i -= 1

        ans = 0
        # print(M-L_i,R_i, L_indexs[M-L_i],R_indexs[R_i+1])
        if R_indexs[R_i+1] > L_indexs[M-L_i]:
            for j in L_indexs[M-L_i]:
                if j in R_indexs[R_i+1]:
                    ans += 1
        else:
            for j in R_indexs[R_i+1]:
                if j in L_indexs[M-L_i]:
                    ans += 1
        
        print(ans)



if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**9)

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()
def deb(text): print("-------\n{}\n-------".format(text))

INF=10**20
def main():
    N,M,Q=mi()
    
    count = [[0] * (N+1) for _ in range(N+1)]
    for i in range(M):
        L,R=mi()
        count[L][R] += 1
    
    # print(count)
    dp = [[0] * (N+1) for _ in range(N+1)]

    for w in range(1,N+1):
        for h in range(1,N+1):
            l,r=N+1-w,h
            dp[w][h] += dp[w][h-1] + dp[w-1][h] - dp[w-1][h-1] + count[l][r]


    # print(dp)
    for i in range(Q):
        p,q=mi()
        w,h=N+1-p,q
        # print(w,h)
        print(dp[w][h])

            






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

import sys


def main():
    n = int(sys.stdin.readline().strip())
    a = [[0] * n for _ in range(n)]
    for i in range(n):
        a[i] = [int(s) for s in sys.stdin.readline().strip().split(' ')]

    loc = [n-2] * n

    ans = 0
    while any([loc_i != -1 for loc_i in loc]):  # TODO: infinity handling
        found = False
        used = [False] * n
        for i in range(n):
            if loc[i] == -1:
                continue
            if used[i]:
                continue
            target = a[i][loc[i]] - 1
            if used[target]:
                continue
            if loc[target] == -1:
                continue
            if a[target][loc[target]] - 1 == i:
                used[i] = True
                used[target] = True
                loc[i] -= 1
                loc[target] -= 1
                found = True
        ans += 1
        if not found:
            print(-1)
            return
    print(ans)


main()


### FIXED CODE ###

import sys
import time


def main():
    n = int(sys.stdin.readline().strip())
    a = [[0] * n for _ in range(n)]
    for i in range(n):
        a[i] = [int(s) for s in sys.stdin.readline().strip().split(' ')]

    loc = [n-2] * n

    ans = 0
    game_count = 0
    total_game_count = n * (n-1) // 2
    start = time.time()
    while game_count != total_game_count:
        now = time.time()
        if (now - start > 1):
            print(n * (n-1) // 2)
            return

        found = False
        used = [False] * n
        for i in range(n):
            if loc[i] == -1:
                continue
            if used[i]:
                continue
            target = a[i][loc[i]] - 1
            if used[target]:
                continue
            if loc[target] == -1:
                continue
            if a[target][loc[target]] - 1 == i:
                used[i] = True
                used[target] = True
                loc[i] -= 1
                loc[target] -= 1
                found = True
                game_count += 1
        ans += 1
        if not found:
            print(-1)
            return
    print(ans)


main()
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
ans=0
for i in range(1,100001):
    tmp=0
    tmp+=a.count(i-1)
    tmp+=a.count(i)
    tmp+=a.count(i+1)
    if tmp>ans:
        ans=tmp
print(ans)

### FIXED CODE ###

n=int(input())
b=[0 for i in range(100002)]
a=list(map(int,input().split()))
a.sort()
for i in range(n):
    b[a[i]]+=1
ans=0
for i in range(1,100001):
    tmp=b[i-1]+b[i]+b[i+1]
    if tmp>ans:
        ans=tmp
print(ans)
### BUGGY CODE ###

n, q = [int(x) for x in input().split()]
vs   = []
us   = [1]
xs   = None
	
for _ in range(0, n + 1):
	vs.append([])
	xs = [0] * (n + 1)

for _ in range(0, n - 1):
	a, b = [int(x) for x in input().split()]
	vs[a].append(b)
	vs[b].append(a)

for _ in range(0, q):
	p, x   = [int(x) for x in input().split()]
	xs[p] += x
	
for i in range(0, n):
	x = xs[us[i]]
	for v in vs[us[i]]:
		if v not in us:
			xs[v] += x
			us.append(v)

print(" ".join(str(x) for x in xs[1:]))


### FIXED CODE ###

n, q = [int(x) for x in input().split()]
vs   = []
	
for _ in range(0, n + 1):
	vs.append([])
	
xs    = [0]     * (n + 1)
fs    = [False] * (n + 1)
us    = [0]     * n
fs[1] = True
us[0] = 1
ui    = 0

for _ in range(0, n - 1):
	a, b = [int(x) for x in input().split()]
	vs[a].append(b)
	vs[b].append(a)

for _ in range(0, q):
	p, x   = [int(x) for x in input().split()]
	xs[p] += x
	
for i in range(0, n):
	x = xs[us[i]]
	for v in vs[us[i]]:
		if fs[v] == False:
			xs[v] += x
			ui    += 1
			us[ui] = v
			fs[v]  = True

print(" ".join(str(x) for x in xs[1:]))
### BUGGY CODE ###

def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    import math

    #inf = 10**17
    mod = 10**9 + 7

    # 素因数分解
    def prime_decomp(n):
        i = 2
        res = []
        while i ** 2 <= n:
            while n % i==0:
                n //= i
                res.append(i)
            i += 1
        if n > 1:
            res.append(n)
        return res
        # 素因数のリストを返す(0, 1は空)

    # aの逆元を求める
    def inv(a, mod=mod):
        return pow(a, mod-2, mod)

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


    lcm = [0]*(max(a)+1)
    for i in a:
        l = prime_decomp(i)
        c = Counter(l)
        for k, v in c.items():
            if lcm[k] < v:
                lcm[k] = v
    
    b = 1
    for i in range(len(lcm)):
        if lcm[i] != 0:
            b *= pow(i, lcm[i], mod)
    
    if n == 1:
        print(1)
    else:
        res = 0
        for i in a:
            res += inv(i)
        print(res*b%mod)

if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    import math

    #inf = 10**17
    mod = 10**9 + 7

    def gcd(a, b):
        if b == 0:
            return a
        else:
            return gcd(b, a % b)
    
    def gcd_group(arr):
        g = gcd(arr[0], arr[1])
        for i in range(2, len(arr)):
            g = gcd(g, arr[i])
        return g
    
    def lcm(a, b):
        g = gcd(a, b)
        return (a*b)//g
    
    def lcm_group(arr):
        l = lcm(arr[0], arr[1])
        for i in range(2, len(arr)):
            l = lcm(l, arr[i])
        return l
    
    # groupは要素1つでエラー

    # aの逆元を求める
    def inv(a, mod=mod):
        return pow(a, mod-2, mod)

    n = int(input())
    a = list(map(int, input().split()))
    if n == 1:
        print(1)
    else:
        l = lcm_group(a)
        res = 0
        for i in a:
            res += inv(i)
        print(res*l%mod)

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

from collections import deque

line1 = input()
n, k = [int(num) for num in line1.split(" ")]
line2 = input()
h = [int(num) for num in line2.split(" ")]

d = deque([0], k)

for i in range(1, len(h)):
    min_cost = float("inf")
    for j,cost in enumerate(d):
        steps_taken = len(d)-j
        if i-steps_taken < 0: break
        step_cost = abs(h[i]-h[i-steps_taken])
        min_cost = min(min_cost, cost + abs(h[i]-h[i-steps_taken]))
        if step_cost == 0: break
    d.append(min_cost)

print(d[-1])

### FIXED CODE ###

from collections import deque

line1 = input()
n, k = [int(num) for num in line1.split(" ")]
line2 = input()
h = [int(num) for num in line2.split(" ")]

d = deque([0], k)

for i in range(1, len(h)):
    min_cost = float("inf")
    for j,cost in enumerate(reversed(d)):
        steps_taken = j+1
        if i-steps_taken < 0: break
        step_cost = abs(h[i]-h[i-steps_taken])
        min_cost = min(min_cost, cost + abs(h[i]-h[i-steps_taken]))
        if step_cost == 0: break
    d.append(min_cost)

print(d[-1])
### BUGGY CODE ###

import sys
import bisect

n = int(sys.stdin.readline())
a = list(map(int, sys.stdin.readline().split()))
b = list(map(int, sys.stdin.readline().split()))
c = list(map(int, sys.stdin.readline().split()))

a.sort()
b.sort()
c.sort()

ans = 0

for i in range(n):
    b_index = bisect.bisect_right(b, a[i])
    for j in range(b_index, n):
        ans += n - bisect.bisect_right(c, b[j])

print(ans)


### FIXED CODE ###

import sys
import bisect

n = int(sys.stdin.readline())
a = list(map(int, sys.stdin.readline().split()))
b = list(map(int, sys.stdin.readline().split()))
c = list(map(int, sys.stdin.readline().split()))

a.sort()
b.sort()
c.sort()

b_ans_list = [0 for _ in range(n)]
for i in reversed(range(n)):
    # b[i]における選択可能なcの個数
    if i == n-1:
        b_ans_list[i] = n - bisect.bisect_right(c, b[i])
    else:
        b_ans_list[i] = n - bisect.bisect_right(c, b[i]) + b_ans_list[i+1]

ans = 0
for i in range(n):
    b_index = bisect.bisect_right(b, a[i])
    if b_index < n: ans += b_ans_list[b_index]

print(ans)