#1029. 魔法星球

内存限制:512 MiB 时间限制:2000 ms 标准输入输出
题目类型:传统 评测方式:Special Judge
上传者: tony102

题目描述

在一个遥远的星球上,有一个名为“Zentra” 的古老王国,王国中有 个学派各自拥有独特的魔法知识,想要在“Eterna”节日期间通过王国的 个魔法水晶塔传播自己的魔法。每个学派的魔法仅能在特定的时间段 内有效展现其魔法效果,而每个魔法水晶塔则在固定的时间段 激活,能够向周围的民众传达魔法,每个塔因其独特的魔力结晶,能吸引 名民众观看。

若某个学派选择在某个魔法水晶塔上展示其魔法,其影响力收益将根据魔法展示的实际时间段 ——即学派的魔法有效时间与水晶塔激活时间的交集——与该塔吸引的观众数量 的乘积来计算,公式为

在“Eterna”节日期间,学派们希望通过精心选择魔法水晶塔来最大化其魔法的影响力。

请编写一个计划,帮助所有学派确定如何选择魔法水晶塔,以便最大化总的影响力收益。

输入格式

第一行两个正整数

接下来 行,每行两个非负整数

接下来 行,每行两个非负整数 和一个正整数

输出格式

第一行一个非负整数代表最大收益。

若最大收益不为 ,第二行输出两个正整数 ,代表选择第 个广告和第 个电视台时收益最大。

样例

样例输入 1

2 3
7 9
1 4
2 8 2
0 4 1
8 9 3

样例输出 1

4
2 1

样例输入 2

1 1
0 0
1 1 10

样例输出 2

0

数据范围与提示

对于 的数据,保证

对于 的数据,保证

对于 的数据,保证: