Problem Statement

アットコーダーモンスターズと言うゲームは、モンスターのチームを編成してバトルするゲームです。

あなたはモンスターを売っているお店にいます。 このお店では、$N$ 匹のモンスターが横一列に並べられています。そして、各モンスター $A_i (1 ≦ i ≦N)$ には以下に示す $2$ つの能力値が存在しています。

• モンスター $M_i$ のこうげきの能力を表す値 ${M_i}_{ATK}$
• モンスター $M_i$ のぼうぎょの能力を表す値 ${M_i}_{DEF}$

いま、$N$ 匹のモンスターの中から異なるちょうど $K$ 匹のモンスターを選んで購入し、それらでチームを編成しようとしています。 しかし、ある能力値について、それらがかけ離れたモンスター同士がいるとチームとして安定しないことが分かっているので、できるだけ安定したチームを作りたいと思っています。

より厳密に、チームに含まれる $2$ 匹のモンスター $X$ と $Y$ についてその不安定度 $S_{X,Y}$ を、

• $S_{X,Y}$ = max{ $|X_{ATK} - Y_{ATK}|$, $|X_{DEF} - Y_{DEF}|$ }

と定義したとき、チームの不安定度は、チームに含まれる全てのモンスターのペアについて計算して得られる不安定度の最大値です。 チームに含まれるモンスターが $1$ 匹の時、チームの不安定度は $0$ です。

あなたは、チームの不安定度を最小化するような異なる $K$ 匹のモンスターを購入しようと思っています。 さらに、チームの不安定度を最小とするようなモンスターの選び方の総数も求めたいと思っています。

あなたは、達成できるチームの不安定度の最小値と、それを達成するモンスターの選び方の総数を $1,000,000,007$ で割った余りを出力しなければなりません。

Input

入力は以下の形式で標準入力から与えられる。

N K
{M_1}_{ATK} {M_1}_{DEF}
{M_2}_{ATK} {M_2}_{DEF}
:
{M_N}_{ATK} {M_N}_{DEF}

• $1$ 行目には、お店に並んでいるモンスターの数と購入したいモンスターの数を表す $2$ つの整数 $N (1 ≦ N ≦ 100,000)$ と $K (1 ≦ K ≦ N)$ がスペース区切りで与えられる.
• $2$ 行目から $N$ 行には、お店に並んでいるモンスターの能力値の情報が与えられる。そのうち $i$ 行目には、$i$ 番目のモンスターの能力値を表す $2$ つの整数 ${M_i}_{ATK}, {M_i}_{DEF} (0 ≦ {M_i}_{ATK}, {M_i}_{DEF} ≦ 3000)$ がスペース区切りで与えられる。

部分点

この問題には部分点が設定されている。

• $10$ 点分のテストケースにおいて、$1≦N≦20$ を満たす。

Output

$1$ 行目には、達成できるチームの不安定度の最小値を出力せよ。

$2$ 行目には、チームの不安定度を最小化するようなモンスターの選び方の総数を $1000000007$ で割った余りを出力せよ。

末尾の改行を忘れないこと。