交换茸角

时间限制:20s      空间限制:512MB

题目描述

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


输入格式

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


输出格式

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


样例输入

3 0
3 3
2 5
2 5

样例输出

1

提示

对于 100% 的数据,n <= 16, c <= 1000000, 每支茸角重量不超过 1000000。


题目来源

By 佚名提供