The Great Wall

Time limit3sMemory limit512 MB

Summary

Each design picks two length-r intervals whose overlap height adds extra cost; find the k-th smallest total wall height over all interval pairs.

Level: Hard8 of 10
Topics: Binary search, Prefix sum, Dynamic programming, Sorting
Solved: No attempts yet

Problem

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.

Input

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$ ).

Output

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.

Hint

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$ .

Examples2

Example 1
Input
```
4 2 1
1 2 3 4
3 3 5 5
7 7 7 7
```
Expected output
```
16
```
Example 2
Input
```
4 2 3
1 2 3 4
3 3 5 5
7 7 7 7
```
Expected output
```
19
```