P1194 Buying Gifts

It is Mingming’s birthday again. Mingming wants to buy $B$ kinds of items, and coincidentally, each of these $B$ items is priced at $A$ yuan. However, the shop owner says there is a promotion: If you have bought item $I$, then when you buy item $J$, you only need to pay $K_{I,J}$ yuan. Moreover, $K_{I,J}$ happens to equal $K_{J,I}$. Now Mingming wants to know the minimum amount of money he has to spend.

The first line contains two integers, $A,B$. Then there are $B$ lines, each containing $B$ numbers. The $I$-th line and $J$-th number is $K_{I,J}$. We guarantee $K_{I,J}=K_{J,I}$ and $K_{I,I}=0$. In particular, if $K_{I,J}=0$, it means there is no discount between these two items. Note that $K_{I,J}$ may be greater than $A$.

Output a single integer, the minimum total amount of money required.

Explanation for Sample $2$. Buy item $2$ first, spending 3 yuan. Then, due to the promotion, buying items $1$ and $3$ each costs 2 yuan, for a total of 7 yuan. (When multiple “discounts” apply at the same time, clever Mingming will of course not choose to pay 4 yuan for the remaining one, but choose to pay 2 yuan.) Constraints For $30\%$ of the testdata, $1\le B\le 10$. For $100\%$ of the testdata, $1\le B\le500,0\le A,K_{I,J}\le1000$. Added one more set of testdata on 2018.7.25. Translated by ChatGPT 5