题目描述(ID:12382)
标题: 铺路
标签:
详情:
    编程星球受小凯和源码巨人战斗的强大冲击波影响,角斗场附近需要修缮。啊哈沃德召集了全星球的铺路大队重整路面。他计划用m天完成所有的修缮任务,其中铺路大队一共有n支,并将他们分配到了不同的地方进行修理。根据初步估计,队伍修复预计用时记为file:///C:/Users/HP/AppData/Local/Temp/msohtmlclip1/01/clip_image002.png,表示第i组的工作预计总用时。
    需要修理的不只是路面。为了配合其他工作组的修理工作,他们不能每天都用所有的时间去修理路面。不过一切都在规划中,他们已经确定,对于第i天,所有队伍均有有file:///C:/Users/HP/AppData/Local/Temp/msohtmlclip1/01/clip_image004.png的时间可以用于进行修理作业。同时,他们每天还要维护设备,无论当天有没有用这些设备。这也要耗费一些时间。记file:///C:/Users/HP/AppData/Local/Temp/msohtmlclip1/01/clip_image006.png为第i支队伍每天执行维护任务的用时。
    现在啊哈沃德要最后确认一遍安排。请告诉他,每支队伍在第几天可以完成自己负责的维修任务,以及所有工程能否按时完成。
输入格式:
第一行给出两个整数n、m。
第二行给出m个整数P_i。
接下来n行,每行给出两个整数M_i和E_i。
输出格式:
n个整数,表示各个队伍最早能在第几天结束维修工作。如果不能完成,输出-1。
限制: 对 30% 的输入数据 :1<=n,m<=1000
对 100% 的输入数据 :1<=n,m<=200000; 1<=P_i,E_i<=1000000; 0<=M_i<=1000000。
样例:

输入

3 3
4 2 5
2 5
3 4
1 3

输出

3 -1 1
登录并解答