All Tracks Problem

The Great Charzeh
Tag(s):

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
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, TypeScript, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

HackerEarth

Challenge Name

March Clash '16

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications

?