A Pie for a Pie#10515
Bessie and Elsie have each baked pies. Each of the pies has a tastiness value assigned by Bessie and a (possibly different) tastiness value assigned by Elsie.
Bessie is considering giving one of her pies to Elsie. If Elsie receives a pie from Bessie, she will feel obligated to give one of her own pies to Bessie in return. To avoid appearing either stingy or overly generous, Elsie will try to choose a pie that she considers at least as tasty as the pie she received, but no more than units tastier. Such a pie may not exist, in which case Elsie will adopt a pseudonym and exile herself to Japan.
If Elsie does give Bessie a pie in return, Bessie will similarly try to give Elsie a pie that she considers at least as tasty, but no more than units tastier, than the pie Elsie just gave her. If this is impossible, Bessie too will exile herself. Otherwise, she gives her chosen pie to Elsie. This process continues until either one of the cows is exiled, resulting in an unhappy outcome, or one of the cows receives a pie that she considers to have a tastiness value of , in which case the gift exchange ends and both cows are happy.
Note that no pie may be gifted more than once, and neither cow may return a pie that she has received.
For each of the pies that Bessie could choose as her initial gift to Elsie, determine the minimum number of pies that could be gifted in the resulting exchange before the cows are happy.
The first line contains two integers n~(1 \le n \le 10^5) and d~(0 \le d \le 10^9). The next lines each contain two space-separated integers, representing the tastiness values of a particular pie according to Bessie and Elsie, respectively.
The first lines describe Bessie's pies, and the remaining lines describe Elsie's pies.
It is guaranteed that all tastiness values are in the range [0, 10^9].
Print lines. Line should contain a single integer: the minimum number of pies that could be gifted in a happy gift exchange starting with Bessie's pie . If no happy gift exchange can be started with pie , print instead.
Example 1