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.