Всем привет! Прорешиваю сейчас задачи со старых заключительных этапов всероса и наткнулся на любопытную задачу с РОИ-2006. Любопытна она тем, что на РОИ для получения 100 баллов было достаточно решения за O(N^2), а на информатиксе N<=10^5. Квадратичное решение в виде сортировки+дп придумал, но быстрее не получается. Подскажите кто что может)

Условие: https://informatics.mccme.ru/mod/statements/view3.php?id=37899&chapterid=113190