Мечето Мендо обожава мед, но собирањето на мед не е секогаш лесно. Високо над него, група вредни пчели произведуваат мед, кој повремено паѓа надолу кон земјата. Сепак, Мендо забележал дека капките мед паѓаат непредвидливо, секоја започнувајќи од различна висина и позиција.

Мендо сака да го постави својот сад (во кој ќе го собира медот) на земјата (односно на x-оската) за да го собере медот. Секоја капка мед паѓа право надолу со брзина од 1 единица во секунда.

Мендо сака да се осигура дека садот ќе собира мед непрекинато барем D секунди, што значи дека разликата во времето помеѓу првата капка што паѓа во садот и последната капка што паѓа во садот треба да е барем D секунди. Капка која паѓа точно на работ на садот се смета дека е во садот.

Мендо може слободно да ја одбере позицијата и ширината W на садот, но сака да ја минимизира ширината W за да не мора да носи премногу голем и тежок сад.

Влез

Првата линија содржи два цели броеви N (1 ≤ N ≤ 10⁶) и D (1 ≤ D ≤ 10⁶) - бројот на капки мед и времето на собирање, соодветно.

Следните N линии содржат по два цели броеви x и y (0 ≤ x, y ≤ 10⁹) - координатите на капка мед. Капката се појавува на висина y и паѓа директно надолу се до y = 0.

Забелешка. За 20% од поените важи: N, D ≤ 1 000.
За останати 40% од поените важи: N ≤ 100 000.

Излез

Отпечатете еден цел број – минималната можна ширина W (W > 0) на садот. Ако не постои решение, отпечатете -1.

Ограничувања

Временско ограничување: 500 milliseconds
Мемориско ограничување: 64 megabytes

Примери

влез
5 4
2 2
7 7
5 2
3 4
6 4

излез
2

влез
5 2
2 2
7 7
5 2
3 4
6 4

излез
1