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

n, k = map(int, raw_input().split(" "))

d = {}
for i in range(n):
    a1, b1 = map(int, raw_input().split(" "))
    if a1 in d.keys():
        d[a1] += b1
    else:
        d[a1] = b1


count = 0
for item in sorted(d.items(), key=lambda x: x[0]) :
    count += item[1]
    if k <= count:
        print item[0]
        break
    #count += item[1]


### FIXED CODE ###

line_one = raw_input().split()
n = int(line_one[0])
k = int(line_one[1])

l = []
#d = {}
for i in range(n):
    line_one2 = raw_input().split()
    a1 = int(line_one2[0])
    b1 = int(line_one2[1])
    l.append( ( a1, b1 ))
    #if a1 in l:
    #    #d[a1] += b1
    #    l[a1][1] += b1
    #else:
    #    l.append( ( a1, b1 ))
    #    #//d[a1] = b1

#l.sort()
l = sorted(l, key=lambda x: x[0])
count = 0
for item in l:
    count += item[1]
    if k <= count:
        print item[0]
        break
### BUGGY CODE ###


def a(H):
    global ans
    if H <= 1:
        ans = ans + 1
    else:
        ans = ans + 1
        a(H // 2)
        a(H//2)


H = int(input())
ans = 0
a(H)
print(ans)



### FIXED CODE ###

def a(H):
    global ans
    global dic
    if H // 2 in dic:
        add = 2 * ans + 1
        ans = add
        dic[H] = add
    else:
        a(H//2)
        a(H//2)

H = int(input())
dic = {}
dic[1] = 1
ans = 1
if H != 1:
    a(H)
print(ans)
### BUGGY CODE ###

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

time_A = list(map(int, input().split()))
time_B = list(map(int, input().split()))
max_books = 0
allot_to_A = 0
allot_to_B = K

while True:
    if max_books == len(time_A) + len(time_B):
        break
    num_books = 0
    change_point = 10000000000
    time_bankA = allot_to_A
    time_bankB = allot_to_B

    for i in range(len(time_A)):
        if time_A[i] <= time_bankA:
            time_bankA -= time_A[i]
            num_books += 1
        else:
            change_point = time_A[i] - time_bankA  # Aで読める本が１冊増える時間
            break

    for j in range(len(time_B)):
        if time_B[j] <= time_bankB:
            time_bankB -= time_B[j]
            num_books += 1
        else:
            break

    max_books = max(max_books, num_books)
    allot_to_A += change_point
    allot_to_B -= change_point
    if allot_to_A < 0 or allot_to_B < 0:
        break

print(max_books)


### FIXED CODE ###

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

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

a, b = [0], [0]
for i in range(N):
    a.append(a[i] + A[i])
for i in range(M):
    b.append(b[i] + B[i])

ans, j = 0, M
for i in range(N+1):
    if a[i] > K:
        break
    while b[j] > K - a[i]:
        j -= 1
    ans = max(ans, i + j)

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


S = input()
N = len(S) + 1
settingIndex = 0
result = [ -1 for i in range(N) ]

def countContinueChar(index):
    startChar = S[index]
    count = 0
    for i in range(index, N-1):
        if S[i] != startChar:
            break
        count += 1
    return count

def getValueOfIndex(index, current, prev = ''):
    if S[index] == '<':
        if prev == '>':
            return 0
        else:
            return current + 1
    else:
        if prev == '<':
            v = countContinueChar(index)
            if v < current + 1:
                return current + 1
            else:
                return v
        else:
            return countContinueChar(index)

current = -1
prev = ''
sum = 0
for i in range(N):
    if i == N-1:
        if S[-1] == '<':
            result[i] = current + 1
            sum += current + 1
        else:
            result[i] = 0
        break
    if i > 0:
        prev = S[i - 1]
    current = getValueOfIndex(i, current, prev)
    result[i] = current
    sum += current

print(sum)

### FIXED CODE ###


S = input()
N = len(S) + 1
result = [ -1 for i in range(N) ]

def countContinueChar(index):
    startChar = S[index]
    count = 0
    for i in range(index, N-1):
        if S[i] != startChar:
            break
        count += 1
    return count

def getValueOfIndex(index, current, prev = '', preprev = ''):
    if S[index] == '<':
        if prev == '>':
            return 0
        else:
            return current + 1
    else:
        if prev == '<':
            v = countContinueChar(index)
            if v < current + 1:
                return current + 1
            else:
                return v
        else:
            if preprev == '<' and prev == '>':
                return countContinueChar(index)
            else:
                if prev != '>':
                    return countContinueChar(index)
                else:
                    return current - 1

current = -1
prev = ''
preprev = ''
sum = 0
for i in range(N):
    if i == N-1:
        if S[-1] == '<':
            result[i] = current + 1
            sum += current + 1
        #else:
            #result[i] = 0
        break
    if i > 0:
        prev = S[i - 1]
    if i > 1:
        preprev = S[i - 2]
    current = getValueOfIndex(i, current, prev, preprev)
    #result[i] = current
    sum += current

#print(result)
print(sum)
### BUGGY CODE ###

s=input()
q=int(input())
Q=[input().split() for i in range(q)]

flg=1
for i in range(q):
    if Q[i][0]=="1":flg*=-1
    if Q[i][0]=="2":
        if Q[i][1]=="1" and flg==1: s=Q[i][2]+s
        if Q[i][1]=="2" and flg==-1:s=Q[i][2]+s
        if Q[i][1]=="1" and flg==-1:s=s+Q[i][2]
        if Q[i][1]=="2" and flg==1:s=s+Q[i][2]
if flg==-1:s=s[::-1]
print(s)

### FIXED CODE ###

s=input()
s1=""
s2=""
q=int(input())
Q=[input().split() for i in range(q)]

flg=1
for i in range(q):
    if Q[i][0]=="1":flg*=-1
    if Q[i][0]=="2":
        if Q[i][1]=="1" and flg==1: s1=Q[i][2]+s1
        if Q[i][1]=="2" and flg==-1:s1=Q[i][2]+s1
        if Q[i][1]=="1" and flg==-1:s2=s2+Q[i][2]
        if Q[i][1]=="2" and flg==1:s2=s2+Q[i][2]
s=s1+s+s2
if flg==-1:s=s[::-1]
print(s)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**6)

n, q = map(int, input().split())
neighbor = [[] for _ in range(n)]
point = [0]*n

for i in range(n-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    neighbor[a].append(b)
    neighbor[b].append(a)

for i in range(q):
    p, x = map(int, input().split())
    point[p-1] += x


def dfs(now, past):
    for nv in neighbor[now]:
        if nv == past:
            continue
        point[nv] += point[now]
        dfs(nv, now)


dfs(0, -1)


print(*point)


### FIXED CODE ###

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

n, q = map(int, input().split())
neighbor = [[] for _ in range(n)]
point = [0]*n

for i in range(n-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    neighbor[a].append(b)
    neighbor[b].append(a)

for i in range(q):
    p, x = map(int, input().split())
    point[p-1] += x


def dfs(now, past):
    for nv in neighbor[now]:
        if nv == past:
            continue
        point[nv] += point[now]
        dfs(nv, now)


dfs(0, -1)


print(*point)
### BUGGY CODE ###

K, S = map(int, input().split())

ans = 0
for i in range(K + 1):
  for j in range(K + 1):
    if i + j == S:
      ans += 1
    elif 0 <= S - (i + j) <= K:
      ans += 1
print(ans)

### FIXED CODE ###

K, S = map(int, input().split())

ans = 0
for i in range(K + 1):
  for j in range(K + 1):
    if i + j == S:
      ans += 1
    elif 0 <= S - (i + j) <= K:
      ans += 1
print(ans)
### BUGGY CODE ###

n=int(input())
s=input()
ans=n
for i in range(n):
    tmp=s[i+1:].count("E")
    tmp+=s[:i].count("W")
    ans=min(ans,tmp)
print(ans)

### FIXED CODE ###

import numpy as np
n=int(input())
s=input()
w=list(map(lambda x: x=="W",s))
e=list(map(lambda x: x=="E",s))
w = np.array([0]+w).cumsum()
e = np.array([0]+e[::-1]).cumsum()
e = e[::-1]
ans=n
for i in range(n+1):
    tmp=w[i-1]+e[i]
    ans=min(ans,tmp)
print(ans)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
result = 1
checker =False
for j in a:
  if j > 1000000000000000000:
    result = -1
    checker =True
if 0 in a:
  result = 0
  checker=True
while checker==False:
  for i in range(len(a)):
    result = result*a[i]
  checker = True
    

if result <= 1000000000000000000:
  print(result)
else:
  print(-1)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
a.sort()
result = 1
for i in range(len(a)):
  result = result*a[i]
  if result == 0:
    break
  elif result > 1000000000000000000:
    break

if result <= 1000000000000000000:
  print(result)
else:
  print(-1)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

n = int(input())
a1, a2, a3 = map(int, input().split())
b1, b2, b3 = map(int, input().split())
def f(n, a1, a2, a3, b1, b2, b3):
  dp = [0]*(n+1)
  for i in range(n+1):
    for a, b in zip((a1, a2, a3), (b1, b2, b3)):
      if i-a >= 0:
        dp[i] = max(dp[i], dp[i-a]+b)
  return max(dp[i]+n-i for i in range(n+1))
m = f(n, a1, a2, a3, b1, b2, b3)
ans = f(m, b1, b2, b3, a1, a2, a3)
print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline

n = int(input())
A = tuple(map(int, input().split()))
B = tuple(map(int, input().split()))
def f(n):
  dp = list(range(n+1))
  for a, b in zip(A, B):
    for i in range(n+1):
      if i-a >= 0:
        dp[i] = max(dp[i], dp[i-a]+b)
  return max(dp)
m = f(n)
A, B = B, A
ans = f(m)
print(ans)
### BUGGY CODE ###

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

to = [[] for _ in range(N)]
for _ in range(N - 1):
  a, b = map(int, input().split())
  a -= 1
  b -= 1
  to[a].append(b)
  to[b].append(a)

queue = [0]
branch = [[i] for i in range(N)]
parent = [[] for _ in range(N)]
while len(queue) > 0:
  q = queue.pop(0)
  for br in to[q]:
    branch[q].append(br)
    to[br].remove(q)
    parent[br].append(q)
    for p in parent[q]:
      parent[br].append(p)
    queue.append(br)

for i in range(1, N):
  for p in parent[i]:
    if not i in branch[p]:
      branch[p].append(i)

cnt = [0 for _ in range(N)]
for _ in range(Q):
  p, x = map(int, input().split())
  p -= 1
  for b in branch[p]:
    cnt[b] += x

for i in range(N):
  print(cnt[i], end = "")
  if i == N - 1:
    print()
  else:
    print(" ", end = "")

### FIXED CODE ###

from collections import deque
n, Q = map(int, input().split())
edges = [[] for _ in range(n+1)]
count = [0]*(n+1)
q = deque()
q.append((1, 0))

for _ in range(n-1):
    a, b = map(int, input().split())
    edges[a].append(b)
    edges[b].append(a)
for _ in range(Q):
    p, x = map(int, input().split())
    count[p] += x

while(q):
    k = q.popleft()
    count[k[0]] += count[k[1]]
    for i in edges[k[0]]:
        if not i == k[1]:
            q.append((i, k[0]))

print(*count[1:])
### BUGGY CODE ###

#122c
N,Q = map(int, input().split())
S = str(input())

for _ in range(Q):
    l,r = map(int, input().split())
    print(S[l-1:r].count('AC'))

### FIXED CODE ###

#122c
#累積和
N,Q = map(int, input().split())
S = list(input())

AC_cumsum = list()
AC_cumsum.append(0)

for i in range(1,N):
    #print(S[i])
    if S[i-1]=="A" and S[i]=="C":
        AC_cumsum.append(AC_cumsum[-1] + 1)
    else:
        AC_cumsum.append(AC_cumsum[-1])
        
#print(AC_cumsum)
    
for i in range(Q):
    l,r = map(int, input().split())
    print(AC_cumsum[r-1] - AC_cumsum[l-1])
### BUGGY CODE ###

import math
import collections as c
def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

n,m=map(int,input().split())
a = [-1]+[int(input()) for _ in range(m)]+[n+1]

def comb(dann):
    num_comb = 0
    for i in range((dann//2)+1):
        num_comb += combinations_count(dann-i, i)
    return num_comb

danns = c.Counter([(a[i+1] - a[i]) - 2 for i in range(len(a)-1)])

ans = 1
ddict = {}
for j in set(list(danns.keys())):
    ans *= comb(j) ** danns[j]
print(ans%1000000007)

### FIXED CODE ###

N, M = map(int, input().split())
A = [int(input()) for _ in range(M)]
inf = float("inf")
dp = [0] * (N+1)
for i in A:
	dp[i] = inf
dp[0] = 1
if dp[1] != inf:
	dp[1] = 1
for i in range(2,N+1):
	if dp[i] == inf:
		continue

	a = dp[i-2] if dp[i-2] != inf else 0
	b = dp[i-1] if dp[i-1] != inf else 0

	dp[i] = (a + b) % 1000000007


print(dp[N])
### BUGGY CODE ###

import numpy as np


def main():
    for _ in range(M):
        A.sort()
        A[-1] = A[-1] // 2

    print(sum(A))


if __name__ == "__main__":
    N, M = map(int, input().split())
    A = np.array(list(map(int, input().split())))
    main()

### FIXED CODE ###

import heapq


def main():
    for _ in range(M):
        mx = heapq.heappop(A) * -1 // 2 * -1
        heapq.heappush(A, mx)

    print(sum(A) * -1)


if __name__ == "__main__":
    N, M = map(int, input().split())
    A = [int(x) * -1 for x in input().split()]
    heapq.heapify(A)
    main()
### BUGGY CODE ###

x = [1, 2, 3, 4, 5, 6, 7, 8, 9]
k = int(input())

for i in range(k):
  f = x.pop(0)
  if(f % 10 != 0):	x.append(10 * f + f % 10 - 1)
  x.append(10 * f + f % 10)
  if(f % 10 != 9):	x.append(10 * f + f % 10 + 1)
print(f)    

  
  

### FIXED CODE ###

from collections import deque
x = deque([1, 2, 3, 4, 5, 6, 7, 8, 9])
k = int(input())

for i in range(k):
  f = x.popleft()
  if(f % 10 != 0):	x.append(10 * f + f % 10 - 1)
  x.append(10 * f + f % 10)
  if(f % 10 != 9):	x.append(10 * f + f % 10 + 1)
print(f)
### BUGGY CODE ###

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


class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


uf = UnionFind(N)
for a, b in AB:
    uf.union(a - 1, b - 1)

max_ = 0
for val in uf.all_group_members().values():
    max_ = max(max_, len(val))

print(max_)


### FIXED CODE ###

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


class UnionFind(object):
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]


uf = UnionFind(N)
for a, b in AB:
    uf.union(a - 1, b - 1)

max_ = 0
roots = uf.roots()

for r in roots:
    max_ = max(max_, uf.size(r))

print(max_)
### BUGGY CODE ###

N = int(input())
O = input()

def check(O):
    idx = [i for i, s in enumerate(O) if s == 'R' and i != 0]
    for i in idx:
        if O[i-1] == 'W':
            return False
    return True

def swap(O, t1, t2):
    L = [x for x in O]
    tmp = L[t1]
    L[t1] = L[t2]
    L[t2] = tmp
    return ''.join(L)

count = 0
while not check(O):
    ridx = [i for i, s in enumerate(O) if s == 'R']
    wrdx = [i for i, s in enumerate(O) if s == 'W']
    O = swap(O, max(ridx), min(wrdx))
    count += 1
    
print(count)

### FIXED CODE ###

N = int(input())
O = input()
ridx = [i for i, s in enumerate(O) if s == 'R']
n = len([i for i in ridx if i >= len(ridx)])
print(n)
### BUGGY CODE ###

import copy
from collections import Counter
n=int(input())
a=list(map(int,input().split()))
count=dict(Counter(a))
ans=0

for i in range(n):
    count1=copy.copy(count)
    num=a[i]
    count1[num]-=1
    for j,k in count1.items():
        ans+=k*(k-1)/2
    print(int(ans))
    ans=0


### FIXED CODE ###

import copy
from collections import Counter
n=int(input())
a=list(map(int,input().split()))
count=dict(Counter(a))
ans=0
dic={}
for j,k in count.items():
    ans=k*(k-1)/2
    dic[j]=ans
s=sum(dic.values())
for i in range(n):
    v=count[a[i]]
    if v==0:
        print(0)
    else:
        print(int(s-v+1))
### BUGGY CODE ###

N=int(input())
S=input()
q=[]
for i in range(N):
    for j in range(N):
        if i<j and S[i]==S[j]:
            q.append((i,j,1))
if len(q)==0:
    ans=0
    print(ans)
    exit()
ans=1
while(len(q)>0):
    l1,l2,ln=q.pop()
    if l2+ln<N and l1+ln<l2:
        if S[l1+ln]==S[l2+ln]:
            ans=max(ans,ln+1)
            q.append((l1,l2,ln+1))
print(ans)

### FIXED CODE ###

#https://tjkendev.github.io/procon-library/python/string/rolling_hash.html
class RollingHash():
    def __init__(self, s, base, mod):
        self.mod = mod
        self.pw = pw = [1]*(len(s)+1)
 
        l = len(s)
        self.h = h = [0]*(l+1)
 
        v = 0
        for i in range(l):
            h[i+1] = v = (v * base + ord(s[i])) % mod
        v = 1
        for i in range(l):
            pw[i+1] = v = v * base % mod
    def get(self, l, r):
        return (self.h[r] - self.h[l] * self.pw[r-l]) % self.mod
N=int(input())
S=input()
R1=RollingHash(S,37,10**9+7)
R2=RollingHash(S,29,10**9+9)
ans=0
for ln in range(1,N//2+1):
    D=dict()
    for l in range(N-ln+1):
        tmp=(R1.get(l,l+ln),R2.get(l,l+ln))
        if tmp in D:
            if D[tmp]+ln<=l:
                ans=max(ln,ans)
        else:
            D[tmp]=l
print(ans)
### BUGGY CODE ###

n = int(input())

a = []
s = [0] * n
a.append(input().split())

for i in range(n-1):
    a[0][i] = int(a[0][i])

for i in range(n-1):
    for j in range(n):
        if j == a[0][i]:
            s[j - 1] += 1
            break

for i in range(n):
    print(s[i])

### FIXED CODE ###

n = int(input())

a = []
s = [0] * n
a.append(input().split())

for i in range(n - 1):
    a[0][i] = int(a[0][i])
    s[a[0][i]-1] += 1

for i in range(n):
    print(s[i])
### BUGGY CODE ###

a, b, c = map(int, input().strip().split())
X = [b for _ in range(a)]

for _ in range(c):
    n = int(input().strip()) - 1
    for i in range(a):
        if not n == i:
            X[i] -= 1

for x in X:
    if x > 0:
        print('Yes')
    else:
        print('No')

### FIXED CODE ###

N, K, Q = map(int, input().strip().split())
P = [K - Q for _ in range(N)]

for _ in range(Q):
    i = int(input()) - 1
    P[i] += 1

for p in P:
    if p > 0:
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

def main():
    from sys import stdin
    S = input()
    Q = int(input())
    reverse = 0
    head = []
    tail = []
    
    for _ in [0] * Q:
        readline = stdin.readline
        s = readline().split()
        if int(s[0]) == 1:
            if reverse == 1:
                reverse = 0
            else:
                reverse = 1
        else:
            if int(s[1]) == 1:
                if reverse == 1:
                    tail.append(s[2])
                else:
                    head.insert(0, s[2])
            else:
                if reverse == 1:
                    head.insert(0, s[2])
                else:
                    tail.append(s[2])
    head = ''.join(head)
    tail = ''.join(tail)
    if reverse == 1:
        print(tail[::-1]+S[::-1]+head[::-1])
    else:
        print(head+S+tail)
        
main()

### FIXED CODE ###

def main():
    from sys import stdin
    from collections import deque
    S = input()
    Q = int(input())
    reverse = 0
    head = []
    tail = []
    head_deque = deque(head)
    tail_deque = deque(tail)
    
    for _ in [0] * Q:
        readline = stdin.readline
        s = readline().split()
        if int(s[0]) == 1:
            if reverse == 1:
                reverse = 0
            else:
                reverse = 1
        else:
            if int(s[1]) == 1:
                if reverse == 1:
                    tail.append(s[2])
                else:
                    head_deque.appendleft(s[2])
            else:
                if reverse == 1:
                    head_deque.appendleft(s[2])
                else:
                    tail.append(s[2])
    head = list(head_deque)
    head = ''.join(head)
    tail = ''.join(tail)
    if reverse == 1:
        print(tail[::-1]+S[::-1]+head[::-1])
    else:
        print(head+S+tail)
        
main()
### BUGGY CODE ###

def main():
    import sys
    input = sys.stdin.buffer.readline

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

    c1, c2, c3 = 0, 0, 0
    for aa in a:
        if aa == 1:
            c1 += 1
        elif aa == 2:
            c2 += 1
        else:
            c3 += 1

    dp = [[[0]*(N+1) for _ in range(N+1)] for _ in range(N+1)]

    # メモ化再帰ではpypy3でもTLEするのでforループを使う
    # j==k==0の場合を計算 → k==0の場合を計算 → 一般の場合を計算
    for k in range(c3+1):
        for j in range(c3+c2-k+1):
            for i in range(N-j-k+1):
                if i == j == k == 0:
                    continue
                else:
                    tmp = N
                    if i > 0: # IndexError防止
                        tmp += dp[i-1][j][k]*i
                    if j > 0:
                        tmp += dp[i+1][j-1][k]*j
                    if k > 0:
                        tmp += dp[i][j+1][k-1]*k
                    dp[i][j][k] = tmp/(i+j+k) # 割り算をまとめないとTLE

    print(dp[c1][c2][c3])

if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    from collections import Counter

    N = int(input())
    a = list(map(float, input().split()))

    dp = [[[0]*(N+1) for _ in range(N+1)] for _ in range(N+1)]
    c = Counter(a)

    # メモ化再帰ではpypy3でもTLEするのでforループを使う
    # j==k==0の場合を計算 → k==0の場合を計算 → 一般の場合を計算
    for k in range(c[3]+1):
        for j in range(c[3]+c[2]-k+1):
            for i in range(N-j-k+1):
                if i+j+k == 0:
                    continue
                else:
                    tmp = N
                    if i > 0: # IndexError防止
                        tmp += dp[i-1][j][k]*i
                    if j > 0:
                        tmp += dp[i+1][j-1][k]*j
                    if k > 0:
                        tmp += dp[i][j+1][k-1]*k
                    dp[i][j][k] = tmp/(i+j+k) # 割り算をまとめないとTLE

    print(dp[c[1]][c[2]][c[3]])

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

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

dp = [0] * (N + 1)

dp[0] = 0
dp[1] = abs(h[0] - h[1])

for n in range(1, N):
    mi = 999999999999
    for k in range(1, K + 1):
        if n - k >= 0:
            t = dp[n - k] + abs(h[n - k] - h[n])
            mi = min(mi, t)
    dp[n] = mi

print(dp[N - 1])


### FIXED CODE ###

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

dp = [0] * (N + 1)

dp[0] = 0
dp[1] = abs(h[0] - h[1])

for n in range(1, N):
    mi = 999999999999
    for k in range(1, K + 1):
        if n - k >= 0:
            t = dp[n - k] + abs(h[n - k] - h[n])
            mi = min(mi, t)
    dp[n] = mi

print(dp[N - 1])