Задача №115253. Музыкальный фестиваль
Мальчик Витя очень любит слушать музыку. Он пристально следит за обновлениями своих любимых групп, поэтому знает, что в эту пятницу должны быть выпущены \(n\) альбомов, \(i\)-й из которых содержит \(k_i\) треков. Разумеется, Витя, как самый преданный фанат, уже послушал все треки, которые должны выйти в ближайшее время, и знает, что в \(i\)-м альбоме крутость \(j\)-го трека равна \(a_{i,j}\).
У Вити есть подруга Маша, которую он очень хочет пригласить на фестиваль, где выступают его любимые группы. Однако для того, чтобы подруга согласилась, она должна сначала оценить вышедшие новинки. Витя знает, что, если Маша послушает трек, который был круче всех прошлых, она получит 1 единицу впечатления. К сожалению, альбомы можно слушать только целиком, не меняя песни в них местами.
Помогите Вите найти такой порядок альбомов, чтобы впечатление Маши оказалось как можно больше, и она точно сходила вместе с ним на фестиваль.
В первой строке дано единственное целое число \(n\) (\(1 \le n \le 200\,000\)) — количество альбомов.
Далее следуют описания альбомов. Каждое описание альбома состоит из двух строк:
В первой строке дано единственное целое число \(k_i\) (\(1 \le k_i \le 200\,000\)) — количество треков в \(i\)-м альбоме.
В следующей строке даны \(k_i\) целых чисел \(a_{i, 1},\ a_{i, 2},\ a_{i, 3},\ \ldots,\ a_{i, k_i}\) (\(1 \le a_{i,j} \le 200\,000\)) — крутость треков в \(i\)-м альбоме.
Обозначим за \(\sum k_i\) сумму по всем \(k_i\). Гарантируется, что \(\sum k_i \le 200\,000\).
Выведите единственное число — максимальное впечатление, которое может может получить Маша.
В первом тестовом примере оптимальным порядком является прослушивание 4-го, 2-го, 3-го и 1-го альбомов. В таком случае Маша послушает треки в следующем порядке: 1 ; 7 ; 8 , 6; 4, 9 , 4, 6, 8 и получит 4 единицы впечатления.
Во втором тестовом примере необходимо сначала прослушать 1-й, потом 4-й и в любом порядке 2-й и 3-й. В таком случае Маша получит максимальное впечатление, причём за каждую песню в 1-м и 4-м альбомах и ничего за 2-й и 3-й.
Тесты к этой задаче состоят из 7 групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов некоторых из предыдущих групп. Обратите внимание, прохождение тестов из условия не требуется для некоторых групп.
| Доп. ограничения | ||||||
| Группа | Баллы | \(n\) | \(k_i\) | \(a_{i, j}\) | Необх. группы | Комментарий |
| 0 | 0 | – | – | – | – | Тесты из условия. |
| 1 | 14 | \(n \le 7\) | \(\sum k_i \le 1000\) | – | 0 | |
| 2 | 9 | – | – | \(a_{i, j} \le 2\) | – | |
| 3 | 12 | – | – | \(a_{i, j} \le 10\) | 0, 2 | |
| 4 | 15 | – | \(k_i \le 2\) | – | – | |
| 5 | 13 | \(n \le 1000\) | – | \(a_{i, j} \le 1000\) | 0 | |
| 6 | 13 | \(n \le 30\,000\) | – | \(a_{i, j} \le 30\,000\) | 0, 5 | |
| 7 | 24 | – | – | – | 0 – 6 | |
4 5 4 9 4 6 8 1 7 2 8 6 1 1
4
4 2 3 4 2 1 8 2 2 8 2 7 9
4