Piroq üçün piroq
Besi və Elzanın hər birində n piroq var. Bu 2n piroqun hər biri Besinin və Elzanın fikrincə bir dadlılıq dəyərinə malikdir, bu dəyərlər fərqli ola bilər.
Besi öz piroqlarından birini Elzaya vermək istəyir. Əgər Elza Besidən piroq alarsa, o, öz piroqlarından birini Besiyə verməlidir. Elza nə xəsis, nə də səxavətli olmaq istəmir, ona görə də aldığı piroq qədər dadlı (Elzanın fikrincə) və ən çox d vahid daha dadlı bir piroq seçməyə çalışacaq. Belə bir piroq mövcud olmaya bilər, bu halda Elza Yaponiyaya qaçacaq.
Əgər Elza əvəzində Besiyə piroq verərsə, Besi də eyni şəkildə aldığı piroq qədər dadlı (Besinin fikrincə) və ən çox d vahid daha dadlı bir piroq verməyə çalışacaq. Əgər Besi bunu edə bilməzsə, o da qaçacaq. Əks halda, Elzaya piroq verəcək. Bu dövrə mümkün olduğu qədər davam edir və ya inəkdən biri dadlılıq dəyəri 0 olan piroq alana qədər, bu halda proses bitir və hər iki inək xoşbəxt olur.
Qeyd edək ki, eyni piroq iki dəfə hədiyyə edilə bilməz və piroq onu hədiyyə edən inəyə geri qayıda bilməz.
Besi hər bir n piroqundan birini Elzaya başlanğıc hədiyyə kimi seçə bilər. Hər iki inəyin xoşbəxt olması üçün hədiyyə edilə biləcək minimum piroq sayını müəyyən edin.
Giriş Məlumatları
Birinci sətir iki tam ədəd n (1 ≤ n ≤ 10^5) və d (0 ≤ d ≤ 10^9) ehtiva edir. Növbəti 2n sətir hər biri boşluqla ayrılmış iki tam ədəd ehtiva edir, müvafiq olaraq həmin piroqun Besinin və Elzanın fikrincə dadlılıq dəyərini göstərir.
İlk n sətir Besinin piroqları, qalan n sətir Elzanın piroqları haqqındadır.
Bütün dadlılıq dəyərlərinin [0, 10^9] intervalında olduğu təmin edilir.
Çıxış Məlumatları
Çıxışda n sətir olmalıdır. i-ci sətir xoşbəxt nəticə ilə hədiyyə edilə biləcək minimum piroq sayını ehtiva etməlidir, əgər Besi i-ci piroqla başlasa. Əgər i-ci piroqla başlamaqla xoşbəxt nəticə mümkün deyilsə, i-ci sətir -1 ehtiva etməlidir.