Brotherly Harmony

Long ago, in a village, an elder brother and a younger brother got along very well. Each planted rice in the paddy inherited from their late parents, tended it carefully, and harvested it. They stacked the leftover rice bundles in their own paddies. Worried about each other, they secretly moved the bundles from their own paddies to the other's paddy every night. Their hearts were in tune, so the amount of bundles gathered in each other's paddies never changed. One day, when they learned the truth, they hugged each other and wept.

Hyeonuk simulates the story of Brotherly Harmony as follows.

• The brothers inherited paddies from their parents, and the elder and the younger each got $N$ paddies. After the harvest, the elder's paddies held $a_1, a_2, \cdots, a_N$ bundles, and the younger's paddies held $b_1, b_2, \cdots, b_N$ bundles.
• Their hearts were in tune, so every night they chose the same integers $i, j$ ($1 \le i < j \le N$). Each brother moved the bundles in their own $i$-th paddy to the other's $j$-th paddy. Before moving, the $i$-th and $j$-th paddies of both brothers must still have bundles stacked.
• They repeated this every night until all bundles were gathered in the $N$-th paddy.

Hyeonuk is simulating the ways to gather all bundles into the $N$-th paddy. When no more bundles can be moved, what is the maximum possible difference between the amounts of bundles in the two $N$-th paddies?

For example, let $a_1, a_2, a_3 = [2, 3, 1]$ and $b_1, b_2, b_3 = [1, 2, 1]$. Here are two ways to gather all bundles in the 3rd paddy.

A way where the amounts in the 3rd paddies differ by $0$ when all bundles are gathered there.

A way where the amounts in the 3rd paddies differ by $2$ when all bundles are gathered there.

The first line contains an integer $N$ ($2 \le N \le 200\,000$).

The second line contains integers $a_1, a_2, \cdots, a_N$ ($1 \le a_i \le 1\,000$), separated by spaces.

The third line contains integers $b_1, b_2, \cdots, b_N$ ($1 \le b_i \le 1\,000$), separated by spaces.

Print the maximum possible difference between the amounts of bundles in the two $N$-th paddies, when all bundles are gathered in the $N$-th paddies in Hyeonuk's simulation.