Toxel 与 PCPC II

题目描述

Toxel 正在参加 PCPC（Pokémon Center Programming Contest）比赛。它写的一段代码中有不少 bug，正在调试。这份代码总共有 $n$ 行，而且经验丰富的 Toxel 已经知道了其中 $m$ 行代码有 bug，并锁定了这 $m$ 行的具体位置。但是 Toxel 还需要进行一些调试以了解错误的具体细节并修复它们。

Toxel 会进行多次调试。每次调试时，Toxel 可以任选一个 $i$，使得程序从第 $1$ 行开始，顺序运行完第 $i$ 行后退出。Toxel 可以通过这 $i$ 行代码运行的一些输出结果来进行 debug。运行这 $i$ 行代码总共需要 $i$ 秒。接下来，Toxel 会一次性地 debug 这 $i$ 行代码，并修复所有这 i 行中的所有 bug。bug 数量越多，修复所需的时间也越多。设这 $i$ 行代码中现存的 bug 数量为 $x$，那么 Toxel 需要 $x^4$ 秒来 debug 并完成修复。修复后，这 $i$ 行代码中将不再存在任何 bug。

PCPC 的赛场争分夺秒。请你帮 Toxel 计算一下，它最短需要多少秒才能完成 debug，修复整个代码中的所有漏洞？

输入格式

第一行包含两个整数 $n，m（1 ≤ m ≤ n ≤ 2 × 10^5）$。 第二行包含 $m$ 个整数 $a_1, a_2, . . . , a_m（1 ≤ a_1 < a_2 < · · · < a_m ≤ n）$，表示代码中所有有 bug 的行编号。

输出格式

输出一行一个整数，表示答案。

样例 #1

样例输入 #1

3 2
1 3

样例输出 #1

6

提示

对于第一个样例，Toxel 应该选择先运行前 $1$ 行代码，运行消耗 $1$ 秒，debug 消耗 $1^4 = 1$ 秒。接下来Toxel 应该选择运行前 $3$ 行代码，运行消耗 $3$ 秒，debug 消耗 $1^4 = 1$ 秒。总计消耗 $1 + 1 + 3 + 1 = 6$ 秒。

对于第三个样例，Toxel 可以分别运行前 $1, 2, 3, . . . , 13, 14, 16, 18, 20$ 行来得到最优解。