Отсортируем все блюда по неубыванию обычной цены (**B**). Предподсчитаем 3 массива:

• sum[i] = сумма первых i обычных цен
• maxD[i] = максимальная разность обычной цены и особой (**B-A**) среди первых i блюд
• minA[i] = минимальная особая цена (**A**) среди последних блюд, начиная с i-того

Рассмотрим 2 случая:

1. Первое блюдо будет среди первых k — тогда суммой будет sum[k] - maxD[k]
2. Иначе — sum[k-1] + minA[k]

Выберем минимум из этих вариантов — это и будет ответом для текущего k.

The trick is to find a way to reduce number of times you have to rebuild the hull.

Сделаем паросочетания цифра — место. Каждое наблюдение делает 2 вещи. Если мы знает что на одном отрезке минимальное число Х, то во-первых, на этом отрезке числа могут быть только от X до N-1, а во-вторых число X может быть только на этом отрезке. Получаем матрицу из 1 и 0. Дальше можно делать всё, что угодно — макс. паросочетания, Венгерка и.т.п.

Матрицу можно получить следующим образом: будем считать "во-первых" и "во-вторых" отдельно. "Во-первых": сначала пробежимся по наблюдениям, и посчитаем, какие числа могут на этим месте быть. Заметим, что это отрезок. Соответственно, обновлять можем за O(M*N) — для каждого наблюдения пробежаться по каждому месту. Потом обновим матрицу "во-вторых": для каждого наблюдения возьмём "пограничное" число и обнулим его вне допустимого отрезка. O(M*N). Итого, получили матрицу.