Bütün Dəhşətlərin İnteqralı
Deep Horizon neft sızması 2010-cu ildə baş verdikdən sonra, ACME Inc. uzaqdan neft sızmalarını bağlamaq üçün yüksək texnologiyalı hissəcik şüası istifadə edən bir maşın hazırladı. Prototipi sınaqdan keçirmək üçün ACME sualtı sınaq sahəsi qurdu və burada n müstəqil neft sızması mövcuddur ki, bunlar L_1, L_2, ..., L_n adlanır.
Hər bir sızma L_i (1 ≤ i ≤ n) r_i və t_i parametrləri ilə təsvir olunur. r_i ilkin neft sızma sürətidir və litr/saniyə (L/s) ilə ölçülür. Hissəcik şüası L_i üzərində işlədikcə, sızma sürəti xətti olaraq azalır və t_i saniyə sonra 0 L/s (yəni bağlanmış) olur.
Məsələn, L_1 r_1 = 20 və t_1 = 4 ilə təsvir olunsun. İlkin olaraq neft 20 L/s sürətlə axır. Bağlama prosesinin 1 saniyəsindən sonra sürət 15 L/s olur; 2 saniyədən sonra sürət 10 L/s olur; 3 s sonra 5 L/s olur; və 4 s sonra sızma bağlanır. Bu 4 saniyə ərzində L_1 sızmasından axan ümumi neft həcmi 20 (L/s) × 4 (s) / 2 = 40 L (üçbucağın sahəsi) olur. Bu müddətdə digər sızmalar neft axıtmağa davam edir və hissəcik şüası onlara yönəldilənə qədər təsirlənmir.
Maşını nümayiş etdirmək sizin məsuliyyətinizdir. t = 0 vaxtında siz sızmaları bağlamaq üçün şüanı aktivləşdirirsiniz. Hissəcik şüası sızmaya hədəflənmək üçün əhəmiyyətsiz vaxt alır və heç vaxt boş qalmır. Buna görə hər bir sızma t = t_1 + t_2 + ... + t_n vaxtında bağlanır (və sonra hər kəs alqışlayır). Lakin, sınaq zamanı çoxlu neft sızacaq. Dəqiq miqdar, nümayiş zamanı hissəcik şüasını necə hədəflədiyinizdən asılıdır.
L_1, L_2, ..., L_n parametrləri verildikdə, t = 0 (hissəcik açılır) və t = t_1 + t_2 + ... + t_n (bütün sızmalar bağlanır) arasında sızan neftin ümumi həcmini (litrlə) minimuma endirmək sizin vəzifənizdir. Qeyd edək ki, bir neçə test halı var (hamısı bir-birindən müstəqildir).
Giriş verilənləri
Birinci giriş sətri test halların sayı N, 1 ≤ N ≤ 50 verir.
Hər bir test halı bir tam ədəd n ilə başlayan bir sətirdən ibarətdir. Sonrakı n sətirin hər biri L_i (üçün 1 ≤ i ≤ n) iki tam ədəd r_i və t_i ilə göstərir, boşluqla ayrılmışdır.
n neft sızmalarının ümumi sayıdır və 1 ≤ n ≤ 50 şərtini ödəyir.
r_i L_i-nin ilkin sızma sürətidir (L/s) və 1 ≤ r_i ≤ 500 şərtini ödəyir.
t_i L_i-ni bağlamaq üçün ümumi şüa vaxtıdır (s) və 1 ≤ t_i ≤ 500 şərtini ödəyir.
Çıxış verilənləri
Hər bir test halı üçün sınaq zamanı sızan neftin minimum mümkün ümumi həcmini (litrlə) 2 onluq dəqiqliklə çap edin.