The Great Wall

You have become the emperor of Sinai, a small country. To stop the raids coming across the border you decided to build a great wall there, and you hired W Corp, the only company in the world that builds walls nobody can break through.

W Corp builds every wall from the same pattern. The wall is $n$ meters long, and each one meter piece is numbered from $1$ to $n$ along its length. Pieces may have different heights. The heights come from three fixed arrays $a$, $b$, $c$ of $n$ elements each, with $a_i < b_i < c_i$ for every $1 \le i \le n$, and from an integer $r$ ($1 \le r < n$). The three arrays and $r$ are the same for every wall W Corp builds.

A specific design is fixed by two integers $x$ and $y$ with $1 \le x < y \le n - r + 1$. Take the two ranges $[x, x+r-1]$ and $[y, y+r-1]$, both inclusive. The height of piece $i$ is:

• $a_i$ if $i$ lies in neither range,
• $b_i$ if $i$ lies in exactly one of the ranges,
• $c_i$ if $i$ lies in both ranges.

The strength of a wall is the sum of the heights of its $n$ pieces.

Because $a$, $b$, $c$ and $r$ never change, W Corp hands you a price list of every possible design sorted in non-decreasing order of strength. You pick the $k$-th design on that list. Report the strength of the wall you picked.

The first line contains three integers $n$, $r$, $k$ ($2 \le n \le 30000$, $1 \le r < n$, $1 \le k \le \frac{(n-r)(n-r+1)}{2}$): the length of the wall, the length of the chosen ranges, and the position on the price list.

The second line contains the $n$ elements of the array $a$ ($1 \le a_i \le 10^6$).

The third line contains the $n$ elements of the array $b$ ($a_i < b_i \le 10^6$).

The fourth line contains the $n$ elements of the array $c$ ($b_i < c_i \le 10^6$).

Print one integer, the strength of the $k$-th wall on the price list. Several designs can share the same strength, and the $k$-th strength value is the same whichever way those ties are ordered.

In the first example there are three walls you can build.

• Choosing $x = 1$ and $y = 2$ gives the heights $3\ 7\ 5\ 4$ and the strength $19$.
• Choosing $x = 1$ and $y = 3$ gives the heights $3\ 3\ 5\ 5$ and the strength $16$.
• Choosing $x = 2$ and $y = 3$ gives the heights $1\ 3\ 7\ 5$ and the strength $16$.