#Условие задачи
#Мы в Авито любим проводить соревнования, — недавно мы устроили чемпионат по шагам. И вот настало время подводить итоги!

#Необходимо определить userIds участников, которые прошли наибольшее количество шагов steps за все дни, не пропустив ни одного дня #соревнований.

#Пример
#Ввод
statistics = [
    [{ 'userId': 1, 'steps': 1000 }, { 'userId': 2, 'steps': 1500 }],
    [{ 'userId': 2, 'steps': 1000 }],
]
#Вывод
champions = { 'userIds': [2], 'steps': 2500 }


#Ввод
statistics = [
    [{ 'userId': 1, 'steps': 2000 }, { 'userId': 2, 'steps': 1500 }],
    [{ 'userId': 2, 'steps': 4000 }, { 'userId': 1, 'steps': 3500 }],
]
#Вывод
champions = { 'userIds': [1, 2], 'steps': 5500 }

#Ввод
statistics = []
#Вывод
champions = { 'userIds': [], 'steps': 0 }

#Главная идея — как только понимаем, что пользователь пропустил день, мы тут же перестаём его «тащить» дальше в памяти. Это поможет #особенно в случаях, когда много пользователей пропускает соревнования, и лишь немногие доходят «до конца».

#Как работает
#На первом дне собираем всех участников в множество valid_users и сразу же запоминаем их шаги.

#На каждом следующем дне:

#Собираем всех участников этого дня во временный словарь day_map вида {userId: steps_за_день}.
#Делаем пересечение valid_users с day_map.keys(). Те, кого нет в текущем дне, сразу «отваливаются» из дальнейшего рассмотрения (они уже #не могут быть чемпионами, раз пропустили).
#Для оставшихся «валидных» пользователей прибавляем их шаги в общий счётчик.
#В конце у нас останутся только те, кто не пропустил ни единого дня. Суммарные шаги для них уже посчитаны.

#За счёт «проредивания» множества valid_users мы избавляемся и от лишних записей в total_steps.

#Временная сложность
#Проход по всем дневным записям (в сумме m штук) даёт O(m).
#Дополнительно на каждом дне делается пересечение valid_users &= day_map.keys().
#Если в среднем множества небольшие или сильно «режутся» на каждом шаге, это может быть довольно быстро.
#В худшем случае пересечение двух множеств размером u занимает
#O(u), но суммарно всё равно остаётся в рамках
#O(m) с некоторой константой на операции с множествами.

def find_champions_optimized(statistics):
    n = len(statistics)
    if n == 0:
        return {"userIds": [], "steps": 0}

    # Берём все userId из первого дня как "пока ещё валидные"
    first_day = statistics[0]
    valid_users = set(record["userId"] for record in first_day)

    # Словарь для суммарных шагов только по тем, кто ещё валиден
    total_steps = {}
    for record in first_day:
        total_steps[record["userId"]] = total_steps.get(record["userId"], 0) + record["steps"]

    # Последовательно обрабатываем оставшиеся дни
    for day in statistics[1:]:
        # Словарь шагов для пользователей конкретного дня
        day_map = {}
        for record in day:
            uid = record["userId"]
            day_map[uid] = day_map.get(uid, 0) + record["steps"]

        # «Узкий проход»: пересекаем множество "валидных" с участниками текущего дня
        valid_users &= day_map.keys()

        # Чтобы не хранить в total_steps "мертвые" userId, удаляем их
        # (тех, кто вылетел, больше не понадобится считать)
        for user in list(total_steps.keys()):
            if user not in valid_users:
                del total_steps[user]

        # Для оставшихся прибавляем шаги
        for user in valid_users:
            total_steps[user] = total_steps.get(user, 0) + day_map[user]

    # Если в итоге никто не остался, значит все кто-то пропустил
    if not valid_users:
        return {"userIds": [], "steps": 0}

    # Ищем максимум шагов среди уцелевших
    max_steps = max(total_steps[user] for user in valid_users)
    # Собираем всех, у кого шаги = максимум
    champions = [user for user in valid_users if total_steps[user] == max_steps]

    return {"userIds": champions, "steps": max_steps}