注意本题不同寻常的内存限制！

在对道路进行检查并考虑到道路每一公里上坑洼的高频率后，省政府拨出了一些资金用于进行部分道路维修。

利用这些资金，可以修复 $K_1$ 个长度恰好为 $L_1$ 公里的连续路段，以及 $K_2$ 个长度恰好为 $L_2$ 公里的连续路段。道路施工完成后，所有被修复路段上的坑洼都将被消除。

你受雇于道路建设公司，负责选择需要修复的路段，以尽可能多地消除坑洼。不幸的是，由于预算限制，为你提供的用于此任务的计算机仅有 32 兆字节的可用内存。

官僚规则要求修复的路段必须在距离道路起点整数公里的位置开始（并因此在整数公里处结束）。

修复的路段之间不能重叠。所有分配用于道路维修的资金必须全部用完。

输入格式

第一行包含五个整数：$N$ 是道路的长度（$1 \le N \le 10^4$），$K_1$ 和 $L_1$ 分别是类型 1 路段的数量和长度，$K_2$ 和 $L_2$ 分别是类型 2 路段的数量和长度（$1 \le K_i, L_i \le 100$，$L_1 \neq L_2$，$K_1L_1 + K_2L_2 \le N$）。

第二行包含 $N$ 个整数，其中第 $i$ 个整数表示道路第 $i$ 公里处的坑洼数量。这些整数是非负的且不超过 $10^9$。

输出格式

第一行输出一个整数——道路施工后消除的坑洼总数。

接下来的 $K_1 + K_2$ 行，每行输出两个整数，表示要修复路段的起点和终点坐标。路段应按坐标递增的顺序排列。

道路起点的坐标为 0。

样例

样例输入 1

20 2 3 3 2
2 0 2 0 1 2 1 2 1 2 2 2 1 1 2 2 2 1 2 2

样例输出 1

22
4 6
6 8
9 12
14 17
18 20