P6958 [NEERC 2017] The Great Wall

最近你成为了西奈一个小国家的皇帝。你决定在边界建造一座长城保护你的国家不被野蛮人抢劫。你联系了“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$。

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