Maximizing Farm Expansion

Farmer John is expanding his farm and has found the ideal location: the Red-Black Forest. The forest is arranged along a number line with ( N ) trees located at positions ( x_i ) (( -10^9 \le x_i \le 10^9 ), ( 1 \le N \le 10^5 )). However, environmental protection laws impose restrictions on which trees can be cut down. There are ( K ) restrictions (( 1 \le K \le 10^5 )). The ( i)-th restriction requires that the closed interval ( [l_i, r_i] ) (with ( -10^9 \le l_i, r_i \le 10^9 )) must always contain at least ( t_i ) trees. It is guaranteed that the initial configuration of the forest satisfies all the restrictions.

Help Farmer John determine the maximum number of trees he can cut down while still satisfying every restriction. In other words, choose a set of trees to remain such that every interval ( [l_i, r_i] ) contains at least ( t_i ) trees, and maximize the number of trees removed. These conditions can be formally stated as follows:

Given a sorted list of tree positions ( x_1, x_2, \dots, x_N ) and restrictions of the form [ [l_i, r_i] : \text{at least } t_i \text{ trees remain}, \quad 1 \le i \le K, ] find a subset of trees of minimum size to keep so that every restriction is met. The answer to output is ( N ) minus the size of this subset.

inputFormat

The input begins with a line containing two integers ( N ) and ( K ).\nThe second line contains ( N ) integers ( x_1, x_2, \dots, x_N ), representing the positions of the trees along the number line.\nEach of the next ( K ) lines contains three integers ( l_i, r_i, t_i ) indicating that in the interval ( [l_i, r_i] ) there must be at least ( t_i ) trees remaining.\nIt is guaranteed that the initial configuration of the forest satisfies all restrictions.

outputFormat

Output a single integer representing the maximum number of trees that can be cut down while still satisfying all the given restrictions.

sample

5 2
1 2 5 10 15
1 10 2
5 15 2

3