#P2190. 小Z的车厢
小Z的车厢
题目描述
小 Z 的家乡有一列在环形铁轨上行驶的火车,共停靠 个站( 号站到 号站顺时针排列)。
众所周知,春运是一件非常可怕的事情。不幸的是,小 Z 是铁路公司的员工,现在他收到了 条除夕凌晨的订票申请,每个申请 表示有 个人要从 号站顺时针坐到 号站,同时,当火车停靠到 号站时,所有要在 站上车的人都会上车,所有要在 号站下车的人都会下车。
由于始发站不确定,现在小 Z 想知道至少需要分配给这列火车多少节车厢(每节车厢可容纳 人)才能顺利完成该铁路运输,希望你帮帮他。
输入格式
第一行包含两个整数 。
接下来 行,每行包含三个整数 。
输出格式
第一行包含一个整数,表示至少需要分配给这列火车的车厢数。
3 2
1 2 36
2 3 36
1
4 2
1 2 36
4 3 36
2
提示
【数据规模】
对于 的数据,,;
对于 的数据,,,。