题目描述

每个人都喜欢电脑，但购买新电脑总是一个经济挑战。幸运的是，总有一种便捷的解决方案：你可以通过更换电脑来获得全新的设备，从而节省一些维护成本。当然，每次购买新电脑都需要支付一笔固定费用。

假设你正在考虑一个$n$年的时间段，在这期间你需要使用电脑。如果你在第$y$年$（1 ≤ y ≤ n）$购买了一台新电脑，那么你需要在第$y$年支付固定费用$c$，并在拥有该电脑的每一年（从第$y$年到第$z$年，$z ≤ n$）支付维护费用$m(y, z)$，直到你计划最终更换另一台电脑为止。

请编写一个程序，计算在这$n$年期间使用电脑的最小总成本。

输入格式

程序输入来自文本文件。每个数据集代表一组特定的成本。数据集的第一行是购买新电脑的固定费用$c$。接下来是年数$n$，以及维护费用$m(y, z)$，其中$y = 1..n，z = y..n$。程序输出在这n年期间使用电脑的最小总成本。

输入中的空格可以自由出现。输入数据是正确的，并以文件结束符终止。

输出格式

对于每个数据集，程序从新行的开头将结果打印到标准输出。

输入样例

3
3
5 7 50
6 8
10

输出样例

19

提示

上面的输入/输出示例展示了一个单独的数据集。购买新电脑的固定费用$c=3$。时间范围$n=3$年，维护费用如下：

• 对于第一台电脑（必须购买）：$m(1,1)=5，m(1,2)=7，m(1,3)=50$
• 对于第二台电脑（如果更换当前电脑）：$m(2,2)=6，m(2,3)=8$
• 对于第三台电脑（如果更换当前电脑）：$m(3,3)=10$

来源

Southeastern Europe 2007