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.
  1. Prepare
  2. Algorithms
  3. Dynamic Programming
  4. The Blacklist

The Blacklist

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.