#P8677. [2019年省队联测]硬件包管理器
[2019年省队联测]硬件包管理器
Problem B. 硬件包管理器
时间限制:1秒。空间限制:512 MB。 我想你应该秒掉过《软件包管理器》这一题,我相信,这道题你也一定能够秒掉。
你要造一套超级计算机。为了使它的计算速度达到能够用暴力算法在 内通过这场比赛的所有测试点,你还需要在这台超级计算机上安装 个硬件,每个硬件都要安装到这个超级计算机去。我们将这些硬件编号为。第个硬件的预定安装时间是。
可是,硬件之间有依赖关系。安装硬件的时间可以忽略不计,但是每个硬件安装的时间有一些大小限制。一共有 组限制,第 组限制可以用两个正整数表示 ,具体意义是编号在 的硬件的安装依赖于第个硬件的安装,因此它们的安装时间不早于编号为 的硬件的安装时间(安装时间可以相等)。
所以你会发现,完全按照预定的安装时间安装每个硬件,这 组限制不会全满足。因此你要调整这些硬件的安装时间。而你希望每个硬件的实际安装时间与预定安装时间的总偏离程度最小。对于第 个硬件,如果它的实际安装时间比预定安装时间早,那么早每个单位时间都会使总偏离程度增加; 如果它的实际安装时间比预定安装时间晚,那么晚每个单位时间都会使总偏离程度增加 。现在你的任务就是把总偏离程度的最小值算出来。
Input
第一行输入两个正整数,表示硬件的个数和限制的个数。
接下来行,每行三个正整数,意义与题目描述相同。 接下来行,每行两个正整数 ,意义与题目描述相同。
Output
仅一行,表示总偏离程度的最小值。
Examples
样例输入
5 1
1 100 1
1 100 1
1 100 1
1 100 1
2 1000000 1
1 5
样例输出
4
原 PDF 样例最后一台硬件的提前代价为 19260817,超过其声明的 。上例改为 1000000。把前四台各延后一单位的总代价4仍严格小于将最后一台提前一单位的代价,因此答案保持4。
补充样例2
2 1
1 1 1
2 1 1
1 2
1
补充样例3
3 1
1 2 3
4 2 3
2 2 3
1 3
2
Constraints
对于所有数据,$1\le n,m\le 300000,1\le t_{i}\le 10^{5},1\le a_{i},b_{i}\le 10^{6}$。 特殊性质 1:对于任意 。 特殊性质 2:对于任意 。
Subtask 1 (points: 10)
保证,且满足特殊性质 1.
Subtask 2 (points: 10)
保证.
Subtask 3 (points: 15)
保证,且满足特殊性质 2.
Subtask 4 (points: 20)
保证,且满足特殊性质 2.
Subtask 5 (points: 25)
保证。
Subtask 6 (points: 20)
保证。