该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

好的作业

题目背景

开学了，Genius_Star 的作业还没有做完，于是他打算使用一次时光机来弥补遗憾。

题目描述

寒假期间，老师给 Genius_Star 布置了 $n$ 个学科的作业，第 $i$ 个学科至少要做 $b_i$ 页。

但是 Genius_Star 上课睡觉没听到，只做了 $a_i$ 页；定义他完成了第 $i$ 项作业当且仅当 $a_i \ge b_i$。

定义一个作业子区间 $[l, r]$ 是好的，当且仅当这个区间内的所有作业都被完成了。

开学时，会有 $q$ 个老师来检查作业，第 $i$ 个老师的评分是区间 $[l_i, r_i]$ 中好的子区间的个数。

最终 Genius_Star 的总得分是所有老师评分的和。

他有一个仅能使用一次的时光机，可以选择一个科目 $x$，直接令其作业变为已完成状态（也就是强制让 $a_x \ge b_x$）。

你的任务是：

1. 求出使用一次时光机后，能获得的最大总得分。
2. 在得分最大的前提下，选择编号最小的科目 $x$。

输入格式

输入共 $3 + q$ 行：

1. 第一行：两个正整数 $n, q$，分别表示作业数量和老师数量。
2. 第二行：$n$ 个非负整数 $a_i$，表示每个科目实际完成的页数。
3. 第三行：$n$ 个非负整数 $b_i$，表示每个科目要求完成的页数。
4. 接下来 $q$ 行：每行两个正整数 $l_i, r_i$，表示第 $i$ 个老师的检查区间。

输出格式

输出一行两个正整数，用空格隔开： x ans

• $x$：选择穿越的科目编号（从1开始）。
• $ans$：穿越后的最大总得分。

样例

样例 1

输入：

5 1
5 5 1 5 5
1 1 2 1 1
1 5

输出：

3 15

样例 2

输入：

6 4
5 1 5 1 5 1
1 2 1 2 1 2
1 3
5 6
5 6
5 6

输出：

6 11

样例 3

输入：

9 2
5 5 5 1 5 5 5 5 1
1 1 1 2 1 1 1 1 2
3 5
5 9

输出：

9 17

数据范围与子任务

• 对于 100% 的数据：$1 \le n, q \le 10^5,\ 1 \le a_i, b_i \le 10$。
• 本题采用捆绑测试：

提示：部分测试点输入量较大，请使用快速 I/O 方式。