← 返回题目列表

Codeforces · 69/B

B. 投注

中文机器翻译题面 查看原题

在车里雅宾斯克住着一位备受尊敬的商人尼基塔,他有一个奇怪的绰号“老板”。有一次,尼基塔决定和他的朋友亚历克斯一起去参加夏季冬季两项世界杯。尼基塔(Nikita)作为一位非常重要的人物,收到了一个代币,该代币允许在每个部分最多对一个竞争对手进行下注。

首先跟朋友学了规则:比赛有n个长度相等的路段,m个参赛者。参与者编号从 1 到 m。关于每个参与者,已知以下信息:

- li — 起始节的编号,
- ri — 精加工段的编号(li ≤ ri),
- ti — 冬季两项运动员完成一段路径所需的时间,
- ci — 以卢布为单位的利润。如果第 i 个运动员在其中一个部分获胜,则利润将给予对该运动员下注的人。

第 i 个冬季两项运动员通过了从 li 到 ri(含)的部分。参赛者以(ri - li + 1)·ti 时间单位跑完全程。他需要恰好ti个时间单位才能通过每个部分。如果运动员在 k 个部分获胜,则为他下注的人将获得 k·ci 卢布。

在每个部分中,获胜者的独立确定如下:如果至少有一名冬季两项运动员在该部分中跑完该部分,则在所有运动员中以最短时间跑完该部分(通过该部分的时间最短)的获胜者。如果次数相等,则指数较小的运动员获胜。如果本部分没有参赛者,则本部分的获胜者尚未确定。不得不说,夏季冬季两项,所有参赛者都在以匀速前进。

我们还应该补充一点,尼基塔可以对每个部分以及在该部分中运行的任何参赛者进行投注。

帮助朋友们找到最大可能的利润。

输入

第一行包含两个整数 n 和 m (1 ≤ n, m ≤ 100)。然后是 m 行,每行包含 4 个整数 li, ri, ti, ci (1 ≤ li ≤ ri ≤ n, 1 ≤ ti, ci ≤ 1000)。

输出

打印一个整数,朋友们可以获得的最大利润(以卢布为单位)。在 n 个部分的每个部分中,不允许对超过一名运动员进行投注。

示例

输入 #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

注意

在第一个测试中,最佳投注是:在冬季两项运动员 1 的 1-2 部分中,在冬季两项运动员 3 的第 3 部分中,在冬季两项运动员 4 的第 4 部分中。总计:1 部分利润 5 卢布,2 部分利润 5 卢布,3 部分利润 30 卢布,4 部分利润 20 卢布。总利润60卢布。

在第二个测试中,最佳投注是:在冬季两项运动员 1 的 1 和 5 部分中,在冬季两项运动员 2 的 2-4 部分中,在运动员 4 的 6-7 部分中。第 8 部分没有获胜者。总计:1 段利润 10 卢布,2、3、4 段利润 15 卢布,5 段利润 10 卢布,6、7 段利润 20 卢布。利润总额105卢布。