Problem K
Digital Padlock
Languages
en
is
To improve your computer security you put a large lock on your computer, so that it cannot be turned on without opening that combination lock first.
But now there is a bit of an issue as the competition is starting real soon, and you need to get the lock open as fast as possible!
To open the lock, each wheel on the lock needs to be turned one step at a time until it shows the correct number out of the $M$ available numbers. The wheels can be turned either up or down to increase or decrease the shown number by $1$, except $M$ increases to $1$ and $1$ decreases to $M$.
To speed things along you can also place a finger along a contiguous interval of wheels and move them all up or down by one in a single step. For example, you could go from $1, 2, 3, 2$ to $2, 3, 4, 2$ by turning the first three wheels together. But you cannot turn the first and fourth wheel together without turning the second and third wheels as well.
How many steps does it take to open the lock at a minimum?
Input
The first line of input contains two integers $1 \leq N, M \leq 10^5$, separated by spaces. $N$ denotes the number of wheels and $M$ the number of possible values on each wheel. Next there are two lines, each with $N$ numbers, each of them at least $1$ and at most $M$. The first line gives the values visible on each wheel of the lock in order while the second gives the values needed on each wheel to unlock the lock.
Output
Print the minimum number of steps needed to open the lock.
Explanation of samples
In the first sample we start by turning the first two wheels
up by two steps and the last two down by two steps. This is a
total of four steps and we end up with $3, 4, 3, 2, 3$ showing on the lock.
Then we only have to turn the first wheel up twice and the last
down twice, which gives $8$ steps in total.
In the second sample we start by rotating all wheels up by one to get $2, 2, 2, 2, 2$. Then we just have to turn the middle wheel down twice. First it shows $2$, then $1$ and then $8$ as each wheel has $8$ numbers. This means $8$ and $1$ will be adjacent. In total this takes $3$ steps.
| Sample Input 1 | Sample Output 1 |
|---|---|
5 10 1 2 3 4 5 5 4 3 2 1 |
8 |
| Sample Input 2 | Sample Output 2 |
|---|---|
5 8 1 1 1 1 1 2 2 8 2 2 |
3 |
