#2393. 「JOISC 2017 Day 2」门票安排

内存限制:256 MiB 时间限制:4000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

题目译自 JOISC 2017 Day2 T1「切符の手配 / Arranging Tickets

某条铁路环线共有 N 个车站,顺时针依次编号为 1\ldots N
该线路有 N 种车票,分别编号为 1\ldots N 。一张车票 i(1\le i\le N-1) 仅供一人从车站 i 顺时针移动到车站 i+1 ,或供一人从车站 i+1 逆时针移动到车站 i 。一张车票 N 仅供一人从车站 N 顺时针移动到车站 1 ,或供一人从车站 1 逆时针移动到车站 N
购买车票只有一种方法:购买套餐,套餐包含车票 1\ldots N 1 张。 你是一名导游,你正在为游客订票。现有 M 个订票请求,订票请求 i(1\le i\le M) 表示从车站 A_i 到车站 B_i C_i 名旅客(路线可以不同)。
求最少需要购买多少套餐。

输入格式

第一行有两个整数 N,M ,用空格分隔。
在接下来的 M 行中,第 i (1\le i\le M) 有三个整数 A_i,B_i,C_i ,用空格分隔。

输出格式

一个整数,表示最少需要购买的套餐数。

样例

样例输入 1

3 3
1 2 1
2 3 1
3 1 1

样例输出 1

1

样例解释 1

所有人都顺时针移动。

样例输入 2

3 2
1 2 4
1 2 2

样例输出 2

3

样例解释 2

下面是一种需购买 3 个套餐的方法:

  • 对于请求 1 3 人顺时针移动, 1 人逆时针移动。
  • 对于请求 2 2 人逆时针移动。

没有更优的方案。

样例输入 3

6 3
1 4 1
2 5 1
3 6 1

样例输出 3

2

样例解释 3

把车票 1,2,3 给第一个人,把车票 1,6,5 给第二个人,把车票 3,4,5 给第三个人。
没有更优的方案。

数据范围与提示

Subtask # 分值 N M C_i(1\le i\le M)
1 10 N\le 20 M\le 20 C_i=1
2 35 N\le 300 M\le 300
3 20 N\le 3000 M\le 3000
4 N\le 2\times 10^5 M\le 10^5
5 15