Land of the Shire
All submissions for this problem are available.
The land of The Shire is separated from Rivendell by a long hanging bridge. When viewed from the side, the bridge seems to be an endless array of planks. The planks of the array are numbered from left to right with integers, starting with 1. The elves from Rivendell are playing a game. At the beginning of the game the i-th elf is above the plank number hi. Every elf can only take one step to the left or one step to the right or stay in the same position. During the game each elf's movement does not affect the movement of the other elves: there can be more than one elf on any of the planks. A plank is considered to be passed if at least one elf has visited this plank. In particular, all of the planks numbered h1, h2, ..., hn have been passed at the beginning of the game. m distinct planks with numbers p1, p2, ..., pm need to be passed. Determine the minimum steps the elves need to move to pass over all the given planks. Note that an arbitrary number of other planks can also be passed./p>
The first line of the input contains two space-separated integers n, m (1 ≤ n, m ≤ 10^5) — the number of elves and the number of planks to be passed, accordingly. The second line contains n distinct integers hi in ascending order (1 ≤ hi ≤ 10^10, hi < hi + 1) — the initial positions of the each elf. The third line contains m distinct integers pi in ascending order (1 ≤ pi ≤ 10^10, pi < pi + 1) - the numbers of planks to be passed.
Print a single number — the minimum steps required to pass all the needed planks.
Input: 3 4 2 5 6 1 3 6 8 Output: 2
Note : This problem has been inspired from previously solved questions.
|Time Limit:||2 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.