D. 魔法星球

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

题目描述

在一个遥远的星球上,有一个名为“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

数据范围与提示

对于 的数据,保证

对于 的数据,保证

对于 的数据,保证: