Потратить как можно меньше плюгенов для покупки всех n предметов

В вашей любимой игре вышло новое обновление, в котором добавили много всего нового.

Ваши любимые разработчики добавили n предметов, но, так как они тоже люди и им тоже хочется кушать, бесплатно вы эти предметы не получите. Цена i-го предмета равна ci плюгенов. При этом разработчики понимают, что если сделать цены слишком большими (а они так и сделали), то игроки могут разозлиться и пойти играть в какую-нибудь другую игру. Поэтому эти добрые люди добавили m купонов, i-й из которых позволяет уменьшить стоимость ровно одного предмета на di в том случае, если изначальная цена была хотя бы Li плюгенов. Но важно не забывать, что каждый купон может быть использован не более одного раза. Более того, чтобы игроки не забывали, во что они играют, им запрещено применять на один предмет более одного купона.

Вы — простой студент одной известной экономической школы, поэтому перед вами встала очень сложная задача — потратить как можно меньше плюгенов для покупки всех n предметов (потому что по отдельности эти предметы никакого интереса не представляют).

-----------------------------------------------

(сначала вводится число n и число m, затем последовательность с (из n элементов); затем последовательности L и d (из m элементов))

Примеры:

3 3
4 3 1
4 4 2
2 3 1
-> 4

10 5
9 7 1 5 2 2 5 5 7 6
7 2 7 8 2
3 2 4 1 2
-> 37

0

В вашей любимой игре вышло новое обновление, в котором добавили много всего нового.

Ваши любимые разработчики добавили n
предметов, но, так как они тоже люди и им тоже хочется кушать, бесплатно вы эти предметы не получите. Цена i-го предмета равна ci плюгенов. При этом разработчики понимают, что если сделать цены слишком большими (а они так и сделали), то игроки могут разозлиться и пойти играть в какую-нибудь другую игру. Поэтому эти добрые люди добавили m купонов, i-й из которых позволяет уменьшить стоимость ровно одного предмета на di в том случае, если изначальная цена была хотя бы li

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

Вы — простой студент одной известной экономической школы, поэтому перед вами встала очень сложная задача — потратить как можно меньше плюгенов для покупки всех n

предметов (потому что по отдельности эти предметы никакого интереса не представляют).
Формат входных данных

В первой строке даны целые числа n
и m (1≤n,m≤2⋅105

) — количество предметов и купонов.

Во второй строке перечислены числа c1,…,cn
(1≤ci≤109

) — стоимости предметов.

В третьей строке перечислены числа l1,…,lm
(1≤li≤109

) — минимальные цены предметов для использования купонов.

В четвертой строке перечислены числа d1,…,dm
(1≤di≤li

) — скидки после использования купонов.
Формат выходных данных

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

3 3
4 3 1
4 4 2
2 3 1

Выходные данные

4

Входные данные

10 5
9 7 1 5 2 2 5 5 7 6
7 2 7 8 2
3 2 4 1 2

Выходные данные

37

Примечания

Рассмотрим первый пример. Если использовать второй купон (он уменьшает на 3
стоимость предмета, который стоил хотя бы 4 плюгена) для первого предмета и третий купон (он уменьшает на 1 стоимость предмета, который стоил хотя бы 2 плюгена) для второго предмета, то потребуется (4−3)+(3−1)+1=4 плюгена.

0

Напоминает "Задачу о Рюкзаке".

0

В задании i-й индекс для предмета и i-й индекс для купона как-то связаны? или это разные индексы?
Ну т.е.
вариант 1) i-й купон применим только к i-му предмету,
или
вариант 2) любой купон применим к любому предмету?

Если 1), то у нас вообще нет вариантов, необходимая сумма денег это сумма предметов минус сумма купонов (фурмула полностью верна, если купоны не больше стоимости предметов). Но в любом случае вариантов тут не вижу.

А если вариант 2), то алгоритм видится простым:
- сортируем стоимость предметов по убыванию
- сортируем стоимость купонов по убыванию
- последовательно применяем купоны в порядке убывания к стоимости предметов в порядке убывания (т.е. вычитаем из стоимости предметов стоимость купонов в порядке сформированных списков); если купон больше стоимости предмета - стоимость предмета просто обнуляем (не в минус же); так применяем все купоны ко всем предметам, на сколько хватит
- а теперь суммируем получившиеся стоимость всех предметов - это и будет минимально необходимая сумма денег.

0