Mingming's Discount Dilemma

Mingming is celebrating his birthday and wants to buy B different items. Normally, each item costs A yuan. However, the store currently has a promotion: if you buy the i^th item and then the j^th item, you pay only \(K_{i,j}\) yuan for the second item (where \(K_{i,j} = K_{j,i}\)). Thus, if you purchase items in a certain order, the total cost will be:

[ \text{Total Cost} = A + \sum_{r=2}^{B} \min\left(A, K_{i_{r-1},i_r}\right) ]

Your task is to determine the minimum total cost to buy all B items. Note that for the first item you always pay the full price \(A\), and for each subsequent item you have the option to pay \(A\) or if available, take advantage of the discount (if \(K_{i,j} < A\)).

inputFormat

The first line contains two integers \(A\) and \(B\) (the regular price and the number of items). Following this are B lines, each containing B integers. The j^th number in the i^th line represents \(K_{i,j}\) (the discounted price when buying item j immediately after item i). It is guaranteed that \(K_{i,j} = K_{j,i}\) and values on the diagonal are given but not used.

outputFormat

Output the minimum total cost to purchase all B items.

sample

10 3
0 7 11
7 0 9
11 9 0

26