#P2190. 小Z的车厢

小Z的车厢

题目描述

小 Z 的家乡有一列在环形铁轨上行驶的火车,共停靠 nn 个站(11 号站到 nn 号站顺时针排列)。

众所周知,春运是一件非常可怕的事情。不幸的是,小 Z 是铁路公司的员工,现在他收到了 mm 条除夕凌晨的订票申请,每个申请 (x,y,z)(x, y, z) 表示有 zz 个人要从 xx 号站顺时针坐到 yy 号站,同时,当火车停靠到 xx 号站时,所有要在 xx 站上车的人都会上车,所有要在 xx 号站下车的人都会下车。

由于始发站不确定,现在小 Z 想知道至少需要分配给这列火车多少节车厢(每节车厢可容纳 3636 人)才能顺利完成该铁路运输,希望你帮帮他。

输入格式

第一行包含两个整数 n,mn, m

接下来 mm 行,每行包含三个整数 x,y,zx, y, z

输出格式

第一行包含一个整数,表示至少需要分配给这列火车的车厢数。

3 2
1 2 36
2 3 36

1

4 2
1 2 36
4 3 36

2

提示

【数据规模】

对于 30%30 \% 的数据,n1000n \le 1000m10000m \le 10000

对于 100%100 \% 的数据,1n,m1061 \le n, m \le 10^6xyx \ne y1z1001 \le z \le 100