#765. [Lydsy1706月赛]城市规划

[Lydsy1706月赛]城市规划

Description

最近比特镇正在迅速建成。沿着美丽的大街,一座座新建筑拔地而起。小Q喜欢沿着大街走,但问题是不同的建筑位于街对面。为了从一个建筑到另一个建筑,有时需要通过漫长的步行穿过最近的人行道。所以他决定写一个程序,计算如何沿着大街平移所有人行道,使得人行道的布局最有利于行人。他希望尽可能多的人行道出现在某些建筑物的前面,同时人行道的移动距离应当是最小的。

大街以直线表示,人行道被视为这条线上的点。所有建筑物都平行于大街,所以你可以认为它们是直线上的一条条线段。每条线段都具有左边界和右边界。如果某人行道位于某建筑物的左右边界之间(包括边界点),则你可以认为该人行道位于该建筑物的前方。由于人行道已经按照某些标准建立,小Q决定保持它们之间的距离,所以他想将所有的人行道移动相同的距离。

请帮助小Q写一个程序计算最优布局

Format

Input

第一行包含两个正整数n,m(1<=n<=10000,1<=m<=1000),分别表示人行道和建筑的个数。

第二行包含n个整数a_i(0<=a_i<=10^6),分别表示每条人行道的坐标,可能存在两条人行道重合。

接下来m行,每行两个整数l_i,r_i(0<=l_i<r_i<=10^6),分别表示每座建筑的左右边界,这些线段可以相互重叠。

Output

输出一行两个整数d和s,其中d表示平移距离的绝对值,s表示出现在至少一座建筑物前面的人行道个数。你需要输出s最大的解,若有多个d使得s最大,那么输出d最小的解。注意你可以向左或者向右平移人行道。

Samples

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