... Հնարավոր է, որ այստեղ շուտով հայտնվի ինչ-որ հետաքրքիր լեգենդ ...
Դուք ունեք նվագացանկ: Յուրաքանչյուր նվագացանկը երգերի ցանկ է: Յուրաքանչյուր երգ ունի իր գնահատականը: Այլ խոսքով, նվագացանկ s_i-ն երգերի ցանկ է \left[ s_{i,1}, s_{i,2}, \dots, s_{i,k_i} \right], որտեղ k_i ցանկի երկարությունն է:
Դուք ցանկանում եք լսել նվագացանկերը որոշակի հերթով: Ենթադրենք դուք լսում եք նվագացանկերը հետևյալ հերթականությամբ․ s_1, s_2, \dots, s_n. Այդ դեպքում երգերի ցանկը կլինի այսպիսին․ \left[ s_{1,1}, s_{1,2}, \dots, s_{1, k_1}, s_{2, 1}, s_{2,2}, \dots, s_{n, k_n} \right]:
Երգերի \left[ a_1, a_2, \dots, a_k \right] ցանկը կոչվում է "հիանալի", եթե և միայն եթե a_i > \sum_{j < i} a_j բոլոր 1 \le i \le k համար, այսինքն՝ յուրաքանչյուր երգի գնահատականը ավելի մեծ է, քան բոլոր նախորդ երգերի գնահատականների գումարը:
Խնդրում ենք գտնել "հիանալի" ամենաերկար նախածանցը բոլոր նվագացանկերի հերթականությունների մեջ:
Առաջին տողը պարունակում է մեկ ամբողջ թիվ (1 \le n \le 10^3) — նվագացանկերի քանակը:
Հաջորդ տողերը սահմանում են նվագացանկերը:
-րդ տողը պարունակում է մեկ ամբողջ թիվ k_i (1 \le k_i \le 10^6) — նվագացանկ -ի մեջ երգերի քանակը:
(2i + 1)-րդ տողը պարունակում է k_i ամբողջ թվեր s_{i, 1}, s_{i, 2}, \dots, s_{i, k_i} (0 \le s_{i, j} \le 10^9, s_{i,j} = 2^t որոշ համար) — նվագացանկի երգերի գնահատականները:
Երաշխավորվում է, որ \sum_{i=1}^{n} k_i \le 10^6:
Առաջին տողում տպեք մեկ ամբողջ թիվ — "հիանալի" ամենաերկար նախածանցի երկարությունը:
Երկրորդ տողում տպեք ամբողջ թիվ — նվագացանկերի հերթականությունը, որը հասնում է նման արդյունքի:
Եթե կան մի քանի հնարավոր հերթականություններ, տպեք ցանկացածը:
Example 1
Example 2
Առաջին օրինակում, (1, 2, 3) երգերի հերթականություն այսպիսին է․ [1, 4, 8, 32]:
1 > 0,,
4 > 1,,
8 > 1 + 4 = 5,,
32 > 1 + 4 + 8 = 13,.
Բոլոր չորս երգերը բավարարում են պայմանը, այնպես որ հիանալի նախածանցի երկարությունը է: Երեք նվագացանկերի որևէ այլ հերթականություն չի հասնում ավելի երկար հիանալի նախածանցի:
Երկրորդ օրինակում, նվագացանկերի (2, 1, 4, 3) հերթականության դեպքում երգերը կլինեն [1, 2, 4, 8, 128, 256, 2]:
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.
Հիանալի նախածանցի երկարությունը է
( միավոր) n \le 3;
( միավոր) n \le 8;
( միավոր) k_i = 1;
( միավոր) s_{i,j} < 32;
( միավոր) լրացուցիչ սահմանափակումներ չկան: