Задача . E. Орехус и прямоугольники

Орехус застрял в плоском мире. Чтобы выбраться, необходимо решить следующую задачу.

Вам даны \(n\) прямоугольников с вершинами в точках \((0, 0)\), \((x_i, 0)\), \((x_i, y_i)\), \((0, y_i)\). Также для каждого прямоугольника вам дано число \(a_i\). Необходимо выбрать некоторые из них, чтобы площадь их объединения минус сумма их \(a_i\) была максимальна.

Гарантируется, что нет вложенных прямоугольников.

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