4E. Pyramid.py

"""
Для строительства двумерной пирамиды используются прямоугольные блоки, каждый из
которых характеризуется шириной и высотой.
Можно поставить один блок на другой, только если ширина верхнего блока строго меньше
ширины нижнего (блоки нельзя поворачивать). Самым нижним в пирамиде может быть блок
любой ширины.
По заданному набору блоков определите, пирамиду какой наибольшей высоты можно построить
из них.

Формат ввода
В первой строке входных данных задается число N — количество блоков (1≤N≤100000).
В следующих N строках задаются пары натуральных чисел wi и hi (1≤wi,hi≤109) — ширина
и высота блока соответственно.

Формат вывода
Выведите одно целое число — максимальную высоту пирамиды.

Пример
Ввод
Вывод
3
3 1
2 2
3 3

5

Примечания
В примере пирамида будет состоять из двух блоков: нижним блоком будет блок номер
3, а верхним — блок номер 2. Блок номер 1 нельзя использовать вместе с блоком номер
3.
Скачать условие задачи
"""


def fun(s):
    """
    Faster and less memory usage

    >>> fun([(3, 1), (2, 2), (3, 3)])
    5
    """

    d = {}
    for w, h in s:
        if w not in d:
            d[w] = 0

        if h > d[w]:
            d[w] = h

    return sum(d.values())


def fun2(s):
    """
    >>> fun2([(3, 1), (2, 2), (3, 3)])
    5
    """

    d = {}
    for w, h in s:
        if w not in d:
            d[w] = []

        d[w].append(h)

    ans = 0
    for h in d.values():
        ans += max(h)

    return ans


N = int(input())
s = [tuple(map(int, input().split())) for _ in range(N)]
print(fun(s))

# print(f">>> fun({s})")
# print(f"{fun(s)}")


if __name__ == "__main__":
    import doctest

    doctest.testmod()