Плейлісти#518

Плейлісти

... Можливо, незабаром тут з'явиться якась крута легенда ...

У вас є плейлістів. Кожен плейліст — це список пісень. Кожна пісня має свій рейтинг. Іншими словами, плейлист 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.

Вихідні дані

У першому рядку виведіть єдине ціле число — довжину найдовшого «чудового» префікса.

У другому рядку виведіть цілих чисел — порядок плейлістів, який досягає такого результату.

Якщо є кілька можливих порядків, виведіть будь-який.

Приклади

Приклад 1

Loading
Loading

Приклад 2

Loading
Loading

Примітка

У першому прикладі, з порядком (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.

Чудовий префікс має довжину 

Оцінювання

  1. ( балів) n \le 3;

  2. ( балів) n \le 8;

  3. ( балів) k_i = 1;

  4. ( балів) s_{i,j} < 32;

  5. ( балів) без додаткових обмежень.