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

    HackerRank

  • |
  • Prepare
  • Certify
  • Compete
  • Hiring developers?
  1. Prepare
  2. Algorithms
  3. Dynamic Programming
  4. The Blacklist

The Blacklist

Problem
Submissions
Leaderboard
Discussions
Editorial

A new gangster is trying to take control of the city. He makes a list of his adversaries (e.g. gangster , gangster , ... gangster , gangster ) and plans to get rid of them.

mercenaries are willing to do the job. The gangster can use any number of these mercenaries. But he has to honor one condition set by them: they have to be assigned in such a way that they eliminate a consecutive group of gangsters in the list, e.g. gangster , gangster , ..., gangster , gangster , where the following is true: .

While our new gangster wants to kill all of them, he also wants to pay the least amount of money. All mercenaries charge a different amount to kill different people. So he asks you to help him minimize his expenses.

Input Format

The first line contains two space-separated integers, and . Then lines follow, each containing integers as follows:
The th number on the th line is the amount charged by the th mercenary for killing the th gangster on the list.

Constraints

Output Format

Just one line, the minimum cost for killing the gangsters on the list.

Sample Input

3 2
1 4 1
2 2 2

Sample Output

 5

Explanation

The new gangster can assign mercenary 1 to kill gangster 1, and mercenary 2 to kill gangster 2 and gangster 3.

Author

vlade087

Difficulty

Advanced

Max Score

100

Submitted By

1696

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
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy