你的好友是全球并行计算中心（GCPC）业务团队的一员。她负责购买和销售维持系统运行的硬件，该系统将在未来 $n$ 个月内使用。目前，她正在规划单个 CPU 的更换周期。为了确保系统始终保持最新，CPU 必须至少每 $m$ 个月更换一次。幸运的是，她可以通过出售更换下来的 CPU 来降低运营新系统的总成本。然而，存储容量价格昂贵，她必须接受 CPU 在更换月份时的转售价值。这意味着，当一个使用了 $j$ 个月的 CPU 在第 $i$ 个月被更换时，你需要以该 CPU 使用 $j$ 个月后的价值卖掉当前的 CPU，并以第 $i$ 个月的价格购买一个新的 CPU。她已经整理了一份未来 $n$ 个月的 CPU 价格清单，其中包括使用 $1$ 到 $m$ 个月后的转售价值。注意，你必须在第 $0$ 个月购买一个 CPU，并且需要在第 $n+1$ 个月卖掉最后一个 CPU。系统在 $n$ 个月内的最低成本是多少？

Summit 超级计算机的建造费用为 2 亿美元。

输入格式

输入包含：

• 一行，包含两个整数 $n$ 和 $m$ ($1 \le n, m$ 且 $n \cdot m \le 5 \cdot 10^5$)。
• $n$ 行；第 $i$ 行包含一个整数 $c$ ($0 \le c \le 10^9$)，表示第 $i$ 个月购买 CPU 的成本，随后是 $\min(m, n - i + 1)$ 个整数 $c_j$ ($0 \le c_j \le 10^9$)，表示该 CPU 使用 $j > 0$ 个月后出售所获得的金额。

输出格式

输出一个整数，表示最低总成本。注意，如果转售 CPU 有利可图，该数字可能为负数。