买礼物

背景故事

又到了明明的生日。为了犒劳自己，他计划入手 \(B\) 样心仪的小物件。每样单独买都要 \(A\) 元。不过店家最近在做"连带购买"的促销：在已买过某一件商品的前提下，再去买另一件时，可能以特价入手。

你的任务是：在所有可能的购买顺序中，求出完成全部 \(B\) 件购买所需的最小总花费。

规则说明

• 一共有 \(B\) 件商品（从 1 到 \(B\) 编号），单独买任意一件的价格都是 \(A\) 元。
• 若你已经买过第 \(I\) 件，再买第 \(J\) 件，可选择支付 \(K_{I,J}\) 元（促销价）。并且满足 \(K_{I,J}=K_{J,I}\)。

• 特别地，若 \(K_{I,J}=0\)，表示这两件之间没有任何优惠关系（并不是 0 元购买！）。此时买第 \(J\) 件仍需按常规方式：

  • 要么直接以 \(A\) 元购买；
  • 要么依赖其他已购商品与 \(J\) 形成的优惠（若存在）。
• 促销价 可能大于 原价 \(A\)。如果 \(K_{I,J} > A\)，你当然可以选择直接以 \(A\) 元购买更划算。

你的目标是选择一个最优购买顺序，并在每一步自由选择"用谁触发优惠"或"直接以 \(A\) 元购买"，使得最终买齐所有 \(B\) 件商品的总花费最小。

输入格式

• 第一行：两个整数 \(A, B\)。
• 接下来 \(B\) 行，每行 \(B\) 个整数：第 \(I\) 行第 \(J\) 列是 \(K_{I,J}\)。

保证：

• \(K_{I,J} = K_{J,I}\)
• \(K_{I,I} = 0\)

重要说明：

• \(K_{I,J} = 0\) 表示"无优惠关系"，不是 0 元购买。
• \(K_{I,J}\) 可能大于 \(A\)。

输出格式

输出一个整数，表示在最优策略下，买齐 所有 \(B\) 件商品所需的最小总费用。

样例一

输入

1 1
0

输出

1

解释：只有 1 件商品，直接以 \(A=1\) 元买下即可。

样例二

输入

3 3
0 2 4
2 0 2
4 2 0

输出

7

解释： 一种最优策略：先买第 2 件花 3 元；接着利用优惠，以 2 元买第 1 件；再以 2 元买第 3 件。总费用 \(3+2+2=7\)。 注意同时存在多个优惠时，可以自由选择最便宜的那条，例如不会选择用 4 元去买还能 2 元买到的那件。

数据范围

• 对于 30% 的数据：\(1 \le B \le 10\)。
• 对于 100% 的数据：\(1 \le B \le 500,\quad 0 \le A, K_{I,J} \le 1000\)。