Heapq на Python: минимальная стоимость объединения элементов

Плавильный горн

В алхимическом горне плавят зачарованные кристаллы разной массы, чтобы соединить их в единый монолит. Устройство работает строго по заведённому правилу: на каждом шаге оно выбирает из общей массы два самых лёгких самородка и сплавляет их в один слиток с суммарным весом. Если кристаллов наименьшей массы оказывается несколько, горн может взять любую подходящую пару.

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

Слияния повторяются снова и снова, пока в горне не останется единственный крупный кристалл. Алхимику требуется рассчитать, какая общая стоимость подпитки уйдет на выполнение всех шагов плавки.

Что уже дано

Заготовка скрипта считывает входные данные из стандартного потока ввода, передаёт список масс в функцию total_fusion_cost и выводит результат.

Что нужно сделать

Реализуйте функцию total_fusion_cost(masses: list[int]) -> int.

Функция принимает список целых чисел masses, задающий начальные массы кристаллов в произвольном порядке (массы могут повторяться).

Правила вычисления:

• На каждом шаге из текущего набора берутся два элемента с наименьшими значениями. Если элементов с минимальным весом несколько, допустим любой выбор среди них.
• Выбранные элементы объединяются в один новый элемент с массой, равной их сумме. Стоимость этой отдельной операции равна массе полученного слитка.
• Новый слиток возвращается в общий набор и может быть выбран на любом из последующих шагов.
• Процесс продолжается до тех пор, пока в наборе не останется ровно один элемент.
• Функция должна вернуть суммарную стоимость всех выполненных слияний.
• Если изначально дан только один кристалл, слияния не требуются, и функция должна вернуть 0.

Решение должно укладываться во временную сложность $O(n\log n)$, так как повторный полный перебор списка на каждом шаге не успеет завершиться за отведённое время.

Ввод и вывод

Программа взаимодействует с проверяющей системой через стандартные потоки stdin и stdout.

Формат ввода

• В первой строке передаётся целое число $g$ ($1\le g\le 2000$) — количество групп кристаллов.
• В следующих $g$ строках записаны по два натуральных числа: масса кристалла $\text{mass}$ ($1\le \text{mass}\le 10^9$) и количество таких кристаллов $\text{count}$ ($1\le \text{count}\le 300,000$). Суммарное количество всех кристаллов $n=\sum \text{count}$ не превышает $300,000$.

Готовая заготовка автоматически считывает эти группы и разворачивает их в единый список masses из $n$ чисел, после чего передаёт его в вашу функцию.

Формат вывода

Одна строка с единственным неотрицательным целым числом — суммарной стоимостью всех слияний.