CF367C Sereja and the Arrangement of Numbers

我们称一个由 $n$ 个整数 $a_1, a_2, \ldots, a_n$ 组成的数组是「美丽的」，如果它满足以下性质： - 对于所有出现在数组 $a$ 中的数字 $x$ 和 $y$，其中 $x \neq y$，必须存在某个位置 $j$ $(1 \leq j < n)$ 使得以下两个条件至少满足其一：$a_j = x, a_{j+1} = y$，或者 $a_j = y, a_{j+1} = x$。 Sereja 想要构造一个长度为 $n$ 的美丽数组 $a$。但事情并不简单，他的朋友 Dima 有 $m$ 张优惠券，每张优惠券包含两个整数 $q_i$ 和 $w_i$。使用第 $i$ 张优惠券需要花费 $w_i$ 卢布，并允许在构造数组 $a$ 时使用任意次数的数字 $q_i$。所有 $q_i$ 均互不相同。Sereja 没有优惠券，于是 Dima 和 Sereja 做了如下约定：Dima 构造一个长度为 $n$ 的美丽数组 $a$，之后对于 $a$ 中出现的每一个 $q_i$，Sereja 都要向 Dima 支付 $w_i$ 卢布。 Sereja 信任他的朋友，同意了协议。现在他想知道，自己最多可能需要支付多少钱。 请帮助 Sereja，计算他最多可能支付的卢布数。

第一行包含两个整数 $n$ 和 $m$，$1 \leq n \leq 2 \times 10^{6}$，$1 \leq m \leq 10^{5}$。 接下来的 $m$ 行每行包含两个整数 $q_i$ 和 $w_i$，$1 \leq q_i, w_i \leq 10^{5}$。保证所有 $q_i$ 互不相同。

输出一个整数，表示 Sereja 最多需要支付的卢布数。

在第一个样例中，Sereja 最多可以支付 $5$ 卢布，例如 Dima 可以构造如下数组：$[1, 2, 1, 2, 2]$。对于本测试还存在其它最优数组。 在第三个样例中，如果 Dima 构造数组 $[2]$，那么 Sereja 最多可以支付 $100$ 卢布。 由 ChatGPT 5 翻译