题目描述

在 chelyabinsk 这个地方住着一个厉害的商人，他叫 nikita。人人都叫他 boss（老板的意思）。有一天 nikita 跟朋友 alex 一起去一个叫做 summer biathlon world cup（夏日滑雪世界杯？）的比赛。

nikita 因为是一个厉害的人，所以他拿到了一个神奇奖券。这个奖券可以让他赌谁赢，每个赛道不能赌超过一个选手。这个比赛的规则是这样的：有 $n$ 个相等长度的赛道以及 $m$ 个参赛者（编号 $1$ 到 $m$）。对于每个参赛者有以下信息：

• $L_i$：始发赛道号码；
• $R_i$：结束赛道号码（$L_i\le R_i$）；
• $T_i$：这个选手完成一个赛道的时间；
• $C_i$：利润，单位是卢布（俄罗斯货币单位）。如果这个选手赢了，那么赌这个人会赢的人可以获得这么多钱。

第 $i$ 个选手穿过从 $L_i$ 到 $R_i$ 的赛道（包括 $L_i$ 和 $R_i$），时间为 $(R_i-L_i+1)·T_i$ 个单位时间。每个赛道都需要 $T_i$ 个单位时间。若这个选手在 $k$ 个赛道中获得胜利，那么赌他会赢的人可以拿到 $k·C_i$ 卢布。

在每个赛道中，每个独立的获胜者符合：

• 如果至少有一个选手在这个赛道中比赛，那么获胜者为花时间最少的人。花时间最少指仅在这个赛道上的花时间最少的人。
• 如果有多个选手用相同的时间，那么序号小的选手获胜。
• 如果这个赛道上没有选手，那么就没有获胜者。

注意：每个人的速度始终不变。

nikita 可以在每个赛道上分别赌任何一个选手会赢。帮助 nikita 和 alex 找到最大的利润。

输入格式

第一行两个整数 $n$ 和 $m\ (1\le n,m\le 100)$。

接着的 $m$ 行，每行四个整数 $L_i, R_i, T_i, C_i\ (1\le L_i\le R_i\le n$，$1\le T_i, C_i\le 1000)$。

输出格式

一行，最大的利润值。

4 4
1 4 20 5
1 3 21 10
3 3 4 30
3 4 4 20

60

第 $1\sim 2$ 个赛道赌选手 $1$。第 $3$ 个赛道赌选手 $3$。第 $4$ 个赛道赌选手 $4$。利润为 $5$（赛道 $1$）$+5$（赛道 $2$）$+30$（赛道 $3$）$+20$（赛道 $4$）$=60$ 卢布。

8 4
1 5 24 10
2 4 6 15
4 6 30 50
6 7 4 20

105

第 $1$，$5$ 个赛道赌选手 $1$。第 $2\sim 4$ 个赛道赌选手 $2$。第 $6\sim 7$ 个赛道赌选手 $4$。第八个赛道没有获胜者。利润为 $10$（赛道 $1$）$+15$（赛道 $2\sim 4$）$+10$（赛道 $5$）$+20$（赛道 $6$，$7$）$=105$ 卢布。