weird-chemists-3

You run a chemical laboratory which contains N beakers containing certain amount of solutions. The i^th beaker contains ai ml of a reactant solution. There also M chemists waiting outside your laboratory. Each chemist has a parchment of paper which has 3 integers written on it. The i^th chemist’s parchment contains 3 integers of the form: li ri xi

It denotes that the i^th chemist needs atleast xi ml of reactant solution but you can only take it from the bottles numbered li to ri. If you are able to meet the i^th chemists needs, he is happy . 

To put it more succinctly, to make the i^th chemist happy, it should be possible to take some beakers from li to ri such that the sum of their solutions is at least xi.

Print the number of chemists that returned happy after their transaction with you . 

Please note that a transaction with one chemist is independent of that with another chemist , that is the the values of the beakers doesn’t change for a new transaction. For each transaction consider that the values to be those that were there initially.  

Input: 

The first line contains 2 integers N and M.
The next line contains N integers, the i^th integer denoting ai.
The next M lines are of the form: li ri xi

Output:

Output a single integer: the number of happy chemists.  

Constraints:

1 ≤ N ≤ 10^4
1 ≤ M ≤ 1000
1 ≤ ai ≤ 10^4
1 ≤ li ≤ ri ≤ N
1 ≤ xi ≤ 10^9

SAMPLE INPUT
5 3
1 2 3 4 5
1 5 15
1 5 16
2 4 6

SAMPLE OUTPUT
2

Explanation

For the first chemist he can obtain a sum of 15 using all the beakers.
For the second chemist there is no way he can obtain a sum of 16.
For the third chemist he can use the bottles numbered 2 and 4.

Source: hackerearth | Difficulty: EASY


Solutions: