题目描述

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 \le x < y \le 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 \le n \le 30 000 , 1 \le r < n , 1 \le k \le (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 \le a_{i} \le 10^{6}).$

The third line of the input contains the elements of the array $b (a_{i} < b_{i} \le 10^{6}).$

The fourth line of the input contains the elements of the array $c (b_{i} < c_{i} \le 10^{6}).$

输出格式

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

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

16

提示

Time limit: 3 s, Memory limit: 512 MB.