题目描述

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.

题目大意

最近你成为了西奈一个小国家的皇帝。你决定在边界建造一座长城保护你的国家不被野蛮人抢劫。你联系了“W Corp”——世界上唯一的建造坚不可摧的墙的公司。

“W Corp”用相同的格式建造所有墙。墙的长度是 $n$ 米，每一米墙按顺序从 $1$ 到 $n$ 编号，它们可能有不同的高度。高度的格式取决于三个固定的数组 $a,b,c$，它们各有 $n$ 个元素，对于任意 $1\le i\le n$ 满足 $a_i < b_i < c_i$，还有一个整数 $r\ (1\le r < n)$。三个数组和 $r$ 对于“W Corp”建造的任何墙都是相同的。

按照如下方式，具体的墙体设计的选择取决于两个不同的整数 $x,y\ (1\le x < y\le n-r+1)$。取两个整数区间：$[x,x+r-1]$ 和 $[y,y+r-1]$（区间包括端点）。那么第 $i$ 米墙的高度是：

• $a_i$，当 $i$ 不属于这两个区间
• $b_i$，当 $i$ 属于这两个区间中的恰好一个
• $c_i$，当 $i$ 属于这两个区间中的两个

墙的强度定义为每一米墙高度的和。

在“W Corp”建造的所有墙中，数组 $a,b,c$ 和整数 $r$ 都是固定的。公司提供了一份所有可能的墙体设计的列表，按照强度单调不减排序。你选择了其中第 $k$ 种墙体设计。你的任务是，求出你选择的墙的强度。

输入格式

第一行包括三个整数 $n,r,k\ (2\le n\le 30000,\ 1\le r < n,\ 1\le k\le \frac{(n-r)(n-r+1)}{2}\ \ )$，分别代表墙的长度，取的区间的长度，你的选择在列表中的位置。

第二行包括了数组 $a$ 的元素，$1\le a_i\le 10^6$。

第三行包括了数组 $b$ 的元素，$1\le b_i\le 10^6$。

第四行包括了数组 $c$ 的元素，$1\le c_i\le 10^6$。

输出格式

输出一个整数，“W Corp”的列表中第 $k$ 种墙的强度

样例解释

在样例中，能建造出的不同的墙有三种：

• 选择 $x=1,y=2$，墙的高度是 $[3,7,5,4]$，强度是 $19$。
• 选择 $x=1,y=3$，墙的高度是 $[3,3,5,5]$，强度是 $16$。
• 选择 $x=2,y=3$，墙的高度是 $[1,3,7,5]$，强度是 $16$。

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

16

提示

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