背景

研究や査読の議論を終えた後、茶話会の話題は日常的なソーシャルネットワークへと移りました。小Tは興味深い発見を興奮気味に共有しました。ある一般的なソーシャルプラットフォームにおいて、ユーザー間のフォロー関係はすべて厳密な「片方向フォロー」であり、二人のユーザーが互いにフォローし合うような関係は存在しないというのです。

この奇妙な現象はすぐに議論の的となりました。小Sはこれに乗じて、そのネットワークの統計データの一部を抽出し、各ユーザーのフォロー数とフォロワー数を収集しました。残念なことに、データを回覧する過程で一部を紛失してしまい、最終的にはいくつかの正整数からなる集合だけが残りました。小Sは、集合内の各要素に対して、そのフォロー数またはフォロワー数がちょうどその値に等しいユーザーが少なくとも一人存在することを発見しました。

プラットフォームの完全なフォロー構造は非公開であるため、具体的なソーシャルネットワークを知る由もありません。これらの残存データの妥当性を検証するため、皆は紙とペンを取り出し、条件を満たすネットワークの復元を試みました。さらに面白さと競技性を高めるため、誰が最も総フォロー数の少ないソーシャルネットワークを構築できるかという小さなコンテストまで始まりました。

あるソーシャルプラットフォームには $n$ 人のユーザーが存在します。小Sはサイズ $m$ の数字の集合 $\{c_1, \dots, c_m\}$ を収集しました。この情報に基づくと、考えられるフォロー関係のネットワークは、以下の条件を満たす有向グラフ $G = (V, E)$ として抽象化できます。

• $n$ 人のユーザーを含む。すなわち頂点集合 $V = \{1, 2, \dots, n\}$ である。
• 自分自身をフォローすることや、重複したフォローは存在しない。すなわち、グラフ $G$ は自己ループと多重辺を含まない。
• すべてのフォロー関係は厳密な「片方向フォロー」である。すなわち、任意の有向辺 $(u, v) \in E$ に対して、$(v, u) \notin E$ が成り立つ。
• 集合内の各要素 $c_i$ ($1 \le i \le m$) に対して、グラフ $G$ には、その出次数（フォロー数に対応）または入次数（フォロワー数に対応）がちょうど $c_i$ に等しい頂点が少なくとも一つ存在する。

小Sが収集した情報に基づき、総フォロー数（すなわちグラフ $G$ の辺の数）が最小となるフォローネットワークを復元してください。

入力

入力の1行目には、出力のパラメータを表す非負整数 $o \in \{0, 1\}$ が含まれる。 入力の2行目には、2つの正整数 $n, m$ ($1 \le m < n \le 10^6$) が含まれ、それぞれユーザー数と小Sが収集した集合のサイズを表す。$o = 0$ の場合、$n \le 2 \times 10^3$ であることが保証される。 入力の3行目には、$m$ 個の互いに異なる正整数 $c_1, c_2, \dots, c_m$ ($1 \le c_i \le n - 1$) が含まれ、小Sが収集した集合の要素を表す。

出力

1行目に、考えられるすべてのフォローネットワークにおける総フォロー数の最小値 $k$ を出力する。 $o = 0$ の場合、続けて $k$ 行を出力する。各行には2つの正整数 $u, v$ ($1 \le u, v \le n$) を含め、ユーザー $u$ がユーザー $v$ をフォローしていること、すなわち $(u, v) \in E$ であることを表す。

入出力例

入力 1

0
5 4
3 1 4 2

出力 1

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