There are $n$ gold mines along a river, and each mine $i$ produces $w_i$ tons of gold. In order to collect the mined gold, we want to redistribute and consolidate it amongst exactly $k$ mines where it can be picked up by trucks. We do this according to the following rules:

You can move gold between any pair of mines (i.e., $i$ and $j$, where $1\leq i<j\leq n$).
All the gold at some pickup mine $i$ must either stay at mine $j$ or be completely moved to some other mine, $j$.
Move $w$ tons of gold between the mine at location $x_i$ and the mine at location $x_j$ at a cost of $|x_i-x_j|\times w.$.

Given $n$, $k$, and the amount of gold produced at each mine, find and print the minimum cost of consolidating the gold into $k$ pickup locations according to the above conditions.

Input Format

The first line contains two space-separated integers describing the respective values of $n$ (the number of mines) and $k$ (the number of pickup locations). 

Each line $i$ of the $n$ subsequent lines contains two space-separated integers describing the respective values of $x_i$ (the mine's distance from the mouth of the river) and $w_i$ (the amount of gold produced in tons) for mine $ia$. 

Note: It is guaranteed that the mines are will be given in order of ascending location.

Constraints

$1\leq k<n\leq5000$
$1\leq w_{i},x_{i}\leq10^{6} $

Output Format

Print a single line with the minimum cost of consolidating the mined gold amongst $k$ different pickup sites according to the rules stated above.

Sample Input 0

3 1
20 1
30 1
40 1

Sample Output 0

20

Explanation 0 

We need to consolidate the gold from $n=3$ mines into a single pickup location (because $k=1$). The mines are all equidistant and they all produce the same amount of gold, so we just move the gold from the mines at locations $x=20$ and $x=40$ to the mine at $x=30$ for a minimal cost of $20$.

Sample Input 1

3 1
11 3
12 2
13 1

Sample Input 1

4

Explanation 1 

We need to consolidate the gold from $n=3$ mines into a single pickup location (because $k=1$). We can achieve a minimum cost of $4$ by moving the gold from mines $x=12$ and $x=13$ to the mine at $x=11$.

Sample Input 2

6 2
10 15
12 17
16 18
18 13
30 10
32 1

Sample Output 2

182

Explanation 2 

We need to consolidate the gold from $n=6$ mines into $k=2$ pickup locations. We can minimize the cost of doing this by doing the following:

Move the gold from the mines at locations $x=10$, $x=16$, and $x=18$ to the mine at $x=12$.   
Move the gold from the mine at location $x=32$ to the mine at $x=30$.

Source: hackerrank | Difficulty: HARD
Tags: Dynamic programming


Solutions:
minup = input('')
L = minup.split(' ')
n = int(L[0])
k = int(L[1])
location = []
value = []
for i in range(n):
	a = input('')
	L = a.split(' ')
	location.append(int(L[0]))
	value.append(int(L[1]))
if n <= 3500:
	chasm = [0, 0]
	user = 0
	values = 0
	for i in range(n - k):
		values += value[i]
		user += values * (location[i + 1] - location[i])
		chasm.append(user)
	chasm = chasm + [0] * (n + 1 - len(chasm))
	location = [float('-inf')] + location
	value = [0] + value
	y = k - 1

	def roundi(a, b, tally, chunk, location=location, value=value):
		if luke[a][b] != -1:
			return luke[a][b]
		else:
			Sum = chunk
			for p in range(tally + 1, b):
				worth = value[p]
				if location[p] - location[a] <= location[b] - location[p]:
					tally = p
					chunk += worth * (location[p] - location[a])
					Sum = chunk
				else:
					Sum += worth * (location[b] - location[p])
			(luke[a][b], talisman[a][b], sun[a][b]) = (Sum, tally, chunk)
			return Sum
	luke = [[-1 for i in range(n + 1)] for j in range(n + 1)]
	talisman = [[j for i in range(n + 1)] for j in range(n + 1)]
	sun = [[0 for i in range(n + 1)] for j in range(n + 1)]
	charlie = [chasm, [0 for i in range(n + 1)]]
	xani = 1
	for i in range(2, k + 1):
		xani += 1
		begin = i - 1
		for j in range(i, n - y + xani):
			high = float('inf')
			for x in range(begin, j):
				tally = talisman[x][j - 1]
				chunk = sun[x][j - 1]
				z = roundi(x, j, tally, chunk) + charlie[0][x]
				if high >= z:
					index = x
					high = z
			charlie[1][j] = high
			begin = index
		(charlie[0], charlie[1]) = (charlie[1], charlie[0])
	zigzag = [[0], []]
	for i in range(k + 1, n + 1):
		zigzag[1] = [zigzag[0][x] + (location[i] - location[k + x]) * value[i] for x in range(len(zigzag[0]))]
		zigzag[1] += [charlie[0][i]]
		(zigzag[1], zigzag[0]) = (zigzag[0], zigzag[1])
	print(min(zigzag[0]))
else:
	chasm = [0, 0]
	user = 0
	values = 0
	for i in range(n - k):
		values += value[i]
		user += values * (location[i + 1] - location[i])
		chasm.append(user)
	chasm = chasm + [0] * (n + 1 - len(chasm))
	chasmal = chasm[:]
	location = [float('-inf')] + location
	value = [0] + value
	y = k - 1

	def roundi(a, b, location=location, value=value):
		if luke[a][b] != -1:
			return luke[a][b]
		else:
			Sum = sum((value[p] * min(location[p] - location[a], location[b] - location[p]) for p in range(a + 1, b)))
			luke[a][b] = Sum
			return Sum
	luke = [[-1 for i in range(n + 1)] for j in range(n + 1)]
	charlie = [chasm, [0 for i in range(n + 1)]]
	xani = 1
	for i in range(2, k + 1):
		xani += 1
		begin = i - 1
		for j in range(i, n - y + xani):
			high = float('inf')
			for x in range(begin, j):
				if high >= charlie[0][x] + roundi(x, j):
					index = x
					high = charlie[0][x] + roundi(x, j)
			charlie[1][j] = high
			begin = index
		(charlie[0], charlie[1]) = (charlie[1], charlie[0])
	zigzag = [[0], []]
	for i in range(k + 1, n + 1):
		zigzag[1] = [zigzag[0][x] + (location[i] - location[k + x]) * value[i] for x in range(len(zigzag[0]))]
		zigzag[1] += [charlie[0][i]]
		(zigzag[1], zigzag[0]) = (zigzag[0], zigzag[1])
	print(min(zigzag[0]))


minup = input('')
L = minup.split(' ')
n = int(L[0])
k = int(L[1])
location = []
value = []
for i in range(n):
	a = input('')
	L = a.split(' ')
	location.append(int(L[0]))
	value.append(int(L[1]))
if n <= 3500:
	chasm = [0, 0]
	user = 0
	values = 0
	for i in range(n - k):
		values += value[i]
		user += values * (location[i + 1] - location[i])
		chasm.append(user)
	chasm = chasm + [0] * (n + 1 - len(chasm))
	location = [float('-inf')] + location
	value = [0] + value
	y = k - 1

	def roundi(a, b, tally, chunk, location=location, value=value):
		if luke[a][b] != -1:
			return luke[a][b]
		else:
			Sum = chunk
			for p in range(tally + 1, b):
				worth = value[p]
				if location[p] - location[a] <= location[b] - location[p]:
					tally = p
					chunk += worth * (location[p] - location[a])
					Sum = chunk
				else:
					Sum += worth * (location[b] - location[p])
			(luke[a][b], talisman[a][b], sun[a][b]) = (Sum, tally, chunk)
			return Sum
	luke = [[-1 for i in range(n + 1)] for j in range(n + 1)]
	talisman = [[j for i in range(n + 1)] for j in range(n + 1)]
	sun = [[0 for i in range(n + 1)] for j in range(n + 1)]
	charlie = [chasm, [0 for i in range(n + 1)]]
	xani = 1
	for i in range(2, k + 1):
		xani += 1
		begin = i - 1
		for j in range(i, n - y + xani):
			high = float('inf')
			for x in range(begin, j):
				tally = talisman[x][j - 1]
				chunk = sun[x][j - 1]
				z = roundi(x, j, tally, chunk) + charlie[0][x]
				if high >= z:
					index = x
					high = z
			charlie[1][j] = high
			begin = index
		(charlie[0], charlie[1]) = (charlie[1], charlie[0])
	zigzag = [[0], []]
	for i in range(k + 1, n + 1):
		zigzag[1] = [zigzag[0][x] + (location[i] - location[k + x]) * value[i] for x in range(len(zigzag[0]))]
		zigzag[1] += [charlie[0][i]]
		(zigzag[1], zigzag[0]) = (zigzag[0], zigzag[1])
	print(min(zigzag[0]))
else:
	chasm = [0, 0]
	user = 0
	values = 0
	for i in range(n - k):
		values += value[i]
		user += values * (location[i + 1] - location[i])
		chasm.append(user)
	chasm = chasm + [0] * (n + 1 - len(chasm))
	chasmal = chasm[:]
	location = [float('-inf')] + location
	value = [0] + value
	y = k - 1

	def roundi(a, b, location=location, value=value):
		if luke[a][b] != -1:
			return luke[a][b]
		else:
			Sum = sum((value[p] * min(location[p] - location[a], location[b] - location[p]) for p in range(a + 1, b)))
			luke[a][b] = Sum
			return Sum
	luke = [[-1 for i in range(n + 1)] for j in range(n + 1)]
	charlie = [chasm, [0 for i in range(n + 1)]]
	xani = 1
	for i in range(2, k + 1):
		xani += 1
		begin = i - 1
		for j in range(i, n - y + xani):
			high = float('inf')
			for x in range(begin, j):
				if high >= charlie[0][x] + roundi(x, j):
					index = x
					high = charlie[0][x] + roundi(x, j)
			charlie[1][j] = high
			begin = index
		(charlie[0], charlie[1]) = (charlie[1], charlie[0])
	zigzag = [[0], []]
	for i in range(k + 1, n + 1):
		zigzag[1] = [zigzag[0][x] + (location[i] - location[k + x]) * value[i] for x in range(len(zigzag[0]))]
		zigzag[1] += [charlie[0][i]]
		(zigzag[1], zigzag[0]) = (zigzag[0], zigzag[1])
	print(min(zigzag[0]))