3067: 彩虹岛女神

彩虹岛新生赛开赛啦！众所周知，李颖学姐是彩虹岛集训队的女神(会拉面)，很多人都想接近李颖学姐。而本次新生赛$ac$所有题的人都能得到李颖学姐的联系方式！

然而在这里有$m$个房间连成一排的房间，每个房间的两边有两扇门，分别与前一个房间与后一个房间相连，每个房间内有$l$道难题，限时$t$时间内答完。如果没答完，那么房间的两扇门都会锁上，直到新生赛结束。

现在有$n$个人有各自的做题速度$s$，他们商量让做题最快的人先闯关，然后慢的后闯，保证能让多数人能拿到李颖学姐的联系方式。然而邪恶的$zzy$不想别人拿到彩虹岛最美丽的李颖学姐的联系方式，于是打乱了这$n$个人的先后顺序。

这$n$个人将依次开始闯关。每次移动只能向下一个房间移动。每个人不知道前方房间情况，只有在规定时间内$ac$了当前房间的所有题后(如果消耗时间恰好等于时限，则算通过)，才能向下一个房间移动。如果下一个房间被锁住，那么这个人会被困到当前房间，直到当前房间被锁住。只有在上一个人通过所有房间，或者被困在某一房间且该房间被锁之后，下一个人才会开始闯关。如果第一个房间被锁住了，或者所有人都处于完全通过通过或被困于某个房间中，那么比赛结束。

聪明的$wwh$早已看穿了一切，他知道了每个人的速度序列$S_i$和每个房间的题目数量$L_j$与时限$T_j$，并且告诉$zzy$一共有多少人通过所有房间和哪些房间困住了人。聪明的你能像$wwh$一样得到答案吗？

第一行包括两个整数$n,m(1<=n,m<=100000)$,表示有$n$个人，$m$个题目。

接下来一行有$n$个整数$S_i(0<=S_i<=10^9)$，表示第$i$个人单位时间内做题数量.然后再接下里$m$行，每行两个整数，表示第$m$个房间的题目数量$L_j$与限制时间$T_j,(0\le L_j,T_j \le 10^9)$。

第一行输出两个数字，分别表示通过所有房间的人数，被困住的人数，用一个空格分开。

第二行从小到大输出每个困住人的房间编号，编号之间用一个空格分隔开。

3 5
2 1 3
1 1
1 2
2 1
0 1
4 5

1 2
2 3