The ZAFT are attacking the Orb Union! There are 
~I~ stations, numbered from 
~1, 2, \dots, I~, that need to be defended. For it to be secure, the Orb Union needs to have at least 
~N~ troops at each station. Unfortunately, due to the radar-jamming effects of the Neutron Jammer, the Orb Union cannot order their troops to move between stations. The Orb Union will send 
~J~ waves of troops, each of which sends 
~K~ troops to each of the stations 
~X_i, X_{i+1}, \dots, X_f~. All stations start with 
~0~ troops.
The Orb Union wants you to help them find the number of stations that are not secure.
Input Specification
The first line will contain the integer ~I~ 
~(1 \le I \le 10^5)~, the number of stations.
The second line will contain the integer ~N~ 
~(1 \le N \le 10^9)~, the minimum number of troops required to defend a station.
The third line will contain the integer ~J~ 
~(1 \le J \le 10^5)~, the number of waves of troops.
The next ~J~ lines will contain 3 space-separated integers. These integers will be in the order 
~X_i~, 
~X_f~, ~K~ 
~(1 \le X_i \le X_f \le I)~ 
~(1 \le K \le 10^4)~.
Output Specification
Output the total number of stations that have less than ~N~ troops.
Sample Input
4
1
3
1 3 1
2 3 2
3 3 2
Sample Output
1
Explanation for Sample Output
Station 1 has 1 troop, station 2 has 3 troops, station 3 has 5 troops and station 4 has 0 troops. Station 4 is the only station with less than 1 troop, so the output is 1.
Comments
Is there a better than linear time way to sum the values in a sub-array of an array?
the problem type is data structures, not implementation. there's probably a better way to solve it. also, look at the time restrictions lol
This comment is hidden due to too much negative feedback. Show it anyway.