İncilər#3230
Pearlaniyada hər kəs mirvariləri sevir. "The Royal Pearl" adlı bir şirkət, içində mirvarilər olan çoxlu zərgərlik məmulatları istehsal edir. Şirkət adını Pearlaniyanın kral ailəsinə xidmət göstərdiyi üçün alıb. Amma o, adi insanlar üçün də bilərziklər və boyunbağılar istehsal edir. Təbii ki, bu insanlar üçün mirvarilərin keyfiyyəti kral ailəsi üçün olan mirvarilərin keyfiyyətindən daha aşağıdır. Pearlaniyada mirvarilər 100 fərqli keyfiyyət sinifinə bölünür. Keyfiyyət sinfi bir mirvarinin həmin keyfiyyət sinfindəki qiyməti ilə müəyyən edilir. Bu qiymət həmin keyfiyyət sinfi üçün unikaldır və həmişə aşağı keyfiyyət sinfindəki mirvarinin qiymətindən yüksəkdir.
Hər ay "The Royal Pearl" şirkətinin anbar müdiri hər keyfiyyət sinfində lazım olan mirvarilərin sayını göstərən bir siyahı hazırlayır. Mirvarilər yerli mirvari bazarında alınır. Hər keyfiyyət sinfinin öz mirvari qiyməti var, amma müəyyən keyfiyyət sinfində tam bir alış-veriş üçün həmin sinifdəki 10 mirvariyə bərabər əlavə məbləğ ödənilməlidir. Bu, turistlərin yalnız bir mirvari almasının qarşısını almaq üçündür.
Həmçinin "The Royal Pearl" qlobal iqtisadiyyatın yavaşlamasından əziyyət çəkir. Buna görə də şirkət daha səmərəli olmalıdır. Maliyyə direktoru (CFO) bəzən lazım olan keyfiyyətdən daha yüksək keyfiyyət sinfində mirvarilər alaraq pul qənaət edə biləcəyini aşkar edib. Müştərilər "The Royal Pearl" şirkətini bilərziklərdə daha yaxşı mirvarilər qoyduğuna görə qınamayacaqlar, qiymətlər eyni qaldığı müddətcə.
Məsələn, 10 Avro kateqoriyasında 5 mirvari və 20 Avro kateqoriyasında 100 mirvari lazımdır. Bu normalda belə başa gələcək: (5+10)*10+(100+10)*20 = 2350 Avro. Bütün 105 mirvarini 20 Avro kateqoriyasında almaq yalnız belə başa gəlir: (5+100+10)*20 = 2300 Avro.
Problem ondadır ki, maliyyə direktoru üçün ən yaxşı şəkildə neçə mirvarinin daha yüksək keyfiyyət sinfində alınacağını hesablamaq çox vaxt aparır. Sizdən "The Royal Pearl" şirkətinə bir kompüter proqramı ilə kömək etməyiniz xahiş olunur.
Fərqli keyfiyyət siniflərində mirvarilərin sayı və hər mirvarinin qiyməti ilə verilmiş siyahı nəzərə alınaraq, siyahıdakı hər şeyi almaq üçün lazım olan ən aşağı mümkün qiyməti verin. Mirvarilər tələb olunan və ya daha yüksək keyfiyyət sinfində alına bilər, amma daha aşağı sinifdə deyil.
Girişin ilk sətri test hallarının sayını ehtiva edir. Hər test halı, c (1 ≤ c ≤ 100) kateqoriyalarının sayını ehtiva edən bir sətr ilə başlayır. Sonra, hər biri iki ədəd a_i və p_i olan c sətir gəlir. Bu ədədlərdən birincisi, bir sinifdə lazım olan mirvarilərin sayıdır (1 ≤ a_i ≤ 1000).
İkinci ədəd isə həmin sinifdəki mirvarinin qiymətidir (1 ≤ p_i ≤ 1000). Siniflərin keyfiyyətləri (və beləliklə qiymətləri) artan sırada verilir. Girişdəki bütün ədədlər tam ədədlərdir.
Hər test halı üçün bir sətir, siyahıdakı hər şeyi almaq üçün lazım olan ən aşağı mümkün qiyməti ehtiva edən bir ədəd.
Nümunə 1