AT_joisc2017_d 切符の手配 (Arranging Tickets)

#「JOISC 2017 Day 2」门票安排 **题目译自 [JOISC 2017](https://www.ioi-jp.org/camp/2017/2017-sp-tasks/index.html) Day2 T1「[切符の手配](https://www.ioi-jp.org/camp/2017/2017-sp-tasks/2017-sp-d2.pdf)（[Arranging Tickets](https://www.ioi-jp.org/camp/2017/2017-sp-tasks/2017-sp-d2-en.pdf)）」** 某条铁路环线共有 $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 ```plain 3 3 1 2 1 2 3 1 3 1 1 ``` #### 样例输出 1 ```plain 1 ``` #### 样例解释 1 所有人都顺时针移动。 #### 样例输入 2 ```plain 3 2 1 2 4 1 2 2 ``` #### 样例输出 2 ```plain 3 ``` #### 样例解释 2 下面是一种需购买 $3$ 个套餐的方法： - 对于请求 $1$，$3$ 人顺时针移动，$1$ 人逆时针移动。 - 对于请求 $2$，$2$ 人逆时针移动。 没有更优的方案。 #### 样例输入 3 ```plain 6 3 1 4 1 2 5 1 3 6 1 ``` #### 样例输出 3 ```plain 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$|$C_i=1$| |3|20|$N\le 3000$|$M\le 3000$|$C_i=1$| |4|20|$N\le 2\times 10^5$|$M\le 10^5$|$C_i=1$| |5|15|$N\le 2\times 10^5$|$M\le 10^5$|| 感谢 Planet6174 提供的翻译