- Prepare
- Algorithms
- Dynamic Programming
- The Blacklist

# 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*.