Minimum Watermelon Plantation

Benben has a long, narrow watermelon field whose planting positions are aligned in a straight line and labeled from 1 to n. After much research, he derived m conclusions that guarantee his harvest is maximized. Each conclusion states that within an interval of the field, from position B to E, at least T watermelons must be planted to achieve maximum yield.

However, Benben does not want to work too hard. He aims to minimize the total number of watermelons he plants while satisfying all the conclusions. Your task is to help him determine the minimum number of watermelons that must be planted along the field so that every conclusion is met.

Problem Summary

• You are given an integer n (the number of positions in the field) and an integer m (the number of conclusions).
• Each of the next m lines contains three integers: B, E, and T. This means that in the interval [B, E] (inclusive), there must be at least T watermelons planted.
• You need to choose, for each position, a nonnegative integer (typically 0 or 1 in the optimal strategy) indicating the number of watermelons planted, so that all conditions are satisfied and the total planted is minimized.

Note: It is guaranteed that a solution exists. A greedy algorithm that processes the intervals sorted by their end position is sufficient to solve this problem.

inputFormat

The first line contains two integers n and m separated by a space, where n is the number of positions in the field and m is the number of conclusions.

Each of the next m lines contains three integers B, E, and T (separated by spaces) representing a conclusion: in the interval from position B to E, at least T watermelons must be planted.

It is assumed that positions are 1-indexed.

outputFormat

Output a single integer, which is the minimum total number of watermelons that need to be planted in order to satisfy all the conclusions.

sample

10 2
1 5 3
4 10 2

3