### 问题描述 大衣有一个长度为 $N​$ 的数组 $A​$，给定一个变量 $X​$，初始值为 $0​$。 大衣将进行 $Q​$ 次操作，每次操作给定一组 ​$L_i​$ 和 ​$R_i​$（满足 $1\le L_i\le R_i\le N​$），将数组从 $L_i​$ 到 $R_i​$ 之间的所有元素加到变量 $X​$ 上。 在操作之前大衣可以对数组进行重新排列，大衣想让操作后 $X$ 尽可能大，请问他能得到的 $X​$ 的最大值是多少？ 大衣还想知道在 $X$ 取到最大值条件下重新排列后的数组 $A$，如果存在多种情况满足条件，数组 $A$ 为字典序最小的那个。 ### 输入格式 第一行输入两个正整数 $N$ 和 $Q$ 分别表示数组的长度和操作的次数。 第二行输入 $N$ 个整数 $A_1,A_2,\cdots,A_N$ 表示数组的元素。 接下来 $Q$ 行每行输入两个正整数 $L_i$ 和 $R_i$ 表示 $Q$ 次操作。 ### 输出格式 第一行输出一个整数表示经过重新排列和 $Q$ 次操作后能得到的 $X​$ 的最大值。 第二行输出在 $X$ 取到最大值条件下重新排列后的数组 $A$，如果存在多种情况满足条件，输出字典序最小的数组 $A$。 ### 样例输入1 ```text 5 2 1 2 3 4 5 1 4 2 3 ``` ### 样例输出1 ```text 23 2 4 5 3 1 ``` ### 样例输入2 ```text 2 3 1 1 1 1 1 2 2 2 ``` ### 样例输出2 ```text 4 1 1 ``` ### 说明 样例 $1$：给出的数组 $A=[1,2,3,4,5]$，将其重新排列成 $[2,4,5,3,1]$。 - 最初 $X=0$。 - 第一个操作将 $A_1+A_2+A_3+A_4$ 加到 $X$ 上得到 $X=0+14=14​$。 - 第二个操作将 $A_2+A_3$ 加到 $X$ 上得到 $X=14+9=23$。 此时经过 $Q$ 次操作后得到的 $X=23$，并且没有其他的排列方法使 $X$ 的值更大。 ### 评测数据规模 对于所有的评测数据，$1\le N,Q\le 2\times10^5$，$1\le A_i\le10^9$，$1\le L_i\le R_i\le N​$。