Задача №114082. Облачные вычисления
Джонни основывает Bytecomp — компанию, которая предлагает вычислительные мощности в облаке. Компании этого профиля обычно обладают большим количеством быстрых компьютеров, на которых производятся вычислениях их клиентов.
Джонни ещё не купил ни одного компьютера. Он пошёл в компьютерный магазин и получил список из \(n\) доступных компьютеров. Каждый компьютер характеризуется колиеством процессорных ядер \(c_i\), частотой \(f_i\) и ценой \(v_i\). Такой компьютер имеет \(c_i\) независимых ядер, не мешающих друг другу, поэтому они могут быть назначены для выполнения разных задач.
Когда клиент делает заказ на ресурс, он определяет требуемое количество ядер \(C_j\) и минимальную необходимую частоту \(F_j\). Также заказ содержит цену \(V_j\), которую клиент собирается заплатить. Если заказ принимается, Bytecomp должна предоставить эксклюзивный доступ к вычислительным мощностям, требуемым клиентом. Джонни должен выбрать \(C_j\) ядер (возможно, из разных компьютеров), каждое частотой хотя бы \(F_j\). Эти ядра не могут быть назначены какому-нибудь другому заказу.
Помогите Джонни заработать так много денег, как это возможно: выберите оптимальное подмножество заказов для исполнения, а также подмножество компьютеров из магазина, чтобы удовлетворить все принятые заказы. Ваша цель — максимизировать итоговую прибыль, то есть разность между доходом от предоставления вычислительных ресурсов клиентам и стоимостью покупки компьютеров.
Первая строка содержит целое число \(n\) (\(1 \leq n \leq 2000\)) — количество компьютеров, доступных в магазине.
Каждая из следующих \(n\) строк содержит описание одного компьютера. Она содержит три целых числа \(c_i\), \(f_i\) и \(v_i\) (\(1 \leq c_i \leq 50\), \(1 \leq f_i \leq 10^9\), \(1 \leq v_i \leq 10 ^ 9\)) — количество ядер, частота и цена, соответственно.
Следующая строка содержит целое число \(m\) (\(1 \leq m \leq 2000\)) — количество заказов.
Каждая из следующих \(m\) строк содержит описание одного заказа. Она содержит три целых числа \(C_j\), \(F_j\) и \(V_j\) (\(1 \leq C_j \leq 50\), \(1 \leq F_j \leq 10^9\), \(1 \leq V_j \leq 10^9\)) — количество запрашиваемых ядер, минимальная разрешённая частота и бюджет клиента, соответственно.
Выведите единственное целое число — максимально возможную итоговую прибыль.
Пояснение к примеру из условия: есть четыре доступных типа компьютера и три заказа. Оптимально купить четырехъядерные компьютеры стоимостью \(700\) и \(750\) (\(1450\) в сумме) и затем принять первые два заказа, получив \(300 + 1500 = 1800\). Тогда у нас есть четыре ядра с частотой \(2000\) и четыре ядра с частотой \(2200\). Мы можем назначить любые шесть из них второму клиенту (требуемая частота \(1900\)) и одно — второму клиенту (требуемая частота \(1500\)). Одно ядро не будет использоваться, что разрешено.
Итоговая прибыль равна \(1800 - 1450 = 350\).
4 4 2200 700 2 1800 10 20 2550 9999 4 2000 750 3 1 1500 300 6 1900 1500 3 2400 4550
350