Contexto

Tras concluir las tediosas tareas de investigación y revisión, los temas de conversación en la reunión social derivaron hacia las interacciones cotidianas. El pequeño T compartió con entusiasmo un hallazgo interesante: en una plataforma social de uso común, las relaciones de seguimiento entre los usuarios son estrictamente unidireccionales, es decir, no existe el caso en el que dos usuarios se sigan mutuamente.

Este fenómeno peculiar despertó inmediatamente la discusión. El pequeño S aprovechó la oportunidad para extraer algunos datos estadísticos de la red, recopilando el número de seguidos y seguidores de cada usuario. Lamentablemente, durante la transmisión de los datos, perdió una parte, dejando finalmente solo un conjunto compuesto por varios números enteros positivos. El pequeño S descubrió que, para cada elemento del conjunto, siempre es posible encontrar al menos un usuario cuyo número de seguidos o número de seguidores sea exactamente igual a dicho elemento.

Debido a que la estructura completa de seguimiento de la plataforma es confidencial, la red social específica es desconocida. Para verificar la razonabilidad de estos datos residuales, todos tomaron papel y lápiz, intentando reconstruir una red que cumpliera con las condiciones. Para añadir un poco de diversión y competitividad, incluso organizaron una pequeña competencia para ver quién podía construir la red social con el menor número total de seguimientos.

Descripción

En esta plataforma social, hay un total de $n$ usuarios. El pequeño S ha recopilado un conjunto de números de tamaño $m$, $\{c_1, \dots, c_m\}$. Basándose en esta información, una posible red de seguimiento puede abstraerse como un grafo dirigido $G = (V, E)$ que satisface las siguientes condiciones:

• Contiene $n$ usuarios, es decir, el conjunto de vértices $V = \{1, 2, \dots, n\}$;
• No existen casos de usuarios que se sigan a sí mismos o seguimientos repetidos, es decir, el grafo $G$ no contiene bucles ni aristas múltiples;
• Todas las relaciones de seguimiento son estrictamente unidireccionales, es decir, para cualquier arista dirigida $(u, v) \in E$, se cumple que $(v, u) \notin E$;
• Para cada elemento $c_i$ del conjunto ($1 \le i \le m$), en el grafo $G$ existe al menos un vértice cuyo grado de salida (correspondiente al número de seguidos) o grado de entrada (correspondiente al número de seguidores) es exactamente igual a $c_i$.

Debes reconstruir una red de seguimiento con el menor número total de seguimientos (es decir, el menor número de aristas en el grafo $G$) basándote en la información recopilada por el pequeño S.

Entrada

La primera línea de la entrada contiene un entero no negativo $o \in \{0, 1\}$, que representa el parámetro de salida.

La segunda línea de la entrada contiene dos enteros positivos $n, m$ ($1 \le m < n \le 10^6$), que representan el número de usuarios y el tamaño del conjunto recopilado por el pequeño S. Se garantiza que si $o = 0$, entonces $n \le 2 \times 10^3$.

La tercera línea de la entrada contiene $m$ enteros positivos distintos dos a dos $c_1, c_2, \dots, c_m$ ($1 \le c_i \le n - 1$), que representan los elementos del conjunto recopilado por el pequeño S.

Salida

Imprime en una línea un entero positivo $k$, que representa el valor mínimo del número total de seguimientos entre todas las redes de seguimiento posibles.

Si $o = 0$, a continuación imprime $k$ líneas, cada una conteniendo dos enteros positivos $u, v$ ($1 \le u, v \le n$), indicando que el usuario $u$ sigue al usuario $v$, es decir, $(u, v) \in E$.

Ejemplos

Entrada 1

0
5 4
3 1 4 2

Salida 1

7
3 2
4 1
3 4
4 5
3 5
4 2
3 1