伊万·阿纳托利耶维奇的机构开始在镇上出名。
他们已经订购并制作了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 的愿望不满足电视频道的选项,段不相交,因此答案为零。