Kazak Vus və seqmentlər#10486
Son zamanlar Kazak Vus koordinat düz xəttində parça tapdı. Bu parçalar iki koordinatla verilir: a_i — parçanın başlanğıcı və b_i — parçanın sonu.
Kazak Vus uzunluğu olan iki yeni parça yerləşdirmək istəyir ki, bu iki parça kəsişməsin. Qoy — birinci parçanın tamamilə yerləşdiyi parçaların sayı olsun. Eyni şəkildə, — ikinci parçanın tamamilə yerləşdiyi parçaların sayı olsun.
Kazak Vus bu parçanı elə yerləşdirmək istəyir ki, x+y ədədi mümkün qədər böyük olsun. Ona bu ədədi tapmağa kömək edin.
Qeyd edin ki, bir parça eyni zamanda bu iki yeni parçanı tamamilə yerləşdirə bilər.
Qeyd 1. Qoy k_1, k_2(k_1 < k_2) — yeni parçaların başlanğıcları olsun. Onda bu parçalar kəsişməz, əgər k_1+m \le k_2.
Qeyd 2. Başlanğıcı olan yeni parça [l, r] parçasında tamamilə yerləşir, əgər l \le k və k+m \le r.
Birinci sətir iki tam ədəd və (1 \le n \le 3 \cdot 10^5, 1 \le m \le 10^8) — parçaların sayı və yeni parçaların uzunluğunu ehtiva edir.
Növbəti sətirin hər biri iki tam ədəd a_i, b_i (1 \le a_i < b_i \le 10^8) — müvafiq parçanın başlanğıc və son koordinatlarını ehtiva edir.
Yeganə ədəd çıxarın — x+y ifadəsinin mümkün olan maksimum dəyəri.
Nümunə 1
( bal): n, m, a_i, b_i \le 200;
( bal): n \le 200;
( bal): n \le 2000;
( bal): n \le 2 \cdot 10^5, m=1;
( bal): əlavə məhdudiyyətlərsiz.