All Tracks Problem

The Great Charzeh
/

Binary search algorithm, Matching, Medium-Hard

Problem
Editorial
Analytics

View Russian Translation

The great Charzeh is playing a game with Joffrey Baratheon. There are n knights in seven kingdoms. i-th knight has strength equal to ai (0 ≤ ai < m). There are also n+m-1 numbers f0, f1, ..., fn+m-2 on the walls of black castle.

"The game" consists of two turns. In the first turn, Charzeh chooses a permutation of numbers 0, 1, ..., n-1 like p0, p1, ..., pn-1.

In the second turn Joffrey chooses and integer i (0 ≤ i < n) and then beheads fpi + ai random residents of Winterfell. Charzeh is kind and Joffrey is cruel. That's why Charzeh tries to minimize and Joffrey tries to maximize the number beheaded people.

If they both play optimally, how many people will die?

Input

The first line of input contains two integers n and m (1 ≤ n, m ≤ 300).

The second line contains n integers a0, a1, ..., an-1 separated by spaces (0 ≤ ai < m).

The third line contains n+m-1 integers f0, f1, ..., fn+m-2 separated by spaces (1 ≤ fi ≤ 109).

Output

Print the number of beheaded people at the end of the game.

Note

This problem doesn't require any Game of Thrones knowledge. They're just some random words ;)

SAMPLE INPUT
4 10
7 0 9 1
5 61 53 6 7 72 75 42 5 79 91 5 16
SAMPLE OUTPUT
7
Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB

Best Submission

Similar Problems

Contributors

This Problem was Asked in

Initializing Code Editor...
Notifications
View All Notifications

?