← 返回题目列表

Codeforces · 542/A

A. 在此放置您的广告

中文机器翻译题面 查看原题

伊万·阿纳托利耶维奇的机构开始在镇上出名。

他们已经订购并制作了n个电视广告视频。每个视频都以特殊的方式制作:颜色和配乐根据一天中的时间和观众的心情进行调整。这就是为什么第i个视频只能在[li,ri]的时间范围内播放(不必使用整个片段,但播放时间应该在该片段内)。

现在是时候选择一个电视频道来播放广告了。总体而言,该城市有 m 个电视频道在播出,第 j 个频道有 cj 个观众,并准备出售时间 [aj, bj] 来播放广告。

Ivan Anatolyevich 面临着一个艰难的选择:他必须选择恰好一个视频 i 和恰好一个电视频道 j 来播放该视频,以及播放的时间范围 [x, y]。此时应选择时间范围,使其既在范围 [li, ri] 内又在范围 [aj, bj] 内。

让我们将广播效率定义为值 (y - x)·cj — 电视频道的所有观众观看广告的时间总和。帮助伊万·阿纳托利耶维奇以最高效率选择转播!

输入

第一行包含两个整数 n 和 m (1 ≤ n, m ≤ 2·105) - 分别是商业视频和频道的数量。

接下来的 n 行每行包含两个整数 li, ri (0 ≤ li ≤ ri ≤ 109) – 可以播放相应视频的时间段。

以下 m 行每行包含三个整数 aj、bj、cj (0 ≤ aj ≤ bj ≤ 109, 1 ≤ cj ≤ 109),表征电视频道。

输出

在第一行打印一个整数 - 广播的最大可能效率。如果没有正确的方法来获得严格的正效率,请打印零。

如果最大效率严格为正,则在第二行中还打印最有效播放中视频 i (1 ≤ i ≤ n) 的编号和电视频道 j (1 ≤ j ≤ m) 的编号。

如果有多个最佳答案,您可以打印其中任何一个。

示例

输入 #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

注意

在第一个示例测试中,最佳解决方案是在时间 [2, 4] 使用第一个电视频道播放第二个广告。该解的效率等于(4 - 2)·2 = 4。

在第二个样本测试中,Ivan Anatolievich 的愿望不满足电视频道的选项,段不相交,因此答案为零。