4317: 负载均衡

有n台计算机，第i台计算机的运算能力为$v_i$。

有一系列的任务被指派到各个计算机上，第i个任务在$a_i$时刻分配，指定计算机编号为$b_i$，耗时为$c_i$且算力消耗为$d_i$。

如果此任务成功分配，将立刻开始运行，期间持续占用$b_i$号计算机$d_i$的算力，持续$c_i$秒。

对于每次任务分配，如果计算机剩余的运算能力不足则输出−1，并取消这次分配，否则输出分配完这个任务后这台计算机的剩余运算能力。

输入的第一行包含两个整数n,m，分别表示计算机数目和要分配的任务数。

第二行包含n个整数$v_1,v_2,⋅⋅⋅v_n$，分别表示每个计算机的运算能力。

接下来m行每行4个整数$a_i,b_i,c_i,d_i$，意义如上所述。数据保证$a_i$严格递增，即$a_i$。

输出m行，每行包含一个数，对应每次任务分配的结果。

2 6
5 5
1 1 5 3
2 2 2 6
3 1 2 3
4 1 6 1
5 1 3 3
6 1 3 4

2
-1
-1
1
-1
0