AT_xmascon16_g.Guide Passengers

题目意思

兔子铁路是兔子专用的铁路。车站从西到右依次编号为1～N（1≤i≤N）。各站都有限制C，车站只能同时有Ci只兔子等车。
铁道计划运行M（1≤i≤M）趟列车，列车是在时刻Si从车站Ai出发，在时刻Ti到达车Ai+1，只可以搭载兔子Bi只。
现在，车站1有一只C1的兔子，所有兔子都想去车站N，最多能搬运几只兔子到车站N？

样例1解释

可以像以下那样搬运5只兔子。
-列车1乘坐3只。
-在车站2全体换乘列车2（到站时另一辆列车--2号车恰好来了，所以不考虑车站2的限制。
-在车站3全体下车。
-列车4乘坐5只。
-在车站2全体下车等待列车3（3号车还没到，所以要等车，考虑限制为C2--2只兔子，所以5只兔子只留了2只等车，剩下的可以不用运过来，放回车站1）。
-剩下的两只乘坐列车3。
-在车站3全体下车。
共计5只兔子来到n站。

第一行两个整数 $N$ $M$，表示车站数和列车数。
第二行$N$个整数 $C1...Cn$ ,表示每个车站的限制。
接下来$M$组数据：
$S,T,A,B$。

一个整数$N$,到n站的兔子数。