Biçin
Gənc kuzənlər Bessi, Ella və Bella fermaya baş çəkdilər. Təəssüf ki, gəldikləri andan etibarən yalnız zərər gətirdilər.
Son macəralarında mümkün qədər çox ot biçməyə qərar verdilər. Fermadakı ən yaxşı otlaqlar böyük kvadrat t × t formasındadır. Sol alt küncün koordinatları (0, 0), sağ üst küncün isə (t, t) şəklindədir. Beləliklə, kvadrat (t + 1) * (t + 1) ızgara nöqtələrini (tam ədədi koordinatları olan nöqtələr) ehtiva edir.
Ella və Bella (0, 0) nöqtəsindən başlayıb, (t, t) nöqtəsinə qədər vahid sürətlə hərəkət etməyi planlaşdırırlar, çox iti və çox uzun bir telin uclarını tutaraq. Bu telin keçəcəyi hər hansı bir sahədəki otlar biçilir. Ella və Bella fərqli yollarla gedə bilərlər, lakin hər bir yol yalnız yuxarı və sağa addımlardan ibarətdir, ızgara nöqtələri boyunca keçidlər edərək.
Bessi çox narahatdır ki, çox ot biçilə bilər, buna görə də Ella və Bellanın gedəcəyi yolları məhdudlaşdırmaq üçün ağıllı bir plan hazırlayır. Çəmənliklərdə n dadlı çiçək səpələnmişdir, hər biri ayrı bir ızgara nöqtəsində yerləşir. Bessi S çiçəklər dəstini seçir ki, Ella və Bella onları ziyarət etməlidirlər (belə ki, Ella'nın yolu S-dəki bütün çiçəkləri ziyarət etməlidir, Bella'nın yolu da). Bu yollara mümkün qədər çox yol nöqtəsi əlavə etmək üçün Bessi S-ni, (0, 0) nöqtəsindən (t, t) nöqtəsinə qədər yuxarı və sağa hərəkət edən bir inəyin ziyarət edə biləcəyi çiçəklərin alt dəstləri arasında mümkün qədər böyük seçəcək.
Ella və Bella, S-dəki çiçəkləri ziyarət etmək məhdudiyyətini nəzərə alaraq mümkün qədər çox ot biçməyə çalışacaqlar. Bessiyə S-ni elə seçməyə kömək edin ki, biçilən otun miqdarı mümkün qədər az olsun.
Giriş Məlumatları
Birinci sətir n (1 ≤ n ≤ 2 * 10^5) və t (1 ≤ t ≤ 10^6) ədədlərini ehtiva edir. Növbəti n sətirin hər biri çiçəyin tam ədədi koordinatlarını (x[i], y[i]) ehtiva edir. Bütün i üçün 1 ≤ x[i], y[i] ≤ t − 1 təmin edilir və heç bir iki çiçək eyni üfüqi və ya şaquli xətt üzərində yerləşmir.
Çıxış Məlumatları
Bir tam ədəd çıxarın - biçilməli olan otun minimal mümkün miqdarı.
Nümunə
Bu nümunədə Bessi üçün optimal olaraq (10, 3) və (13, 11) nöqtələrindəki çiçəkləri toplamaqdır. Ən pis halda Ella və Bella ümumi sahəsi 117 olan üç ot düzbucağı biçəcəklər.