407798: GYM102894 F Hotel Chevalier

The newly opened Hotel Chevalier is accepting tourists. The hotel boasts $$$n$$$ rooms of various size, the $$$i$$$-th room accommodating $$$c_i$$$ people. $$$k$$$ groups would like to rent a room, the $$$j$$$-th group containing $$$p_j$$$ people and offering $$$m_j$$$ dollars for a room. A room is suitable for some group if and only if its capacity doesn't exceed the number of people in the group. Also, two groups cannot rent the same room.

Unfortunately, it may be possible that the hotel is not large enough to accommodate all groups. Help the hotel manager make the maximum possible revenue for the hotel by optimally assigning rooms to the groups.

The first line contains two integers $$$n$$$, $$$k$$$ $$$(1 \le n, k \le 150000)$$$ — the number of rooms in the hotel and the number of tourist groups.

The second line contains $$$n$$$ integers $$$c_i$$$ $$$(1 \le c_i \le 100000)$$$ — the room capacities.

The third line contains $$$k$$$ integers $$$p_i$$$ $$$(1 \le p_i \le 100000)$$$ — the number of tourists in each group.

The fourth line contains $$$k$$$ integers $$$m_i$$$ $$$(1 \le m_i \le 100000)$$$ — the amount of money the groups are willing to pay for a room.

Output a single number — the maximum possible amount of money the hotel can make after renting rooms to the tourist groups.

2 4
3 5
2 4 5 6
9 10 8 22

19