Problem 1162. -- 集结

1162: 集结

Time Limit: 1 Sec  Memory Limit: 256 MB  Special Judge
Submit: 24  Solved: 4
[Submit][Status][Web Board]

Description

张老师一直希望同济大学能够进入ICPC的World Final,但是觉得同济大学ACM队太弱了。他想召集世界各地的上古大神来带领同济ACM队进行训练。
假设世界是一个1*n的一维地图,所有格子的坐标都是1到n之间的整数。一开始地图上某一些格子有一位上古大神,其他的格子会有一些事件。每个格子里面只有一位上古大神或者只有一个事件。张老师希望能请到上古大神能集中到一个格子上。
约定集结的坐标点之后,上古大神们依次开始移动。每一次有一位上古大神向着集结的坐标直线前进,不会向相反方向走。当一位上古大神进入一个格子的时候,如果这个格子里面有一个事件没有触发,那么就会触发这个事件让上古大神获得或者失去一些体力。当上古大神某一个时刻体力小于0的时候就不能到达集结点了(等于0依然可以到达)。一个事件只会触发一遍,已经触发过之后就不会再触发了。一位上古大神移动结束之后,另一位上古大神才开始移动。
张老师希望能将上古大神都请过来,但是不知道怎么安排集结点和移动顺序才能让所有人都能到达。他想让你规划一个集结的方案。
注意所有上古大神都需要移动且仅移动一次,即使是和集结点在一个坐标上也需要移动。

Input

第一行两个整数n,m(1<=m<=n<=100,000)表示格子的个数是n,一共有m位上古大神
接下来m行,有2个整数ai,bi(1<=ai<=n, 1<=bi<=1,000,000),表示第i位上古大神在坐标ai的位置上,有bi的体力。保证上古大神初始不会在同一共位置上
接下来一行,包括n个整数c1,c2......cn,第i个整数ci(-1,000,000<=ci<=1,000,000)表示坐标为i的位置的情况:
等于0:这个位置有一位上古大神;
不等于0:这个位置有一个事件,代表上古大神的体力变化量,大于0为增加,小于0为减少。

Output

第一行输出一个数代表集结点。
第二行输出m个数,第i个数代表第i个移动的上古大神序号。这个序号和输入的顺序相同。
如果有多种方案,输出任意一种。如果不能使所有人都到达,那么输出-1。

Sample Input

8 3
1 15
8 1
5 10
0 -5 -5 -5 0 -5 -5 0

Sample Output

7
3 1 2 

HINT

Source

[Submit][Status]