the-great-charzeh

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 ≤ 10^9).

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

Source: hackerearth | Difficulty: MEDIUM_HARD
Tags: Sorting

Flows and cuts


Solutions: