F. Гранд-отель "Шевалье"
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод
"On a dark desert highway Cool wind in my hair..."
Eagles

Недавно открывшийся отель "Шевалье" принимает туристов. В отеле находится $$$n$$$ номеров различной вместительности, $$$i$$$-й номер имеет вместительность $$$c_i$$$. Снять номер желает $$$k$$$ компаний, $$$j$$$-ая компания состоит из $$$p_j$$$ человек и готова заплатить за номер $$$m_j$$$ долларов. Компания может поместиться в номер, если ее размер не больше, чем вместительность номера. Кроме того, в одном номере может проживать не более одной компании.

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

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

На первой строке подается два целых числа $$$n$$$, $$$k$$$ $$$(1 \le n, k \le 150000)$$$ — количество номеров в отеле и количество компаний потенциальных гостей.

На второй строке подается $$$n$$$ целых чисел $$$c_i$$$ $$$(1 \le c_i \le 100000)$$$ — вместительность комнат.

На третьей строке подается $$$k$$$ целых чисел $$$p_i$$$ $$$(1 \le p_i \le 100000)$$$ — количество туристов в каждой компании.

На четвертой строке подается $$$k$$$ целых чисел $$$m_i$$$ $$$(1 \le m_i \le 100000)$$$ — количество денег, которое готовы заплатить компании туристов за размещение.

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

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

Система оценки

№БаллыОграниченияНеобх. подзадачиРезультаты
120$$$n \le 10, k \le 10$$$-подзадача
214$$$c_i \le 2$$$-подзадача
319$$$m_i = 1$$$-подзадача
446$$$n \le 1000, k \le 1000$$$-подзадача
51$$$n \le 150000, k \le 150000$$$1, 2, 3, 4подзадача

Пример
Входные данные
2 4
3 5
2 4 5 6
9 10 8 22
Выходные данные
19