#P8677. [2019年省队联测]硬件包管理器

    ID: 8764 传统题 1000ms 512MiB 尝试: 3 已通过: 1 难度: 9 上传者: 标签>动态规划数据结构栈图论拓扑排序CF2600堆树形DP

[2019年省队联测]硬件包管理器

Problem B. 硬件包管理器

时间限制:1秒。空间限制:512 MB。 我想你应该秒掉过《软件包管理器》这一题,我相信,这道题你也一定能够秒掉。

你要造一套超级计算机。为了使它的计算速度达到能够用暴力算法在10−100s10^{-100}s 内通过这场比赛的所有测试点,你还需要在这台超级计算机上安装nn 个硬件,每个硬件都要安装到这个超级计算机去。我们将这些硬件编号为1,2,...,n1,2,...,n。第ii个硬件的预定安装时间是tit_{i}。

可是,硬件之间有依赖关系。安装硬件的时间可以忽略不计,但是每个硬件安装的时间有一些大小限制。一共有mm 组限制,第ii 组限制可以用两个正整数li,ril_{i},r_{i}表示 (1≤li<ri≤n)(1\le l_{i}<r_{i}\le n) ,具体意义是编号在[li,ri)[l_{i},r_{i}) 的硬件的安装依赖于第rir_{i}个硬件的安装,因此它们的安装时间不早于编号为rir_{i} 的硬件的安装时间(安装时间可以相等)。

所以你会发现,完全按照预定的安装时间安装每个硬件,这mm 组限制不会全满足。因此你要调整这些硬件的安装时间。而你希望每个硬件的实际安装时间与预定安装时间的总偏离程度最小。对于第ii 个硬件,如果它的实际安装时间比预定安装时间早,那么早每个单位时间都会使总偏离程度增加aia_{i}; 如果它的实际安装时间比预定安装时间晚,那么晚每个单位时间都会使总偏离程度增加bib_{i} 。现在你的任务就是把总偏离程度的最小值算出来。

Input

第一行输入两个正整数n,mn,m,表示硬件的个数和限制的个数。

接下来nn行,每行三个正整数ti,ai,bit_{i},a_{i},b_{i},意义与题目描述相同。 接下来mm行,每行两个正整数li,ril_{i},r_{i} ,意义与题目描述相同。

Output

仅一行,表示总偏离程度的最小值。

Examples

样例输入

5 1
1 100 1
1 100 1
1 100 1
1 100 1
2 1000000 1
1 5

样例输出

4

原 PDF 样例最后一台硬件的提前代价为 19260817,超过其声明的 ai≤106a_i\le10^6。上例改为 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:对于任意1≤i≤n,ti∈{1,2}1\le i\le n,t_{i}\in \{1,2\} 。 特殊性质 2:对于任意1≤i≤m,ri−li=11\le i\le m,r_{i}-l_{i}=1 。

Subtask 1 (points: 10)

保证n≤17,m≤17n\le 17,m\le 17,且满足特殊性质 1.

Subtask 2 (points: 10)

保证n≤300000,m≤1n\le 300000,m\le 1.

Subtask 3 (points: 15)

保证n≤3000,m≤3000n\le 3000,m\le 3000,且满足特殊性质 2.

Subtask 4 (points: 20)

保证n≤300000,m≤300000n\le 300000,m\le 300000,且满足特殊性质 2.

Subtask 5 (points: 25)

保证n≤3000,m≤3000n\le 3000,m\le 3000。

Subtask 6 (points: 20)

保证n≤300000,m≤300000n\le 300000,m\le 300000。