CF69B.Bets

In Chelyabinsk lives a much respected businessman Nikita with a strange nickname "Boss". Once Nikita decided to go with his friend Alex to the Summer Biathlon World Cup. Nikita, as a very important person, received a token which allows to place bets on each section no more than on one competitor.

To begin with friends learned the rules: in the race there are n sections of equal length and m participants. The participants numbered from 1 to m. About each participant the following is known:

• l__i — the number of the starting section,
• r__i — the number of the finishing section (l__i ≤ r__i),
• t__i — the time a biathlete needs to complete an section of the path,
• c__i — the profit in roubles. If the i-th sportsman wins on one of the sections, the profit will be given to the man who had placed a bet on that sportsman.

The i-th biathlete passes the sections from l__i to r__i inclusive. The competitor runs the whole way in (r__i - l__i + 1)·t__i time units. It takes him exactly t__i time units to pass each section. In case of the athlete's victory on k sections the man who has betted on him receives k·c__i roubles.

In each section the winner is determined independently as follows: if there is at least one biathlete running this in this section, then among all of them the winner is the one who has ran this section in minimum time (spent minimum time passing this section). In case of equality of times the athlete with the smaller index number wins. If there are no participants in this section, then the winner in this section in not determined. We have to say that in the summer biathlon all the participants are moving at a constant speed.

We should also add that Nikita can bet on each section and on any contestant running in this section.

Help the friends find the maximum possible profit.

在车里雅宾斯克住着一位备受尊敬的商人尼基塔，他有一个奇怪的绰号叫“老板”。某次，尼基塔决定和朋友亚历克斯一同前往夏季冬季两项世界杯。尼基塔作为一位非常重要的人物，获得了一枚特殊令牌，该令牌允许他在每个赛段上最多对一名选手下注。

首先，朋友们了解了比赛规则：比赛共有 $n$ 个长度相等的赛段和 $m$ 名参赛者，参赛者编号为 $1$ 到 $m$。关于每位参赛者，已知以下信息：

• $l_i$ —— 起始赛段编号，
• $r_i$ —— 终止赛段编号（满足 $l_i \le r_i$），
• $t_i$ —— 该冬季两项运动员完成一个赛段所需的时间，
• $c_i$ —— 下注收益（单位：卢布）。若第 $i$ 名运动员在某个赛段上获胜，则对该运动员下注的人将获得 $c_i$ 卢布的收益。

第 $i$ 名运动员经过的赛段为从 $l_i$ 到 $r_i$（含端点）。他全程耗时为 $(r_i - l_i + 1) \cdot t_i$ 个时间单位；且通过每个赛段均恰好耗时 $t_i$ 个时间单位。若该运动员在 $k$ 个赛段上获胜，则对其下注者将获得 $k \cdot c_i$ 卢布的收益。

每个赛段的获胜者独立判定，规则如下：
若至少有一名运动员在该赛段上参赛，则所有在该赛段参赛的运动员中，通过该赛段用时最短者获胜（即花费最少时间通过该赛段者获胜）；若存在多名运动员用时相同，则编号较小者获胜；若该赛段无任何运动员参赛，则该赛段无获胜者。需要说明的是，在夏季冬季两项比赛中，所有运动员均以恒定速度移动。

还需补充一点：尼基塔可在每个赛段上对任意一名正在该赛段参赛的运动员下注。

请帮助这两位朋友计算出可能获得的最大总收益。

The first line contains two integers n and m (1 ≤ n, m ≤ 100). Then follow m lines, each containing 4 integers l__i, r__i, t__i, c__i (1 ≤ l__i ≤ r__i ≤ n, 1 ≤ t__i, c__i ≤ 1000).

第一行包含两个整数 $n$ 和 $m$（$1 \leq n, m \leq 100$）。接下来是 $m$ 行，每行包含四个整数 $l_i$、$r_i$、$t_i$、$c_i$（$1 \leq l_i \leq r_i \leq n$，$1 \leq t_i, c_i \leq 1000$）。

Print a single integer, the maximal profit in roubles that the friends can get. In each of n sections it is not allowed to place bets on more than one sportsman.

输出一个整数，即朋友们所能获得的最大利润（单位：卢布）。在全部 $n$ 个区段中，每个区段最多只能对一名运动员下注。

In the first test the optimal bet is: in the 1-2 sections on biathlete 1, in section 3 on biathlete 3, in section 4 on biathlete 4. Total: profit of 5 rubles for 1 section, the profit of 5 rubles for 2 section, profit of 30 rubles for a 3 section, profit of 20 rubles for 4 section. Total profit 60 rubles.

In the second test the optimal bet is: on 1 and 5 sections on biathlete 1, in the 2-4 sections on biathlete 2, in the 6-7 sections on athlete 4. There is no winner in the 8 section. Total: profit of 10 rubles for 1 section, the profit of 15 rubles for 2,3,4 section, profit of 10 rubles for a 5 section, profit of 20 rubles for 6, 7 section. Total profit 105 rubles.

第一次测试中，最优投注方案为：第 1–2 节投注于冬季两项运动员 1，第 3 节投注于冬季两项运动员 3，第 4 节投注于冬季两项运动员 4。收益分别为：第 1 节盈利 5 卢布，第 2 节盈利 5 卢布，第 3 节盈利 30 卢布，第 4 节盈利 20 卢布。总盈利为 60 卢布。

第二次测试中，最优投注方案为：第 1 和第 5 节投注于冬季两项运动员 1，第 2–4 节投注于冬季两项运动员 2，第 6–7 节投注于运动员 4。第 8 节无获胜者。收益分别为：第 1 节盈利 10 卢布，第 2、3、4 节每节盈利 15 卢布，第 5 节盈利 10 卢布，第 6、7 节每节盈利 20 卢布。总盈利为 105 卢布。