Minimum Bubble Sort Swaps on Constrained Sequences

Consider a sequence a₁, a₂, ..., a_n of non-negative integers that must satisfy m additional constraints. For each constraint i (1 ≤ i ≤ m), you are given three integers L_i, R_i, and V_i. The constraint requires that the minimum value of the elements in the interval [L_i, R_i] (i.e. a_Li, a_Li+1, ..., a_Ri) is exactly \(V_{i}\).

Your task is to choose one sequence among all sequences satisfying these constraints such that the number of swaps performed by bubble sort is minimized. Note that the number of swaps performed by bubble sort is equivalent to the inversion count of the sequence, i.e., the number of pairs (i, j) with i < j and a_i > a_j.

You may assume that the constraints are consistent, meaning that there exists at least one valid sequence. Hint: A non-decreasing (sorted) sequence has 0 inversions and will satisfy the constraints if you appropriately set the required elements.

inputFormat

The first line contains two integers n and m (1 ≤ n ≤ 10⁵, 0 ≤ m ≤ 10⁵) — the length of the sequence and the number of constraints.

Each of the next m lines contains three integers L_i, R_i, and V_i (1 ≤ L_i ≤ R_i ≤ n, 0 ≤ V_i ≤ 10⁹) representing a constraint that the minimum value within a[L_i] ... a[R_i] is exactly \(V_{i}\).

outputFormat

Output a single integer — the minimum possible number of swaps that bubble sort would perform on any valid sequence satisfying all the constraints.

sample

3 1
2 3 2

0