DAS Növbə
Son illərdə elektron növbələr gündəlik həyatımıza sıx şəkildə daxil olub. Bir çox dövlət qurumlarında, ziyarətçilərin "Axırıncı kimdir?" sualını vermədən, elektron tablo vasitəsilə nə qədər gözləməli olduqlarını və növbələrinin nə vaxt çatacağını öyrənə bildikləri terminallara rast gəlmək mümkündür.
Lakin, bu sistemlər hələ də mükəmməl deyil. Məsələn, standart təsadüfi növbə prinsipi bəzi suallar doğurur: "Birinci gələn birinci xidmət alır". DAS "Növbə" adlı innovativ sistemin hazırlanması zamanı bu prinsipin tətbiqinə ehtiyac olmadığı qərara alındı. Bunun əvəzinə, yeni sistem növbədə duran insanların qəbuluna gələn məmura düşən neqativin miqdarını minimuma endirməyə yönəldilmişdir.
Məlumdur ki, hər bir insanın qıcıqlanma əmsalı var. Əgər bu parametr w bərabərdirsə, növbədə t saat gözlədikdən sonra bu insan məmura dəqiq wt vahid qəzəb və söyüş tökəcək. Belə ki, ziyarətçiyə dərhal gəldikdən sonra xidmət göstərilsə, məmur zərər görməyəcək. Amma ziyarətçi üçüncü saatın əvvəlində gəlib, ona yalnız beşinci saatın əvvəlində xidmət göstərilsə, qəzəb miqdarı 2w olacaq.
Həmçinin məlumdur ki, hər bir ziyarətçiyə xidmət göstərilməsi dəqiq bir saat çəkir və hər bir ziyarətçi hansısa saatın əvvəlində gəlir. Sizin vəzifəniz, ziyarətçilərin qıcıqlanma göstəriciləri və gəlmə vaxtları verildikdə, optimal xidmət sırası ilə məmura düşəcək neqativin miqdarını müəyyən etməkdir.
Giriş verilənləri
Birinci sətirdə bir tam ədəd t verilir — işləməli olduğunuz hallar sayı. Sonra isə t halların təsvirləri gəlir.
Hər bir halın təsviri: birinci sətirdə n ədəd — ziyarətçilərin sayı və n ziyarətçinin təsvirləri. Hər bir ziyarətçi üçün ayrıca sətirdə iki tam ədəd r_i və w_i (1 ≤ r_i, w_i ≤ 10^6) — ziyarətçinin gəldiyi saatın nömrəsi və onun qıcıqlanma əmsalı, müvafiq olaraq.
Bir testin bütün hallarında ziyarətçilərin ümumi sayı 10^5-i keçmir.
Çıxış verilənləri
Hər bir hal üçün ayrıca sətirdə cavabı yazın — məmurun alacağı minimal ümumi neqativ miqdarını.