Daxili komanda növbəsi
Daxili Komanda Növbəsi (Native Command Queuing, NCQ) - SATA cihazlarında performansı artırmaq üçün istifadə olunan bir texnologiyadır. NCQ, cihazın daxili arxitekturasını nəzərə alaraq sorğuları toplayır və onların icra sırasını optimallaşdırır. Bu, başlıqların hərəkətini minimuma endirmək və trekdə lazım olan sektorun gözləmə müddətini azaltmaq məqsədini güdür. Bu məsələdə, biz bəzi amillərin dəyərini nəzərə almayacağıq və yalnız SATA cihazının oxuma başlığının hərəkət vaxtını nəzərə alacağıq. Başlanğıcda başlığın 0 mövqeyində olduğunu qəbul edəcəyik. Onun hərəkət sürəti 1 (bir mövqe milisaniyədə) bərabərdir. Sizə (x_i, t_i) şəklində komandalar verilir, burada x_i - məlumatın oxunmalı (və ya yazılmalı) olduğu mövqe, t_i - sorğunun daxilolma vaxtıdır. Sorğular mütləq daxilolma sırasına uyğun işlənməli deyil. Əsas odur ki, cihazın başlığı x_i mövqeyini t_i vaxtında və ya daha sonra tutsun. Oxuma/yazma vaxtını əhəmiyyətsiz dərəcədə kiçik hesab edəcəyik. Cihazın bütün daxil olan komandaları işləməsi üçün lazım olan ən az vaxtı tapın.
Giriş verilənləri
Giriş faylının ilk sətirində n (1 ≤ n ≤ 2000) - daxil olan komandaların sayı qeyd olunub. Sonra komandaların özləri - hər biri bir sətirdə sadalanır. Komandalar tam ədədlər cütü x_i, t_i ilə verilir (-10^6 ≤ x_i ≤ 10^6; 0 ≤ t_i ≤ 10^6).
Çıxış verilənləri
Tək bir ədəd çıxarın - bütün komandaların işlənməsi üçün lazım olan ən az vaxt.