Harryxun/stf_run huggingface dataset:
S = list(map(int,input().split()))
N = S[0]
K = S[1]
X = list(map(int,input().split()))

Xnegative = [abs(x) for x in X if x < 0]
Xpositive = [x for x in X if x >= 0]
Xnegative = sorted(Xnegative)

i = 0

if len(Xpositive) >= K:
    sub = Xpositive[K-1]
    while i < len(Xnegative) and K-i-2 >= 0:
        distance = min(Xnegative[i],Xpositive[K-2-i]) + Xnegative[i] + Xpositive[K-2-i]
        if sub > distance:
            sub = distance
        i = i + 1
elif len(Xpositive) == 0:
    sub = Xnegative[K-1]
else:
    l = K-len(Xpositive)
    sub = min(Xnegative[l-1],Xpositive[-1]) + Xnegative[l-1] + Xpositive[-1]
    while i + l < len(Xnegative) and i-2 < len(Xpositive):
        distance = max(Xnegative[i+l],Xpositive[-i-2]) + Xnegative[i+l] + Xpositive[-i-2]
        if sub > distance:
            sub = distance
        i = i + 1

print(sub)

### FIXED CODE ###

S = list(map(int,input().split()))
N = S[0]
K = S[1]
X = list(map(int,input().split()))

Xnegative = [abs(x) for x in X if x < 0]
Xpositive = [x for x in X if x >= 0]
Xnegative = sorted(Xnegative)

i = 0

if len(Xpositive) >= K:
    sub = Xpositive[K-1]
    while i < len(Xnegative) and K-i-2 >= 0:
        distance = min(Xnegative[i],Xpositive[K-2-i]) + Xnegative[i] + Xpositive[K-2-i]
        if sub > distance:
            sub = distance
        i = i + 1
elif len(Xpositive) == 0:
    sub = Xnegative[K-1]
else:
    l = K-len(Xpositive)
    sub = min(Xnegative[l-1],Xpositive[-1]) + Xnegative[l-1] + Xpositive[-1]
    while i + l < len(Xnegative) and -i-2 >= -len(Xpositive):
        distance = min(Xnegative[i+l],Xpositive[-i-2]) + Xnegative[i+l] + Xpositive[-i-2]
        if sub > distance:
            sub = distance
        i = i + 1

print(sub)
k = int(input())

a=[1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]

print(a[K-1])

### FIXED CODE ###

k = int(input())

a=[1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]

print(a[k-1])
from math import factorial
n,m = map(int,input().split())

N = factorial(n)/factorial(2)/factorial(n-2)
M = factorial(m)/factorial(2)/factorial(m-2)

print(N+M)


### FIXED CODE ###

from math import factorial
n,m = map(int,input().split())

if n == 0:
   N = 0
elif n == 1:
    N = 0
else:
    N = factorial(n)/factorial(2)/factorial(n-2)
if m == 0:
   M = 0
elif m == 1:
    M = 0
else:
    M = factorial(m)/factorial(2)/factorial(m-2)

print(int(N+M))
N=int(input())
G=[[]for i in range(N)]

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

ans=[-1]*N
#ルートでは親はいないから-1
def dfs(v,p,c):
    ans[v]=c
    for u,w in G[v]:
        if u==p:
            continue
        if w%2==0:
            dfs(u,v,c)
        else:
            dfs(u,v,1-c)
dfs(0,-1,1)
for i in range(N):
    print(ans[i])

### FIXED CODE ###

import sys
 
n = int(input())
links = [set() for _ in [0] * n]
for line in sys.stdin:
    u, v, w = map(int, line.split())
    u -= 1
    v -= 1
    links[u].add((v, w))
    links[v].add((u, w))
ans = [-1] * n
q = [(0, 0, -1)]
while q:
    v, d, p = q.pop()
    if d % 2 == 0:
        ans[v] = 0
    else:
        ans[v] = 1
    for u, w in links[v]:
        if u == p:
            continue
        q.append((u, d + w, v))
print('\n'.join(map(str, ans)))
import math
from functools import reduce

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

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

ans = []
if len(a) != 1:
    ans.append(gcd(a[1:]))
    ans.append(gcd(a[:n]))

    for i in range(1, n-1):
        aaaa = []
        aaaa.append(gcd(a[:i]))
        aaaa.append(gcd(a[i+1:]))
        ans.append(gcd(aaaa))
else:
    ans.append(a[0])
    
print(max(ans))


### FIXED CODE ###

from math import gcd

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

L = [0] * N
L[0] = A[0]

#配列の左から順番に最大公約数を求める
for i, a in enumerate(A):
    L[i] = gcd(L[max(0, i-1)], a)

# print("L", L)
R = [0] * N
R[0] = A[-1]

#配列の右から順番に最大公約数を求める
for i, a in enumerate(A[::-1]):
    R[i] = gcd(R[max(0, i-1)], a)

# print("R", R)
ans = 0

for i in range(N):
    #一番左の数字を削除
    if i == 0:
        ans = max(ans, R[N-2])
    #一番右の数字を削除
    elif i == N-1:
        ans = max(ans, L[N-2])
    #i+1番目の数字を削除
    else:
        ans = max(ans, gcd(L[i-1], R[N-i-2]))
    
print(ans)
n=int(input())
nlist=[input() for i in range(n)]
m=int(input())
mlist=[input() for i in range(m)]
set1=set(nlist)
print(mlist)
print(max(0,max(nlist.count(set1[i])-mlist.count(set1[i]) for i in len(set1))))

### FIXED CODE ###

#n=[input() for _ in range(int(input()))]
#m=[input() for _ in range(int(input()))]
n1=int(input())
n=[input() for i in range(n1)]
m1=int(input())
m=[input() for i in range(m1)]
#print(n)
#print(m)
l=list(set(n))
#print(l)
print(max(0,max(n.count(l[i])-m.count(l[i]) for i in range(len(l)))))
#print(max(0,max(n.count(l[i])-m.count(l[i]) for i in range(len(l)))))
A, B = map(int,input().split())
def Eratosthenes(n):
    if n == 1:
      return [1]
    if n == 2:
      return [1, 2]
    dp = [False]*n
    dp[0] = dp[1] = True
    prime = []
    l = []
    for i in range(2, n):
        if dp[i]:
            continue
        prime.append(i)
        if n%i == 0:
          l.append(i)
        for j in range(i*2, n, i):
            dp[j] = True
            i += 1
    return l
print(len(set(Eratosthenes(A))&set(Eratosthenes(B)))+1)


### FIXED CODE ###

A, B = map(int,input().split())
def factorization(n):
    if n == 1:
      return [1]
    elif n == 2:
      return [1, 2]
    arr = [1]
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append(i)
    if temp!=1:
        arr.append(temp)
    if arr==[]:
        arr.append(n)
    return arr
print(len(set(factorization(A))&set(factorization(B))))
n = input()

A = map(int, raw_input().split())
 
q = input()
 
m = map(int, raw_input().split())

for i in m:
  for j in range(n):
    if A[-j] <= i
      i = i - A[-j]
    if i <= 0:
      break
  if i == 0:
    print "yes"
  else:
    print "no"

### FIXED CODE ###

n = input()

A = map(int, raw_input().split())
   
q = input()
   
M = map(int, raw_input().split())
  
def solve(i, m):
  if m == 0:
    return True
  if i >= n or m > sum(A):
    return False
  res = solve(i+1, m) or solve(i+1, m - A[i])
  return res
  
  
for m in M:
  if solve(0,m):
    print "yes"
  else:
    print "no"
from operator import mul
from functools import reduce

def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under
n,m=map(int,input().split())
if n<2 and m<2:
    print(0)
    quit()
if n==0:
    print(cmb(m,2))
    quit()
elif m==0:
    print(cmb(n,2))
    quit()
print(cmb(n,2)+cmb(m,2))

### FIXED CODE ###

n,m=map(int,input().split())
print((n*(n-1))//2+(m*(m-1))//2)
C,D = [int(e) for e in input().split()]

if C <= D:
    m = D
    n = C
else:
    m = C
    n = D

while  n != 0 :
    a = m%n
    m = n
    n = a

J = []

for i in range(1,int(m**0.5)+1):
    if m % i == 0:
        J.append(i)
        if i != m//i:
            J.append(m//i)


J.sort()

N = int(len(J))
M = [1]

for i in range(1,N):
   cnt = 0
   for p in range(1,int(J[i]**0.5)+1):
       if J[i]%p == 0:
           cnt += 1
           if cnt >=2:
               break
    if cnt == 1:
        M.extend([J[i]])


M = int(len(M))

print(M)

### FIXED CODE ###

C,D = [int(e) for e in input().split()]

if C <= D:
    m = D
    n = C
else:
    m = C
    n = D

while  n != 0 :
    a = m%n
    m = n
    n = a

J = []

for i in range(1,int(m**0.5)+1):
    if m % i == 0:
        J.append(i)
        if i != m//i:
            J.append(m//i)


J.sort()

N = int(len(J))
M = [1]
I = []

for i in range(1,N):
    for p in range(1,int(J[i]**0.5)+1):
        if J[i]%p == 0:
            I.extend([J[i]])
            if int(len(I)) >=2:
                break
    if int(len(I)) == 1:
        M.extend([J[i]])
    I = []


M = int(len(M))

print(M)
def gu(n,a):
  ans=[0]*n
  for i in len(len(a)):
    ii=a[i]
    while True:
      if ii%2==0:
        ans[i]+=1
      else:
        break
  return ans.min()
n=int(input())
a=list(map(int,input().split()))
print(gu(n,a))
def gu(n,a):
  ans=[0]*n
  for i in range(len(a)):
    ii=a[i]
    while True:
      if ii%2==0:
        ans[i]+=1
      else:
        break
  return ans.min()
n=int(input())
a=list(map(int,input().split()))
print(gu(n,a))


### FIXED CODE ###

def count_1(a):
  c=0
  for i in a:
    if i=="1":
      c+=1
  else:
    return c
a=input()
print(count_1(a))
a = int(input().split())
b = int(input().split())
c = a[0] * b[1]
d = a[1] * b[0]
print(a[0] * a[1] - (c + d - b[0] * b[1]))

### FIXED CODE ###

a = input().split()
b = input().split()
a = list(map(int, a))
b = list(map(int, b))
c = a[0] * b[1]
d = a[1] * b[0]
print(a[0] * a[1] - (c + d - b[0] * b[1]))
from math import gcd

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

if n == 1:
	if n == k:
		print("POSSIBLE")
	else:
		print("IMPOSSIBLE")
else:
	if k in a:
		print("POSSIBLE")
	elif k > max(a):
		print("IMPOSSIBLE")
	else:
		g = gcd(a[0], a[1])
		for i in range(2, n):
			g = gcd(g, a[i])

		if k % g == 0:
			print("POSSIBLE")
		else:
			print("IMPOSSIBLE")

### FIXED CODE ###

from fractions import gcd

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

if n == 1:
	if a[0] == k:
		print("POSSIBLE")
	else:
		print("IMPOSSIBLE")
else:
	if k in a:
		print("POSSIBLE")
	elif k > max(a):
		print("IMPOSSIBLE")
	else:
		g = gcd(a[0], a[1])
		for i in range(2, n):
			g = gcd(g, a[i])

		if k % g == 0:
			print("POSSIBLE")
		else:
			print("IMPOSSIBLE")
#!/usr/bin/env python3.4
# -*- coding: utf-8 -*-

# abc126_d

from collections import namedtuple

DistFrom = namedtuple('DistFrom', ['f', 'dist'])

def main():
    # input
    n, = [int(s) for s in input().split()]
    fs = [[int(s) for s in input().split()] for _ in range(n-1)]
    # getans
    getters = [None] * n
    for i in range(n):
        getters[i] = list()
    for x, y, d in fs:
        x -= 1
        y -= 1
        getters[x].append(DistFrom(y, d))
        getters[y].append(DistFrom(x, d))
    dists = [-1] * n
    def search(cur_i, prev, dist):
        dists[cur_i] = dist
        for i, d in getters[cur_i]:
            if i == prev: continue
            search(i, cur_i, dist+d)
    dists[0] = 0
    for i, d in getters[0]:
        search(i, 0, d)
    ans = [d%2 for d in dists]
    # output
    for a in ans:
        print(a)

if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
 
sys.setrecursionlimit(10**5)

n = int(input())
p = [list() for _ in range(n)]
for i in range(n-1):
    u, v, w = [int(s) for s in input().split()]
    u -= 1
    v -= 1
    w %= 2
    p[u].append((v, w))
    p[v].append((u, w))

costs = [-1 for _ in range(n)]

def dfs(cur, dist):
    if costs[cur] != -1:
        return
    costs[cur] = dist
    for v, d in p[cur]:
        dfs(v, dist^d)
dfs(0, 0)

for i in range(n):
    print(costs[i])
n, m = map(int, input().split())
h = list(map(int, input().split()))
p = [False] + [True]*n
A = []
B = []
for i in range(m):
    a, b = map(int,input().split())
    A.append(a)
    B.append(b)

for i in range(m):
    if h[A[i] - 1] > h[B[i] - 1]:
        p[B[i]] = False
    if h[A[i] - 1] < h[B[i] - 1]:
        p[A[i]] = False
    if h[A[i] - 1] == h[B[i] - 1]:
        p[A[i]] = False
        p[B[i]] = False
    print(p)
ans = [i for i in range(n + 1) if p[i]]

print(len(ans))


### FIXED CODE ###

n, m = map(int, input().split())
h = list(map(int, input().split()))
p = [False] + [True]*n
A = []
B = []
for i in range(m):
    a, b = map(int,input().split())
    A.append(a)
    B.append(b)

for i in range(m):
    if h[A[i] - 1] > h[B[i] - 1]:
        p[B[i]] = False
    if h[A[i] - 1] < h[B[i] - 1]:
        p[A[i]] = False
    if h[A[i] - 1] == h[B[i] - 1]:
        p[A[i]] = False
        p[B[i]] = False
    
ans = [i for i in range(n + 1) if p[i]]

print(len(ans))
n=int(input())
 
import math
from functools import reduce
 
def gcd(*numbers):
    return reduce(math.gcd, numbers)
 
  
ans=0
k=0
for a in range(1,n+1):
    for b in range(1,n+1):
      k=gcd(a,b)
        for c in range(1,n+1):
            ans+=gcd(k,c)  
print(ans)

### FIXED CODE ###

n=int(input())
 
import math
from functools import reduce
 
def gcd(*numbers):
    return reduce(math.gcd, numbers)
 
  
ans=0
for a in range(1,n+1):
    for b in range(1,n+1):
        for c in range(1,n+1):
            
            ans+=gcd(a,b,c)  
print(ans)
#!python3

import sys
iim = lambda: map(int, sys.stdin.readline().rstrip().split())
from heapq import heappush, heappushpop

def resolve():
    it = map(int, sys.stdin.read().split())

    T = next(it)
    if T == 3:
        raise 1
    ans = []
    for i in range(T):
        N = next(it)

        val = 0
        a1 = [[] for i in range(N)];
        a2 = [[] for i in range(N)];
        for i, v1, v2 in ((next(it)-1, next(it), next(it)) for i in range(N)):
            diff = v1 - v2
            if diff == 0 or i == N-1:
                val += v1
            elif diff > 0:
                a1[i].append(diff)
                val += v2
            else:
                i = N-1-i-1
                a2[i].append(-diff)
                val += v1

        for ax in (a1, a2):
            dq = []
            for i, aa in enumerate(ax):
                if not aa: continue
                for diff in aa:
                    ld = len(dq)
                    if ld <= i:
                        heappush(dq, diff)
                        val += diff
                    else:
                        df = heappushpop(dq, diff)
                        val += diff - df

        ans.append(val)


    print(*ans, sep="\n")



if __name__ == "__main__":
    resolve()


### FIXED CODE ###

#!python3

import sys
iim = lambda: map(int, sys.stdin.readline().rstrip().split())
sys.setrecursionlimit(1000000000)

def resolve():
    it = map(int, sys.stdin.read().split())

    T = next(it)
    ans = []
    for i in range(T):
        N = next(it)

        val = 0; a1 = []; a2 = []
        for i, v1, v2 in ((next(it), next(it), next(it)) for i in range(N)):
            diff = v1 - v2
            a, v, diff = (a1, v2, diff) if diff >= 0 else (a2, v1, -diff)
            a.append((diff, i))
            val += v
        a1.sort(reverse=True); a2.sort(reverse=True)

        ls = len(a1)
        vis = [None]*(N+1)
        def root(x):
            if vis[x] == None: return x

            vis[x] = root(vis[x])
            return vis[x]
        def root(x):
            a = []
            while True:
                y = vis[x]
                if y == None:
                    break
                a.append(x)
                x = y
            for i in a:
                vis[i] = x
            return x

        for diff, i in a1:
            j = min(i, ls) - 1
            k = root(j)
            #print(diff, i, j, k,  vis)
            if k < 0: continue
            val += diff
            vis[k] = k - 1


        for diff, i in a2:
            j, v2 = max(i, ls), [[-1]]
            k = root(j)
            #print(diff, i, j, k,  vis)
            if k >= N: continue
            val += diff
            vis[k] = k + 1

        ans.append(val)

    print(*ans, sep="\n")



if __name__ == "__main__":
    resolve()
n, m = int(input().split())
answer = (-1, -1, -1,) # (１万円, 五千円, 千円,)
for x in range(n+1): # 一万円の枚数　０－９
    for y in range(n+1): # 五千円の枚数 ０－９
        z = n - x - y # 千円の枚数　０－９
        if 0 <= z <= 2000 and 10000 * x + 5000 * y + 1000 * z == m:
            answer = (x, y, z,)
            break
        else:
            continue
        break
print(*answer)

### FIXED CODE ###

N,Y=map(int,input().split())
answer=-1,-1,-1
for x in range(N+1):
    for y in range(N-x+1):
        z=N-x-y
        if 0<=z<=2000 and 10000*x+5000*y+1000*z==Y:
            answer=x,y,z
            break
    else:
        continue
    break
print(*answer)
n = int(input())
arr = []
for i in range(n-1):
    arr.append([int(s) for s in input().split(" ")])

# n = 9
# arr = [
#     [1,2],
#     [1,6],
#     [2,8],
#     [2,3],
#     [2,7],
#     [3,9],
#     [3,4],
#     [4,5],
# ]

childNodeNums = [0 for i in range(n)]
childNodeStatus = [-1 for i in range(n)]
nodeLines = [[] for i in range(n - 1)]


def prepare(n, arr):
    s = [[] for i in range(n)]
    for ar in arr:
        s[ar[0] - 1].append(ar[1] - 1)
        s[ar[1] - 1].append(ar[0] - 1)
    return s


# x为记录入边的颜色
def dfs(currentNode, arr, x):
    m1 = childNodeNums
    m2 = childNodeStatus
    childNodes = arr[currentNode]
    if len(childNodes) == 0:
        return

    childNodeNums[currentNode] = childNodeNums[currentNode] + len(arr[currentNode])
    childNodeStatus[currentNode] = 1

    kk = 0
    for i, childNodeIndex in enumerate(childNodes):

        if childNodeStatus[childNodeIndex] == -1:
            kk = kk + 1
            if x == kk:
                kk = kk + 1
            nodeLines[currentNode].append(kk)
            dfs(childNodeIndex, arr, kk)



data = prepare(n, arr)
dfs(0, data, -1)

print(max(childNodeNums))

for ar in nodeLines:
    for a in ar:
        print(a)


### FIXED CODE ###

from sys import setrecursionlimit


def genid(a, b):
    if b < a:
        a, b = b, a
    return a * 100000 + b


def paint(currentNode, usedColor, parentNode, edges, colors):
    color = 1
    for childNode in edges[currentNode]:
        if childNode == parentNode:
            continue
        if color == usedColor:
            color += 1
        colors[genid(currentNode, childNode)] = color
        paint(childNode, color, currentNode, edges, colors)
        color += 1


setrecursionlimit(100000)

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

edges = [[] for _ in range(N)]
for a, b in ab:
    edges[a - 1].append(b - 1)
    edges[b - 1].append(a - 1)

colors = {}
paint(0, -1, -1, edges, colors)

print(max(len(e) for e in edges))
for a, b in ab:
    print(colors[genid(a - 1, b - 1)])
n=int(input())
#n,k=map(int,input().split())
v=list(map(int,input().split()))
l=list()
for i in v:
  if i not in l:
    l.append(i)
n=len(l)
d=list()
if l[0]>l[1]:
    d.append(l[0])
if l[0]<l[1]:
    d.append(l[0])
for i in range(1,n-1):
  if l[i-1]<l[i] and l[i+1]<l[i]:
    d.append(l[i])
  if l[i-1]>l[i] and l[i+1]>l[i]:
    d.append(l[i])
if l[-1]>l[-2]:
    d.append(l[-1])
if l[-1]<l[-2]:
    d.append(l[-1])
#print(d)
n=len(d)
p=1000
for i in range(1,n):
  if l[i-1]<l[i]:
    z=(p//l[i-1])*l[i]
    r=p%l[i-1]
    p=z+r
print(p)
    




### FIXED CODE ###

n=int(input())
#n,k=map(int,input().split())
v=list(map(int,input().split()))
l=list()
prev=0
for i in v:
  if prev!=i:
    l.append(i)
    prev=i
n=len(l)
if n==1:
  print(1000)
else: 
  d=list()
  if l[0]>l[1]:
      d.append(l[0])
  if l[0]<l[1]:
      d.append(l[0])
  for i in range(1,n-1):
    if l[i-1]<l[i] and l[i+1]<l[i]:
      d.append(l[i])
    if l[i-1]>l[i] and l[i+1]>l[i]:
      d.append(l[i])
  if l[-1]>l[-2]:
      d.append(l[-1])
  if l[-1]<l[-2]:
      d.append(l[-1])
  #print(d)
  n=len(d)
  p=1000
  if n>1:
    i=1
    while(i<n):
      if d[i-1]<d[i]:
        z=(p//d[i-1])*d[i]
        r=p%d[i-1]
        i+=2
        if z+r>p:
        	p=z+r
      else:
        i+=1
    print(p)
  else:
    print(p)
n, k, c = map(int, input().split())
S = input()
pre = [0]*n
pre[0] = 1 if S[0] == "o" else 0
for i in range(1, n):
    if S[i] == "o" and i-c-1 >= 0:
        pre[i] = max(pre[i-1], pre[i-c-1]+1)
    else:
        pre[i] = pre[i-1]

suf = [0]*n
suf[-1] = 1 if S[-1] == "o" else 0
for i in range(n-2, -1, -1):
    if S[i] == "o" and i+c+1 < n:
        suf[i] = max(suf[i+1], suf[i+c+1]+1)
    else:
        suf[i] = suf[i+1]

# print(pre)
# print(suf)

if S[0] == "o" and suf[1] < k:
    print(1)

for i in range(1, n-1):
    if S[i] == "o" and pre[i-1]+suf[i+1] < k:
        print(i+1)

if S[-1] == "o" and pre[-2] < k:
    print(n)


### FIXED CODE ###

import sys
from collections import defaultdict, Counter, namedtuple, deque
import itertools
import functools
import bisect
import heapq
import math

MOD = 10 ** 9 + 7
# MOD = 998244353
# sys.setrecursionlimit(10**8)

n, k, c = map(int, input().split())
s = input()
left = [-1]*k
right = [-1]*k

d = w = 0
while w < k:
    if s[d] == "o":
        left[w] = d
        w += 1
        d += c+1
    else:
        d += 1

d, w = n-1, k-1
while w >= 0:
    if s[d] == "o":
        right[w] = d
        w -= 1
        d -= c+1
    else:
        d -= 1

# print(left, right)
for i in range(k):
    if left[i] == right[i]:
        print(left[i]+1)
import numpy as np
import bisect

n, m  = list(map(int, input().split()))
drinks = [list(map(int, input().split())) for _ in range(n)]

drinks.sort(key = lambda x: x[0])
prices = np.array([x[0] for x in drinks])
vols = np.array([x[1] for x in drinks])
cum_vols = np.cumsum(vols)
idx = bisect.bisect_right(cum_vols, m) #このidxは1 ~ vols[idx]を使う

vols[idx] = m - sum(vols[:idx])
print(np.dot(vols[:(idx+1)], prices[:(idx+1)]))


### FIXED CODE ###

import numpy as np
import bisect

n, m  = list(map(int, input().split()))
drinks = [list(map(int, input().split())) for _ in range(n)]

drinks.sort(key = lambda x: x[0])
prices = np.array([x[0] for x in drinks])
vols = np.array([x[1] for x in drinks])
cum_vols = np.cumsum(vols)
idx = bisect.bisect_left(cum_vols, m) #このidxは1 ~ vols[idx]を使う

#print(idx)
l = 0 if idx == 0 else sum(vols[:idx])

vols[idx] = m - l
print(np.dot(vols[:(idx+1)], prices[:(idx+1)]))
# -*- coding: utf-8 -*-
"""
Created on Sun Jul 21 23:25:47 2019

@author: Yamazaki Kenichi
"""
import bisect

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

T = [[] for _ in range(2*10**5+1)]
appearing = [0 for _ in range(2*10**5+1) ]

for i in range(N):
    c = A[i]
#    T[c][0] += 1
    T[c].append(i)

q = [A[0]]
pointa = 0
counta, res = 0, []
while q:
    s = q.pop()
    tmp = bisect.bisect_left(T[s], pointa) + 1
    tmp %= len(T[s])
    p_pointa = pointa
    pointa = T[s][tmp] + 1
#    print(s,tmp,pointa)
#    ans.append([s,tmp,pointa])
    if pointa == p_pointa + 1 or pointa < p_pointa:
        counta += 1
        res.append(p_pointa)
    if pointa == N:
        break
    next_s = A[pointa]
    q.append(next_s)

counta += 1
ans = []
if K % counta != 0:
    tmp = res[K % counta] + 1
    ans.append(A[tmp+1])
    for i in range(tmp + 1,N):
        if ans[0] == A[i]:
            ans = []
        else:
            ans.append(A[i])
        print(ans)
print(' '.join(map(str,ans)))


### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
Created on Sun Jul 21 23:25:47 2019

@author: Yamazaki Kenichi
"""
import bisect

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

T = [[] for _ in range(2*10**5+1)]

for i in range(N):
    T[A[i]].append(i)

s = A[0]
pointa = 0
counta, res = 0, [-1]
while True:
    tmp = bisect.bisect_right(T[s], pointa) % len(T[s])
    p_pointa = pointa
    pointa = T[s][tmp] + 1
    if pointa == p_pointa + 1 or pointa < p_pointa:
        counta += 1
        res.append(p_pointa)
    if pointa == N:
        counta += 1
        res.append(p_pointa)
        break
    s = A[pointa]

ans = []
if K % counta != 0:
    pointa = res[K % counta]
#    ans.append(A[pointa])
    while pointa < N:
        if pointa < T[A[pointa]][-1]:
            tmp = bisect.bisect_right(T[A[pointa]],pointa)
            pointa = T[A[pointa]][tmp] + 1
        else:
            ans.append(A[pointa])
            pointa += 1
#        print(ans)
print(' '.join(map(str,ans)))
import numpy as np
x = map(int, (raw_input()).split(" "))

print np.sqrt((x[2]-x[0])*(x[2]-x[0]) + (x[3]-x[1])*(x[3]-x[1]))

### FIXED CODE ###

import math
x = map(float, (raw_input()).split(" "))

print math.sqrt((x[2]-x[0])*(x[2]-x[0]) + (x[3]-x[1])*(x[3]-x[1]))