Cangüdənlər
Heç vaxt on Avropa kral ailəsinin üzvləri, Argentina futbol komandasının məşqçisi Dieqo Maradona da daxil olmaqla, və ya bütün Turing və Fields medal mükafatçıları ilə tanış olmusunuzmu? Biz CEOI 2010 bağlanış mərasiminə dünyanın hər yerindən bir çox məşhuru dəvət etmişik. Təəssüf ki, onların çox azı dəvətimizi cavablandırdı və cavab verənlər də nəzakətlə rədd etdilər. Buna baxmayaraq, mərasimə kameranızı gətirməyi unutmayın, kimlərin gələcəyini heç vaxt bilmək olmaz!
Təsəvvür edə biləcəyiniz kimi, qonaqların təhlükəsizliyi ən yüksək əhəmiyyətə malikdir. Problem onların mühafizəçilərini auditoriyada elə oturtmaqdır ki, maksimal təhlükəsizlik təmin olunsun.
Auditoriyada çoxlu oturacaqlar var, böyük bir şəbəkə şəklində düzülüb. Təhlükəsizlik qaydalarına əsasən, bir təhlükəsizlik mütəxəssisi auditoriyanın hər bir sıra və sütunu üçün lazım olan mühafizəçi sayını müəyyən edib.
Sizə auditoriyanın hər bir sıra və sütunu üçün tələb olunan mühafizəçi sayı verilir. Bu məlumat aşağıda izah edildiyi kimi sıxılmış formada verilir. Hər bir sıra və hər bir sütunda dəqiq tələb olunan mühafizəçi sayını təmin edəcək şəkildə mühafizəçiləri yerləşdirmək mümkün olub-olmadığını müəyyən edin.
Fərz edin ki, auditoriya əvvəlcə boşdur, yəni mühafizəçiləri istədiyiniz yerə oturda bilərsiniz. Hər bir oturacaq yalnız bir mühafizəçi tərəfindən tutula bilər.
Giriş verilənləri
Giriş sıraların təsviri ilə başlayır. Girişin ilk sətri bir müsbət tam ədəd R: sıra qruplarının sayını ehtiva edir. R sətr izləyir. Bu sətirlərin hər biri 2 müsbət tam ədəd ehtiva edir: qrupun hər bir sırasında tələb olunan mühafizəçi sayı və qrupu təşkil edən sətirlərin sayı.
Bundan sonra sütun qruplarının təsviri gəlir. Növbəti sətir bir müsbət tam ədəd C: sütun qruplarının sayını ehtiva edir. C sətr izləyir. Bu sətirlərin hər biri 2 müsbət tam ədəd ehtiva edir: qrupun hər bir sütununda tələb olunan mühafizəçi sayı və qrupu təşkil edən sütunların sayı.
Məhdudiyyətlər
Sıra məhdudiyyətləri ilə tələb olunan ümumi mühafizəçi sayının sütun məhdudiyyətləri ilə tələb olunan ümumi mühafizəçi sayına bərabər olduğunu fərz edə bilərsiniz. Bu ümumi mühafizəçi sayının ən çox 10^18 olduğunu fərz edə bilərsiniz.
Bütün ədədlərin 1000000000-dan çox olmayan müsbət tam ədədlər olduğunu fərz edə bilərsiniz.
1 ≤ R, C ≤ 200000 olduğunu fərz edə bilərsiniz.
50 xal dəyərində olan bir neçə test dəsti aşağıdakı meyarlara cavab verir:
auditoriyadakı ümumi sıra sayı ən çox 2000 olacaq
auditoriyadakı ümumi sütun sayı ən çox 2000 olacaq
ümumi mühafizəçi sayı ən çox 1000000 olacaq.
Başqa 10 xal dəyərində olan bir test dəstində hər bir test halında R, C ≤ 100 var.
Çıxış verilənləri
Məhdudiyyətlərin yerinə yetirilə biləcəyi halda "1", əks halda "0" (aydınlıq üçün dırnaq işarələri ilə) olan bir sətir çıxarın.