병사 분배

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

요약
N명의 병사를 세 장군에게 각각 K명 이상 배정하면서 능력치 합이 최대가 되도록 분배한다.
난이도

어려움10점 중 8점

유형
동적 계획법, 그리디, 정렬
정답자
아직 제출이 없습니다

문제

어떤 나라에는 장군 33명 AA, BB, CC와 병사 NN명이 존재한다. 각각의 병사는 11번부터 NN번까지의 서로 다른 번호로 구분되며 어떤 장군 밑으로 들어가냐에 따라 발휘할 수 있는 능력치가 달라지며 능력치는 항상 양의 정수이다. 병사 능력치의 합이란 병사들이 특정 장군 밑에 소속되어 발휘할 수 있는 능력치들의 합이다.

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

입력

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

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

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

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

출력

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

예제2

  1. 예제 1

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

  2. 예제 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
    예상 출력
    78