We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  • HackerRank Home
  • |
  • Prepare
  • Certify
  • Compete
  • Apply
  • Hiring developers?
  1. Prepare
  2. Algorithms
  3. Dynamic Programming
  4. Mining

Mining

Problem
Submissions
Leaderboard
Discussions
Editorial

There are gold mines along a river, and each mine produces tons of gold. In order to collect the mined gold, we want to redistribute and consolidate it amongst exactly 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., and , where ).
  • All the gold at some pickup mine must either stay at mine or be completely moved to some other mine, .
  • Move tons of gold between the mine at location and the mine at location at a cost of .

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

Input Format

The first line contains two space-separated integers describing the respective values of (the number of mines) and (the number of pickup locations).
Each line of the subsequent lines contains two space-separated integers describing the respective values of (the mine's distance from the mouth of the river) and (the amount of gold produced in tons) for mine .

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

Constraints

Output Format

Print a single line with the minimum cost of consolidating the mined gold amongst 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 mines into a single pickup location (because ). 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 and to the mine at for a minimal cost of .

Sample Input 1

3 1
11 3
12 2
13 1

Sample Input 1

4

Explanation 1
We need to consolidate the gold from mines into a single pickup location (because ). We can achieve a minimum cost of by moving the gold from mines and to the mine at .

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 mines into pickup locations. We can minimize the cost of doing this by doing the following:

  1. Move the gold from the mines at locations , , and to the mine at .
  2. Move the gold from the mine at location to the mine at .

Author

shaka_shadows

Difficulty

Advanced

Max Score

75

Submitted By

1377

Need Help?


View discussions
View editorial
View top submissions

rate this challenge

MORE DETAILS

Download problem statement
Download sample test cases
Suggest Edits
  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Helpdesk
  • Careers
  • Terms Of Service
  • Privacy Policy

Cookie support is required to access HackerRank

Seems like cookies are disabled on this browser, please enable them to open this website