Organizers of international competitions have a lot of things to think about: tasks, competition systems, accommodation for contestants and their leaders, medals, etc. For the current competition, the chairman wants to help leaders and contestants with their luggage (traveling bags), by sending some of the organizers to carry them from the hotel to the airport.

Each of the organizers can carry two bags (one in each hand). Unfortunately, most of the organizers don’t do sports, and they may injure themselves if they carry bags of dissimilar weight (if one of the bags is much heavier than the other) for a longer period of time.

For each of the N organizers you know the weight of the bags they initially have in each of their hands (Li and Ri). You are also given a non-negative integer X, which is the maximum difference between the weight of the bags that each of the organizers can carry. For example, if X=2, then an organizer can carry bags of weight 3 and 5, for example, but he can’t carry bags of weight 2 and 5 (because 5-2 > X).

The initial distribution of the bags might not be good. In that case, the organizers may be able to finish the task if they swap some bags between each other, before they start their trip to the airport. In one swap, you can choose a bag carried by one organizer, and swap it with a bag carried by another one. Help the organizers by calculating the minimum number of swaps that need to be made, so that no organizer carries two bags whose difference in weight is larger than X.

Input

The first line contains two positive integer numbers N (1 <= N <= 16), and X (0 <= X <= 1 000 000), describing the number of organizers that will carry bags, and the maximum difference in weight between the two bags (that an organizer can carry).

Each of the following N lines contains two positive integers Li and Ri (1 <= Li, Ri <= 1 000 000), the weights of the two bags that the i-th organizer is initially carrying.

Output

Print the required minimum number of swaps, or -1 if it’s impossible to finish the task.

Constraints

Time limit: 1 second
Memory limit: 256 megabytes

Examples

input
4 1
5 5
2 7
2 6
3 3

output
1

input
3 0
1 3
3 5
5 1

output
2

Explanation for the first test: You can swap the bag carried by the second organizer in his left hand (weight 2), with the bag carried by the third organizer in his right hand (weight 6).


Subtasks
 1) In test cases worth 11 points, (1 <= N <= 5)
 2) In other test cases worth 26 points, (1 <= N <= 10)
 3) To earn all 100 points, your solution must work for the input constraints presented in the “Input” section.