Computers

Time limit1sMemory limit128 MB

Summary

Given a fixed replacement cost and arbitrary maintenance costs for owning a computer over any year range, find the minimum total cost to cover n years using dynamic programming.

Level: Medium5 of 10
Topics: Dynamic programming, Array
Solved: No attempts yet

Problem

Everybody likes computers, but buying a new one is always a financial challenge. Fortunately there is a convenient trade-off: you may replace your computer with a brand-new one and save on maintenance, but you must pay a fixed cost for every new computer you buy.

You want to own a computer during a period of n consecutive years. You always own exactly one computer, and you must own one in year 1, so a computer is certainly bought in year 1. Whenever you buy a computer you pay the fixed cost c. If a computer is bought in year y and kept until year z (y ≤ z ≤ n), then owning it over the years y through z costs an additional maintenance m(y, z); at the start of year z + 1 you may replace it with a new one.

Compute the minimum total cost of owning a computer throughout the n-year period.

Input

Input is read from standard input and may contain several data sets; it ends at end of file. Each data set describes one instance. A data set begins with the fixed cost c of buying a new computer, followed by the number of years n, followed by the maintenance costs m(y, z) for y = 1 … n and z = y … n, listed in that order (all values for y = 1 first, then those for y = 2, and so on). White space may appear freely between the numbers, and all input is correct.

Output

For each data set, print the minimum cost of owning a computer throughout the n-year period on its own line.

Examples4

Example 1
Input
```
3
3
5 7 50
6 8
10
```
Expected output
```
19
```
Example 2
Input
```
5
1
10
```
Expected output
```
15
```
Example 3
Input
```
10
2
1 2
1
```
Expected output
```
12
```
Example 4
Input
```
1
2
1 100
1
```
Expected output
```
4
```