... Yəqin ki, burada hər an bəzi maraqlı əfsanə görünə bilər ...
Sizin ədəd playlistiniz var. Hər bir playlist mahnıların siyahısıdır. Hər bir mahnının öz reytinqi var. Başqa sözlə, playlist s_i mahnıların siyahısıdır \left[ s_{i,1}, s_{i,2}, \dots, s_{i,k_i} \right], burada k_i siyahının uzunluğudur.
Siz playlistləri müəyyən bir sırada dinləmək istəyirsiniz. Tutaq ki, siz playlistləri s_1, s_2, \dots, s_n sırasına görə dinləyirsiniz. Onda mahnılar aşağıdakı siyahı olacaq \left[ s_{1,1}, s_{1,2}, \dots, s_{1, k_1}, s_{2, 1}, s_{2,2}, \dots, s_{n, k_n} \right].
Gəlin deyək ki, mahnılar siyahısı \left[ a_1, a_2, \dots, a_k \right] yalnız o zaman "böyük"dir ki, a_i > \sum_{j < i} a_j bütün 1 \le i \le k üçün, yəni, hər bir mahnının reytinqi əvvəlki bütün mahnıların cəmdən daha böyükdür.
Zəhmət olmasa, bütün playlistlərin sıralamaları arasında ən uzun "böyük" prefiksi tapın.
İlk sətir tək bir tam ədəd (1 \le n \le 10^3) — playlistlərin sayı.
Sonrakı sətir playlistləri müəyyən edir.
-ci sətir tək bir tam ədəd k_i (1 \le k_i \le 10^6) — playlist -dəki mahnıların sayı.
(2i + 1)-ci sətir k_i tam ədədini s_{i, 1}, s_{i, 2}, \dots, s_{i, k_i} (0 \le s_{i, j} \le 10^9, s_{i,j} = 2^t bəzi üçün) — playlistdəki mahnıların reytinqlərini ehtiva edir.
Zəmanət verilir ki, \sum_{i=1}^{n} k_i \le 10^6.
İlk sətirdə, ən uzun "böyük" prefiksin uzunluğunu tək bir tam ədəd olaraq çap edin.
İkinci sətirdə, belə bir nəticəni əldə edən tam ədədini çap edin — playlistlərin sırası.
Əgər bir neçə mümkün sıralama varsa, istənilənini çap edin.
Example 1
Example 2
İlk nümunədə, (1, 2, 3) sırası ilə mahnılar [1, 4, 8, 32]-dir:
1 > 0,,
4 > 1,,
8 > 1 + 4 = 5,,
32 > 1 + 4 + 8 = 13,.
Dörd mahnı da şərti ödəyir, beləliklə, böyük prefiksin uzunluğu -dür. Üç playlistin başqa heç bir sıralaması daha uzun böyük prefiks əldə etmir.
İkinci nümunədə, (2, 1, 4, 3) sırası ilə mahnılar [1, 2, 4, 8, 128, 256, 2]-dir:
1 > 0,
2 > 1,
4 > 1 + 2 = 3,
8 > 1 + 2 + 4 = 7,
128 > 1 + 2 + 4 + 8 = 15,
256 > 1 + 2 + 4 + 8 + 128 = 143,
2 \not> 1 + 2 + 4 + 8 + 128 + 256 = 399.
Böyük prefiksin uzunluğu -dır
( bal) n \le 3;
( bal) n \le 8;
( bal) k_i = 1;
( bal) s_{i,j} < 32;
( bal) əlavə məhdudiyyət yoxdur.