Quelling Blade
Cənab Sheep kompüter oyununda özünü itirib. Bu oyunda o, super qəhrəman rolunu oynayır və şər qüvvələrlə mübarizə aparır. Oyun avadanlığı çox vacibdir və Cənab Sheep Quelling Blade-in ən güclü silah olduğunu düşünür.
Oyun zamanı hər bir silah qəhrəmana müəyyən bir məbləğə başa gəlir və ona fayda gətirir. Əgər qəhrəman iki silah alarsa (onların eyni növ olub-olmamasından asılı olmayaraq), fayda dəyərləri toplanır. Məsələn, qəhrəman fayda dəyərləri 3 və 5 olan iki silah alarsa, ümumi fayda dəyəri 8=3+5 olacaq.
Hər bir silah üçün müəyyən tələblər var. Əgər qəhrəman müəyyən bir silah almaq istəyirsə, əvvəlcə bəzi digər silahlara ehtiyacı ola bilər. Məsələn, qəhrəman "Divine Rapier" almaq istəyirsə, "Demon Edge" və "Scared Relic"ə ehtiyacı var. Əlbəttə ki, ikinci "Divine Rapier" almaq üçün başqa bir "Demon Edge" və başqa bir "Scared Relic" almalıdır. Qeyd edək ki, mövcud silah ticarətdən sonra yox olmayacaq. Həmçinin, bir silah eyni növdən bir neçə silaha ehtiyac duya bilər. Bir silah növü ən çox bir başqa silah növü tərəfindən tələb olunur.
Qəhrəman döyüşlə məşğuldur və pul qazanmağa vaxtı yoxdur. Xoşbəxtlikdən, oyun qəhrəmana hər saniyə 1 sikkə verir. Beləliklə, əgər qəhrəman "Quelling Blade" almaq istəyirsə, məqsədinə çatması üçün minimum ümumi vaxt asanlıqla hesablana bilər.
Cənab Sheep mükəmməllik axtarışındadır. O, yalnız "Quelling Blade"i mümkün qədər tez əldə etmək istəmir, həm də oyunun hər saniyəsini optimallaşdırmaq istəyir. O, oyunun faydalılığını qəhrəmanın hər saniyədəki fayda dəyərinin cəmi kimi müəyyən edir. O, faydalılığı oyunun başlanğıcından "Quelling Blade"i əldə etdiyi saniyəyə qədər, eksklüziv olaraq hesablayır. Daha ətraflı izahat üçün nümunələrə müraciət edə bilərsiniz. Başqa sözlə, qəhrəman üçün silahları almaq üçün bir proses təyin etməlisiniz ki, bu da "Quelling Blade"i əldə etmək üçün ümumi vaxtı minimuma endirir və oyunun faydalılığını optimallaşdırır.
Giriş verilənləri
Yüzlərlə test halı var, test hallarının sayı girişin ilk sətrindədir. Qeyd edək ki, test hallarının əksəriyyəti nisbətən kiçikdir.
Hər bir test halı üçün, ilk sətir fərqli silah növlərinin sayını göstərən tək bir tam ədəd N ehtiva edir. (1 ≤ N ≤ 1000)
Növbəti sətirlər silahları təsvir edir. Hər bir silah üçün, ilk sətir bu cür silahın fayda dəyərini və dəyərini göstərən iki tam ədəd B və C ehtiva edir. (1 ≤ B, C ≤ 2^31-1) Sonra növbəti sətirdə bu silahın tələblərinin sayını təsvir edən tək bir tam ədəd P var. Növbəti P sətirlərdə, hər sətir I indeksli A silahlarına ehtiyac olduğunu bildirən iki tam ədəd I və A ehtiva edir.
Silahların indeksləri 1-dən N-ə qədər başlayır. "Quelling Blade" birinci növ silahdır. Və siz güman edə bilərsiniz ki, "Quelling Blade" tərəfindən tələb olunan silahların ümumi sayı 1000000-dən azdır. Həmçinin qeyd edək ki, "Quelling Blade" məhdud oyun vaxtında əldə edilə bilər və bir silah növü ən çox bir başqa silah növü tərəfindən tələb oluna bilər.
Çıxış verilənləri
Hər bir test halı üçün optimal faydalılığı göstərən tək bir tam ədəd çıxarın. Cavabın 64-bitlik imzalı tam ədədə uyğun olduğunu güman edə bilərsiniz.