题目描述

动物园里有 $n$ 头麋鹿。每头麋鹿有两支茸角，每支茸角有一个重量。然而，一旦某头麋鹿上两支茸角的重量之差过大，这头麋鹿就会失去平衡摔倒。为了不然这种悲剧发生，动物园院长决定交换某些茸角，使得任意一头麋鹿的两角重量差不超过 $c$。然而，交换两支茸角十分麻烦，不仅因为茸角需要多个人来搬运，而且会给麋鹿造成痛苦。因此，你需要计算出最少交换次数，使得任意一头麋鹿的两角重量差不超过 $c$。

注意，交换两支茸角只能在两头麋鹿之间进行。因为交换同一头麋鹿的两支角是没有意义的。

输入格式

第一行为整数 $n,c$。

接下来 $n$ 行，每行两个整数，分别表示一开始每头麋鹿的两角重量。

输出格式

一个数，即最少交换次数。如果无论如何也不能使每头麋鹿平衡，输出 $-1$。

输入输出样例 #1

3 0
3 3
2 5
2 5

1

数据范围

对于 $100\%$ 的数据，$n \le 16$，$c \le 1000000$，每支茸角重量不超过 $1000000$。