样例下载

问题描述

数轴上有 $N$ 头奶牛，第 $i$ 头奶牛的坐标为 $X_i$。同一个位置可能有多头奶牛。

数轴上还有 $M$ 个条形食槽，第 $i$ 个食槽的左端点坐标为 $L_i$，右端点坐标为 $R_i$。同一个位置可能有多个食槽，不同的食槽可能有重叠。

如果一头奶牛的坐标位于一个食槽之间，则奶牛会在这个食槽内进食。具体地，若奶牛 $i$ 在食槽 $j$ 之间，即 $L_j ≤ X_i ≤ R_j$，则奶牛 $i$ 会在食槽 $j$ 内进食。如果一头奶牛不在任何一个食槽前，则它无法进食。

Farmer John 要去看一下奶牛的进食情况。如果同时进食的奶牛数量非常多，John 会认为这些奶牛被饲养得非常好。

为此，你准备同时平移所有奶牛。奶牛的平移方向和距离均相同。

你希望经过你的平移后，同时进食的奶牛的数量达到最多。

问：你最多可以使多少头奶牛同时进食？并输出奶牛的平移距离。如果有多个距离满足要求，你需要输出最小的平移距离。

输入

第一行：两个整数 $N$, $M$

第二行：$N$ 个整数 $X_i$

接下来 $M$ 行：每行两个整数 $L_i, R_i$

输出

两个整数，中间以单个空格隔开，依次表示最小的平移距离和最多进食的奶牛数量。

样例输入

5 2
1 2 6 8 6
4 6
5 6

样例输出

2 3

数据范围

$1 ≤ N ≤ 10000,1 ≤ M ≤ 1000，0 ≤ X_i ≤ 10^6，0 ≤ L_i < R_i ≤ 10^6$