병사 분배

시간 제한1초메모리 제한1024 MB

요약

N명의 병사를 장군 A, B, C에게 나누어 각 장군이 최소 K명을 맡도록 하면서 능력치 합의 최댓값을 구합니다.

난이도: 보통10점 중 7점
유형: 동적 계획법, 그리디, 정렬
정답자: 아직 제출이 없습니다

문제

어떤 나라에는 장군 $3$ 명 $A$ , $B$ , $C$ 와 병사 $N$ 명이 있다. 각 병사는 $1$ 번부터 $N$ 번까지 서로 다른 번호로 구분된다. 병사의 능력치는 어느 장군 밑에 소속되느냐에 따라 달라지며, 항상 양의 정수이다. 병사 능력치의 합은 병사들이 특정 장군 밑에 소속되어 발휘하는 능력치의 합이다.

장군들은 훈련과 전투를 각각 독립적으로 진행한다. 한 장군에게 소속된 병사가 적으면 훈련과 전투에 지장이 생긴다. 각 장군이 훈련과 전투를 수행하는 데 필요한 병사의 최소 인원 $K$ 가 주어진다. 모든 장군이 원활하게 훈련과 전투에 임할 수 있도록 병사들의 소속을 정하면서 병사 능력치의 합을 최대로 하라.

입력

첫 번째 줄에 병사의 수 $N$ , 전술을 위해 필요한 병사들의 최소 인원 $K$ 가 공백으로 구분되어 주어진다. $(3 \le N \le 200\,000$ , $1 \le K \le \lfloor \cfrac{N}{3} \rfloor)$

두 번째 줄에 $A$ 장군에게 소속되었을 때 병사들의 능력치가 $1$ 번 병사부터 $N$ 번 병사까지 차례대로 공백으로 구분되어 주어진다. $(1 \le A_i \le 10^9)$

세 번째 줄에 $B$ 장군에게 소속되었을 때 병사들의 능력치가 $1$ 번 병사부터 $N$ 번 병사까지 차례대로 공백으로 구분되어 주어진다. $(1 \le B_i \le 10^9)$

네 번째 줄에 $C$ 장군에게 소속되었을 때 병사들의 능력치가 $1$ 번 병사부터 $N$ 번 병사까지 차례대로 공백으로 구분되어 주어진다. $(1 \le C_i \le 10^9)$

출력

병사 능력치의 합의 최댓값을 출력한다.

예제2

예제 1
입력
```
4 1
1 2 3 4
3 1 2 2
2 3 1 3
```
예상 출력
```
13
```

예제 2

입력

10 2
6 3 3 8 7 1 5 1 7 5
4 8 5 10 3 4 9 10 1 3
8 7 3 4 2 7 7 8 9 6

예상 출력