最近你成为了西奈小国的皇帝。你决定在边境修建一座大墙，以保护你的国家免受蛮族袭击。你联系了“W Corp”，这是世界上唯一一家建造坚不可摧之墙的公司。

“W Corp”使用相同的模式建造每一座墙。墙的长度为 $n$ 米。墙的每一米都被编号为从 $1$ 到 $n$ 的整数，并且可以有不同的高度。高度模式基于三个长度均为 $n$ 的固定数组 $a$、$b$ 和 $c$，满足对于所有 $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]$（这些区间包含其端点）。那么，对于所有 $1 \le i \le n$，墙在第 $i$ 米处的高度等于：

• 如果 $i$ 不属于任何选定区间，则为 $a_i$；
• 如果 $i$ 属于恰好一个选定区间，则为 $b_i$；
• 如果 $i$ 属于两个选定区间，则为 $c_i$。

墙的强度定义为它所有 $n$ 个一米片段高度的总和。

数组 $a$、$b$、$c$ 和整数 $r$ 对于“W Corp”建造的任何墙都是相同的，因此该公司提供了一份价格表，列出了所有可能的墙体设计，并按其强度非递减的顺序排列。你选择了列表中第 $k$ 个墙体设计。任务是找出所选墙的强度。

输入格式

第一行包含三个整数 $n$、$r$ 和 $k$ ($2 \le n \le 30\,000$, $1 \le r < n$, $1 \le k \le \frac{(n-r)(n-r+1)}{2}$) —— 墙的长度、选择的片段长度以及墙在价格表中的位置。

第二行包含数组 $a$ 的元素 ($1 \le a_i \le 10^6$)。

第三行包含数组 $b$ 的元素 ($a_i < b_i \le 10^6$)。

第四行包含数组 $c$ 的元素 ($b_i < c_i \le 10^6$)。

输出格式

输出一个整数 —— “W Corp”价格表中第 $k$ 个墙的强度。

样例

输入 1

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

输出 1

16

说明

在样例测试中，我们可以建造三种不同的墙：

• 选择 $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。