Bets

题意翻译

**题目描述** 在chelyabinsk这个地方住着一个厉害的商人，他叫nikita。人人都叫他boss (老板的意思)。 有一天nikita跟朋友alex一起去一个叫做summer biathlon world cup (夏日滑雪世界杯？。)的比赛。 nikita因为是一个厉害的人，所以他拿到了一个神奇奖券。这个奖券可以让他赌谁赢，每个赛道不能赌超过一个选手。 ------------ ------------ 这个比赛的规则是这样的： 有n个相等长度的赛道以及m个参赛者（编号1到m）。对于每个参赛者有以下信息： - Li：始发赛道号码 - Ri：结束赛道号码（Li<=Ri） - Ti：这个选手完成一个赛道的时间 - Ci：利润。。。单位是卢布（俄罗斯货币单位）。如果这个选手赢了，那么赌这个人会赢的人可以获得这么多钱。 第i个选手穿过从Li到Ri的赛道（包括Li和Ri），时间为(Ri-Li+1)·Ti个单位时间。每个赛道都需要Ti个单位时间。若这个选手在k个赛道中获得胜利，那么赌他会赢的人可以拿到k·Ci卢布。 在每个赛道中，每个独立的获胜者符合： - 如果至少有一个选手在这个赛道中比赛，那么获胜者为花时间最少的人。花时间最少指仅在这个赛道上的花时间最少的人。 - 如果有多个选手用相同的时间，那么序号小的选手获胜。 - 如果这个赛道上没有选手，那么就没有获胜者。 注意：每个人的速度始终不变。 nikita可以在每个赛道上分别赌任何一个选手会赢。 帮助nikita和alex找到最大的利润。 ------------ ------------ **输入格式** 第一行两个整数n和m(1<=n,m<=100)。接着的m行每行四个整数Li, Ri, Ti, Ci (1<=Li<=Ri<=n, 1<=Ti, Ci<=1000)。 ------------ ------------ **输出格式** 一行，最大的利润值。 again:每个赛道不能赌超过一个选手。 ------------ ------------ **说明提示** **第一个测试数据** 第1-2个赛道赌选手1。 第3个赛道赌选手3。 第4个赛道赌选手4。 利润为5（赛道1）+5（赛道2）+30（赛道3）+20（赛道4）=60卢布。 **第二个测试数据** 第1，5个赛道赌选手1。 第2-4个赛道赌选手2。 第6-7个赛道赌选手4。 第八个赛道没有获胜者。 利润为10（赛道1）+15（赛道2-4）+10（赛道5）+20（赛道6，7）=105卢布。

题目描述

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.

输入输出格式

输入格式

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 $ ).

输出格式

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.

输入输出样例

输入样例 #1

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

输出样例 #1

60

输入样例 #2

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

输出样例 #2

105

说明

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.