首先对 $$$c_i$$$ 进行桶排序，将 $$$c_i$$$ 变成严格单调递增的正整数序列。以下 $$$c_i$$$ 都满足这个假设。

将每个顶点 $$$i$$$ 拆成两个点 $$$i^{+}$$$ 和 $$$i^{-}$$$，一个表示入边，一个表示出边，比如 $$$1$$$ 向 $$$2$$$ 连边就变成了 $$$1^-$$$ 和 $$$2^+$$$ 连边。不难发现得到的新图为无向二分图。

不妨先不考虑自环重边双向边的条件，则问题转化为：对一个无向二分图 $$$G=X+Y$$$，求 $$$|E(G)|_{\min}$$$ 使得存在 $$$m$$$ 个点度分别为 $$$c_1, c_2, \dots, c_m$$$。

实际上，我们考查度为 $$$c_{m-i+1}, \dots, c_{m-1}, c_m$$$ 的点，设其中有 $$$a$$$ 个点在 $$$X$$$ 内，$$$b$$$ 个点在 $$$Y$$$ 内，则 $$$a+b=i$$$。那么 $$$E(G)$$$ 包含这些点连出的所有边的并，而这个边数 $$$\ge \sum\limits_{k=m-i+1}^m c_k - ab$$$（总的减去重复算的）$$$\ge \sum\limits_{k=m-i+1}^m c_k - \left\lfloor\dfrac{i^2}{4}\right\rfloor$$$，因此我们得到了 $$$|E(G)|$$$ 的一个下界：

$$$$$$\max_{1 \le i \le m}\{\sum_{k=m-i+1}^m c_k - \left\lfloor\dfrac{i^2}{4}\right\rfloor\}$$$$$$

下面我们构造一个取得这么多条边的例子。记 $$$X = \{u_1, \dots, u_n\}, Y=\{v_1,\dots, v_n\}$$$。设上式在 $$$i=t$$$ 时取到最大值，如果在多处取到最大就取 $$$t$$$ 最小的那个。记 $$$a = \left\lceil\dfrac{t}{2}\right\rceil, b = \left\lfloor\dfrac{t}{2}\right\rfloor$$$。

我们选定 $$$X$$$ 中的 $$$a$$$ 个点，让其中的点度分别为 $$$c_m, c_{m-2},\dots, c_{m-2(a-1)}$$$，且选定 $$$Y$$$ 中的 $$$b$$$ 个点，让其中的点度分别为 $$$c_{m-1}, c_{m-3}, \dots, c_{m-(2b-1)}$$$。不妨设这些点为 $$$u_1, \dots,u_a, v_1,\dots,v_b$$$。

我们的构造方式是：$$$\forall\ 1\le j\le a$$$，$$$u_j$$$ 与 $$$v_1, v_2, \dots, v_{c_{m-2j+2}}$$$ 连边；$$$\forall\ 1 \le k \le b$$$，$$$v_k$$$ 与 $$$u_1, u_2, \dots, u_{c_{m-2k+1}}$$$ 连边。

因为 $$$i=t$$$ 时上式取到最大值，所以 $$$c_{m-t} \le \left\lceil\dfrac{t}{2}\right\rceil$$$（$$$i=t$$$ 时与 $$$i=t+1$$$ 时两式比较），$$$c_{m-t+1} \ge \left\lceil\dfrac{t+1}{2}\right\rceil$$$（$$$i=t$$$ 时与 $$$i=t-1$$$ 时比较并结合 $$$t$$$ 的最小性）。我们又注意到在这样的构造下，度为 $$$1, 2, \dots, \left\lceil\dfrac{t}{2}\right\rceil$$$ 的点是必然存在的，因此这样的构造满足要求，同时我们发现当 $$$(u_1, u_2, \dots, u_n)=(1, 2, \dots, n)$$$，$$$(v_1, v_2. \dots, v_n) = (n, n - 1, \dots, 1)$$$ 时，这种构造可以直接搞定条件中的没有自环重边双向边。事实上可以注意到在这个构造下，不存在 $$$1 \le p, q \le n$$$，满足 $$$p^{-}$$$ 与 $$$q^{+}$$$、$$$p^{+}$$$ 与 $$$q^{-}$$$ 均连边。

在具体实现时我们并不需要先求出 $$$t$$$，直接按照这样的构造方式从大到小枚举，同时小端不断右移直至两端汇合即可，所以如果直接猜出了构造方式的话通过此题也不需要最开始的论证，只不过在数学上缺少了严谨证明。

over，$$$opt=0$$$ 时时间复杂度为 $$$\mathcal O(n^2)$$$，$$$opt=1$$$ 时时间复杂度为 $$$\mathcal O(n + m)$$$。