문제

Recently you had become an emperor of a small country of Sinai. You had decided to build a big wall at the border to save your country from barbarian raids. You had contacted "W Corp", the only company in the world that builds non-penetrable walls.

"W Corp" builds each wall using the same pattern. The length of the wall is $n$ meters. Each one-meter piece of the wall is numbered by an integer from $1$ to $n$ along its length and may have a different height. The height pattern is based on three fixed arrays $a$, $b$, and $c$ of $n$ elements each, such that $a_i < b_i < c_i$ for all $1 \le i \le n$, and an integer $r$ ($1 \le r < n$). These arrays and $r$ are the same for any wall that is built by "W Corp".

The choice of the specific wall design is determined by two distinct integers $x$ and $y$ ($1 \leq x < y \leq n - r + 1$) in the following way. Take two ranges of integers: $[x, x + r - 1]$ and $[y, y + r - 1]$ (these ranges are inclusive of their ends). Then the height of the wall at one meter piece $i$ for all $1 \le i \le n$ is equal to:

• $a_i$ if $i$ does not belong to any of the chosen ranges;
• $b_i$ if $i$ belongs to exactly one chosen range;
• $c_i$ if $i$ belongs to both chosen ranges.

A strength of a wall is defined as the sum of all heights of its $n$ one meter pieces.

The arrays $a$, $b$, $c$, and an integer $r$ are the same for any wall built by "W Corp", so the company provides a price list with all the possible wall designs, sorted in non-decreasing order of their strength. You choose the $k$-th wall design from the list. The task is to find the strength of the chosen wall.

입력

The first line of the input contains three integers $n$, $r$ and $k$ ($2 \leq n \leq 30\,000$, $1 \leq r < n$, $1 \leq k \leq \frac{(n - r)(n - r + 1)}{2}$) — the length of the wall, the length of the segments to choose, and the position of the wall in the price list.

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

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

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

출력

Print one integer — the strength of the $k$-th wall from "W Corp" price list.

예제 입력 1

4 2 1
1 2 3 4
3 3 5 5
7 7 7 7

예제 출력 1

16

노트

In the sample test we could build three different walls:

• The choice of $x = 1$ and $y = 2$ yields heights "3 7 5 4" with the strength of 19;
• The choice of $x = 1$ and $y = 3$ yields heights "3 3 5 5" with the strength of 16;
• The choice of $x = 2$ and $y = 3$ yields heights "1 3 7 5" with the strength of 16.