Minimum Trees to Satisfy Residents' Tree Planting Requirements

There are n roadside regions numbered \(1, 2, \ldots, n\). Each region has unit size and can have at most one tree planted in it.

There are several residents, each with a desire for trees in front of their house. Every resident specifies three numbers \(b\), \(e\), and \(t\), meaning that they want at least \(t\) trees planted in the regions between \(b\) and \(e\) (inclusive). The residents' intervals may overlap.

Your task is to determine the minimum number of trees that need to be planted so that all the residents' requirements are satisfied.

Note: In each region you can plant at most one tree.

inputFormat

The first line contains two integers \(n\) and \(m\), where \(n\) is the number of regions and \(m\) is the number of residents.

The next \(m\) lines each contain three integers \(b\), \(e\), and \(t\) representing a resident's requirement: at least \(t\) trees should be planted in the regions from \(b\) to \(e\) (inclusive), where \(1 \leq b \leq e \leq n\).

outputFormat

Output a single integer — the minimum total number of trees that must be planted to satisfy all residents' requirements.

sample

5 1
1 5 3

3