Open Sesame

Didi and chogahui05 followed a treasure map they picked up by chance and reached the spot it marked. The treasure was locked in a safe that opens only when a puzzle is solved. The puzzle goes like this.

There is a board of $N$ columns and $2^{31}$ rows. Each of the $N$ columns holds one pebble and one groove that the pebble has to end up in.

Once per second you may choose $X$ consecutive columns and raise every pebble in them by one cell, or lower every pebble in them by one cell. A pebble that already sits in its groove can be moved too. The puzzle is solved and the safe opens once every pebble sits in a groove.

A pebble and a groove are both $1 \times 1$, and a pebble counts as placed only when it sits exactly at the center of its groove. A pebble must never leave the board.

Didi wants to solve the puzzle as fast as possible while chogahui05 is away, then run off with the treasure. Write a program that computes the shortest time in seconds that solving the puzzle takes.

The picture above shows a board 3 columns wide and 5 rows tall, where ● is a pebble and ✕ is a groove. One of the fastest ways raises the pebbles in columns 1 to 3 by one cell, then lowers the pebble in column 2 twice. That takes 3 seconds.

The first line contains the number of columns $N$. ($1 \le N \le 1{,}000{,}000$)

The second line contains $N$ integers separated by spaces, giving the positions of the pebbles. The $i$th number is the height $Y_i$ of the pebble in column $i$. ($0 \le Y_i < 2^{31}$)

The third line contains $N$ integers in the same format, giving the positions of the grooves. ($0 \le Y_i < 2^{31}$)

Print the shortest time in seconds that solving the puzzle takes.