M. 构造王国
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

在遥远的构造王国中 ， 坐落着 $$$m$$$ 座城邦 ， 居住着 $$$n$$$ 名居民 。

第 $$$j$$$ 座城邦由两位守门人驻守 ， 他们的编号分别为 $$$2j-1$$$ 和 $$$2j$$$ 。 第 $$$i$$$ 名居民的编号则为 $$$2m+i$$$ 。

起初 ， 王国中的任意两人均互为朋友 。 然而 ， 按照王国的法则 ， 若两人并非朋友 ， 他们便无法同时踏入同一座城邦 。

构造水晶为每位居民降下了指引 ： 第 $$$i$$$ 名居民必须前往并进入第 $$$c_i$$$ 座城邦 。

为了确保第 $$$i$$$ 名居民绝对无法进入其他任何城邦 $$$j$$$ （ 即满足 $$$j \neq c_i$$$ ） ， 你必须使该居民与第 $$$j$$$ 座城邦的至少一位守门人解除朋友关系 。 换言之 ， 对于所有满足 $$$j \neq c_i$$$ 的城邦 $$$j$$$ ， 你需要在 $$$(2m+i , 2j-1)$$$ 与 $$$(2m+i , 2j)$$$ 这两对朋友关系中 ， 至少断绝其中一条 。 与此同时 ， 王国希望在满足条件的前提下 ， 能够保留尽可能多的朋友关系 。

在被断绝的朋友关系中 ， 若被解除关系的一方为某座城邦的 ' 第一位守门人 ' （ 即编号为奇数的守门人 ） ， 那么此次关系的断绝将在该居民与该守门人身上各留下一道 ' 赤印 ' 。

此时 ， 构造水晶施加了额外的束缚 ： 其一 ， 第 $$$i$$$ 名居民的身上必须恰好背负 $$$p_i$$$ 道赤印 ； 其二 ， 第 $$$j$$$ 座城邦的第一位守门人身上必须恰好汇聚 $$$q_j$$$ 道赤印 。

你需要判断是否存在一种断绝朋友关系的方案 ， 能够同时满足以下所有条件 ： 首先 ， 确保每名居民只能进入水晶所指定的唯一城邦 ； 其次 ， 所有居民与城邦第一位守门人身上的赤印数量均严格符合上述限制 ； 最后 ， 在满足以上所有前提下 ， 使得最终保留下来的朋友关系总数达到最大 。

若存在这样的方案 ， 请给出任意一种合法的关系断绝列表 ； 若无论如何均无法达成 ， 则输出 $$$-1$$$ 。

Input

输入的第一行包含两个正整数 $$$n$$$ 与 $$$m$$$ （ $$$1 \le n , m \le 1000$$$ ） ， 分别代表王国的居民数量与城邦数量 。

第二行包含 $$$n$$$ 个正整数 $$$c_1 , c_2 , \dots , c_n$$$ （ $$$1 \le c_i \le m$$$ ） ， 其中 $$$c_i$$$ 表示构造水晶为第 $$$i$$$ 名居民指定的城邦编号 。

第三行包含 $$$n$$$ 个非负整数 $$$p_1 , p_2 , \dots , p_n$$$ （ $$$0 \le p_i \le m-1$$$ ） ， 其中 $$$p_i$$$ 表示第 $$$i$$$ 名居民身上必须恰好拥有的赤印数量 。

第四行包含 $$$m$$$ 个非负整数 $$$q_1 , q_2 , \dots , q_m$$$ （ $$$0 \le q_j \le n$$$ ） ， 其中 $$$q_j$$$ 表示第 $$$j$$$ 座城邦的第一位守门人身上必须恰好拥有的赤印数量 。

Output

若不存在任何满足所有条件的合法方案 ， 请仅输出一行一个整数 $$$-1$$$ 。

若存在合法方案 ， 请在第一行输出一个非负整数 $$$D$$$ （ $$$0 \le D \le 10^6$$$ ） ， 表示为了达成目标而需要断绝的朋友关系总数 。

随后输出 $$$D$$$ 行 ， 每行包含两个正整数 $$$u$$$ 与 $$$v$$$ （ $$$1 \le u , v \le 2m+n$$$ 且 $$$u \neq v$$$ ） ， 表示你选择断绝编号为 $$$u$$$ 和 $$$v$$$ 两人之间的朋友关系 。

你输出的每一对朋友关系必须互不相同 （ 即同一条关系不可被重复断绝 ） 。 断绝这些关系后 ， 必须严格满足题目描述中的所有限制条件 ， 并且在合法前提下使剩余的朋友关系数量达到最大 。 若存在多种符合条件的最优方案 ， 输出其中任意一种即可 。 此外 ， 任何未被输出的编号对之间将依然保持原始的朋友关系 。

Example
Input
3 3
1 2 3
1 1 0
1 1 0
Output
6
7 3
7 6
8 1
8 6
9 2
9 4