Agent
Агент Ceyms Bond təqaüdə çıxmışdı, lakin sakit xarakteri yeni təəssüratlar tələb edirdi. Buna görə də Ceyms Bond məmnuniyyətlə "Gənc agent" məktəbinin bəzi qruplarında ustad dərsi keçməyə razılaşdı. Dərslərdən birinin mövzusu - agentin tərəfdaşla işi idi. Kəşfiyyat kimi təhlükəli bir işdə çox etibarlı bir tərəfdaşın olması vacibdir, buna görə də tərəfdaşlar yalnız yaş baxımından maksimum yaxın olan agentlər ola bilər (yəni, əgər qrupda biri digərindən yaşca böyük, digəri isə kiçik olan üçüncü bir agent varsa, iki agent tərəfdaş ola bilməz).
Bondun vəzifəsi agentlərin bir-birinə elə tərəfdaş tapmasıdır ki, hər bir agentin ən azı bir tərəfdaşı olsun (agentin ümumilikdə 2 tərəfdaşı ola bilər - biri ondan kiçik, biri isə böyük, lakin bu ikisi bir-birinə tərəfdaş hesab olunmur). Aydındır ki, 4 və daha çox agentdən ibarət qrup bir neçə şəkildə bölünə bilər.
Bir neçə dərsdən sonra Bond "Gənc agent" məktəbində təhsil alan qrupların bacarıqlarını öyrəndi və hər bir agentin ifşa olunma riskini qiymətləndirdi. Lakin tərəfdaşla işin spesifikası belədir ki, cütlükdə yalnız iki agentdən yaşca böyük olan risk altındadır, buna görə də qrupu elə bölmək lazımdır ki, ümumi risk minimal olsun.
Giriş verilənləri
Giriş faylının birinci sətirində Ceyms Bondun ustad dərsi keçdiyi qrupların sayı olan bir tam ədəd M (1 <= M <= 13) verilir. Sonra ardıcıl olaraq M qrupun təsviri verilir. Hər bir qrupun təsviri iki sətirdən ibarətdir. Birinci sətirdə qrupdakı agentlərin sayı olan bir tam ədəd N verilir (2 <= N <= 10000). İkinci sətirdə boşluqla ayrılmış N cüt müsbət tam ədəd verilir. Cütdə birinci ədəd agentin yaşıdır (günlərlə) və [5000, 16000] diapazonundadır, ikinci ədəd isə agentin ifşa olunma riskidir, [1, 1000] diapazonunda olan bir ədəddir. Məlumdur ki, istənilən qrupda bütün agentlər müxtəlif yaşdadır.
Çıxış verilənləri
Hər bir qrup üçün ayrıca sətirdə qrupun ifşa olunma riskinin minimal dəyərini verin.
Misal üçün şərhlər: birinci qrupda tərəfdaş seçmək lazım deyil - bölünmə variantı yalnız bir dənədir: cüt 6000-5500 (risk 2) və cüt 5500-5000 (risk 3).
İkinci qrupda 5005 və 5001 agentləri yaş baxımından kənar olduqları üçün tərəfdaş olaraq müvafiq olaraq 5004 və 5002 alırlar. Amma tərəfdaşsız qalan 5003 agenti 5004 və ya 5002 seçə bilər. 5004 ilə cütdə risk daha azdır (2 əvəzinə 3), buna görə də optimal bölünmə ümumi risk 1 + 2 + 4 = 7 olur.