거대한 성벽

시간 제한3초메모리 제한512 MB

요약

길이 r인 두 구간을 골라 겹치는 부분에 추가 높이가 더해질 때, 모든 구간 쌍의 벽 전체 높이 중 k번째로 작은 값을 구한다.

난이도: 어려움10점 중 8점
유형: 이분 탐색, 누적 합, 동적 계획법, 정렬
정답자: 아직 제출이 없습니다

문제

당신은 작은 나라 시나이의 황제가 되었다. 국경 너머에서 넘어오는 약탈을 막으려고 국경에 거대한 성벽을 세우기로 했다. 공사는 뚫리지 않는 성벽을 짓는 세계 유일의 회사인 W사에 맡겼다.

W사는 모든 성벽을 같은 방식으로 짓는다. 성벽의 길이는 $n$ 미터이고, 1미터짜리 조각마다 길이 방향으로 $1$ 부터 $n$ 까지 번호를 붙인다. 조각마다 높이는 다를 수 있다. 높이는 길이가 $n$ 인 세 배열 $a$ , $b$ , $c$ 와 정수 $r$ ( $1 \le r < n$ )로 정해지며, 모든 $1 \le i \le n$ 에 대해 $a_i < b_i < c_i$ 이다. 이 세 배열과 $r$ 는 W사가 짓는 모든 성벽에서 같다.

구체적인 설계는 $1 \le x < y \le n - r + 1$ 을 만족하는 두 정수 $x$ 와 $y$ 가 정한다. 양 끝을 포함하는 두 구간 $[x, x+r-1]$ 과 $[y, y+r-1]$ 을 잡으면, $i$ 번째 조각의 높이는 다음과 같다.

두 구간 어디에도 속하지 않으면 $a_i$
두 구간 중 정확히 한 곳에만 속하면 $b_i$
두 구간 모두에 속하면 $c_i$

성벽의 강도는 조각 $n$ 개의 높이를 모두 더한 값이다.

$a$ , $b$ , $c$ 와 $r$ 는 어떤 성벽에서도 같으므로, W사는 가능한 설계를 모두 강도가 감소하지 않는 순서로 정렬한 가격표를 준다. 당신은 이 가격표에서 $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$ 의 원소 $n$ 개가 주어진다 ( $1 \le a_i \le 10^6$ ).

셋째 줄에 배열 $b$ 의 원소 $n$ 개가 주어진다 ( $a_i < b_i \le 10^6$ ).

넷째 줄에 배열 $c$ 의 원소 $n$ 개가 주어진다 ( $b_i < c_i \le 10^6$ ).

출력

가격표에서 $k$ 번째 성벽의 강도를 한 줄에 출력한다. 강도가 같은 설계가 여러 개 있어도 $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$ 이다.

예제2

예제 1
입력
```
4 2 1
1 2 3 4
3 3 5 5
7 7 7 7
```
예상 출력
```
16
```
예제 2
입력
```
4 2 3
1 2 3 4
3 3 5 5
7 7 7 7
```
예상 출력
```
19
```