407798: GYM102894 F Hotel Chevalier

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

F. Hotel Chevaliertime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output"On a dark desert highway Cool wind in my hair..."Eagles

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.

Input

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

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

Scoring

PointsLimitsDependenciesGrading policy
120$$$n \le 10, k \le 10$$$-complete
214$$$c_i \le 2$$$-complete
319$$$m_i = 1$$$-complete
446$$$n \le 1000, k \le 1000$$$-complete
51$$$n \le 150000, k \le 150000$$$1, 2, 3, 4complete

ExampleInput
2 4
3 5
2 4 5 6
9 10 8 22
Output
19

加入题单

上一题 下一题 算法标签: