지성의 시험대라고 불리는 한 카드 게임이 있으며, 그 게임의 이름은 “แคง (Kang)”입니다. 이 게임에서 각 카드는 양의 정수로 된 점수를 가집니다. 게임을 시작할 때 당신은 $N$장의 카드를 받아 손에 쥐고 있으며, 테이블 위에는 또 다른 $M$장의 카드가 왼쪽에서 오른쪽으로 앞면이 보이도록 놓여 있습니다. 당신은 손에 받은 카드와 테이블 위에 놓인 카드 모두의 점수를 볼 수 있습니다. 그다음 당신은 테이블 위의 카드를 $k$라운드에 걸쳐 추가로 가져올 수 있는데, 반드시 왼쪽에서 오른쪽 순서대로 한 번에 한 장씩 가져와야 합니다. 각 라운드에서 카드를 가져온 후, 당신은 손에 있는 카드 중 점수가 같은 카드를 원하는 장수만큼 골라 버리는 동작을 1번 할 수 있습니다. 당신은 테이블에서 카드를 가져오고 손에서 카드를 버리는 과정을 $k$라운드 모두 마친 후, 손에 남은 카드들의 점수 합이 최소가 되도록 플레이 계획을 세워야 합니다.

다음 예를 생각해 봅시다.

처음에 당신이 다섯 장의 카드를 가지고 있고 그 점수가 $6, 3, 9, 6, 3$이며, 테이블 위에 왼쪽에서 오른쪽으로 놓인 카드의 점수가 $4, 6, 9, 6$이라고 합시다.

$k = 1$인 경우: 테이블 위의 카드를 단 1장만 가져올 수 있다면, 첫 번째 카드를 가져왔을 때 당신이 가진 카드의 점수는 $6, 3, 9, 6, 3, 4$가 됩니다. 그 후 점수가 같은 카드를 골라 1번 버릴 수 있는데, 가장 좋은 방법은 점수가 $6$인 카드 2장을 골라 버리는 것이며, 이때 남은 카드의 점수 합은 최솟값인 $3 + 9 + 3 + 4 = 19$가 됩니다.

$k = 2$인 경우: 테이블 위의 카드를 2장 가져올 수 있다면, 가장 좋은 방법은 다음과 같습니다. 점수가 $4$인 첫 번째 카드를 가져온 후, 점수가 $9$인 카드 한 장을 버리는 것을 선택합니다. 손에 남은 카드의 점수는 $6, 3, 6, 3, 4$가 됩니다. 그 후 점수가 $6$인 2번째 카드를 가져왔을 때, 점수가 $6$인 카드 3장을 버릴 수 있으며,이로써 남은 카드의 점수 합은 최솟값인 $3 + 3 + 4 = 10$이 됩니다.

$k = 3$인 경우: 테이블 위의 카드를 3장 가져올 수 있다면, 가장 좋은 방법은 다음과 같습니다. 첫 번째 카드를 가져왔을 때 손에 있는 카드의 점수는 $6, 3, 9, 6, 3, 4$가 됩니다. 그 후 점수가 같은 카드를 골라 1번 버릴 수 있는데, 가장 좋은 방법은 점수가 $3$인 카드 2장을 모두 버리는 것이며 손에는 $6, 9, 6, 4$가 남습니다. 그다음 점수가 $6$인 2번째 카드를 가져왔을 때 점수가 $6$인 카드 3장을 버릴 수 있어 손에는 $9, 4$가 남게 됩니다. 그리고 점수가 $9$인 카드를 3번째로 가져왔을 때 점수가 $9$인 카드 2장을 모두 버릴 수 있어, 남은 카드의 점수 합은 $4$가 됩니다.

$k = 4$인 경우: 테이블 위의 카드를 4장 가져올 수 있다면, 가장 좋은 방법은 다음과 같습니다. 점수가 $4$인 첫 번째 카드를 가져온 후 점수가 $4$인 카드 한 장을 버리는 것을 선택하면, 손에 남은 카드의 점수는 $6, 3, 9, 6, 3$이 됩니다. 그다음 2번째로 가져오는 카드의 점수는 $6$인데, 가장 좋은 방법은 점수가 $3$인 카드 2장을 모두 버리는 것이며 손에는 $6, 9, 6, 6$이 남습니다. 3번째로 가져오는 카드의 점수는 $9$이며, 점수가 $9$인 카드 2장을 모두 버리는 것을 선택합니다. 그리고 점수가 $6$인 마지막 카드를 가져올 때, 점수가 $6$인 카드 4장을 버릴 수 있습니다. 이번 버리기로 인해 손에 남은 카드가 없게 되며, 이는 카드의 점수 합이 $0$임을 의미합니다.

당신의 과제 (Your Task)

$k = 1, 2, 3, \ldots, M$일 때, $k$라운드가 끝난 후 “손에 남은 카드들의 점수 합의 최솟값”을 구하세요.

이 문제는 실제 대회에서 사용되는, 일반적인 형식과는 다른 프로그래밍 형식을 가집니다. 사용 방법에 대해서는 이 문제의 마지막 부분을 참고해 주세요.

구현 세부사항

다음 함수를 작성해야 합니다:

std::vector<long long> capsize(std::vector<int> A, std::vector<int> B)

매개변수는 다음과 같습니다:

• $A$는 길이 $N$인 배열로, 시작할 때 손에 있는 카드들의 번호를 나타냅니다.
• $B$는 길이 $M$인 배열로, 테이블 위에 놓인 카드들의 번호를 왼쪽에서 오른쪽 순서대로 나타냅니다.
• 이 함수는 길이 $M$인 배열 $C$를 반환해야 하며, 이는 $k = 1, 2, 3, \ldots, M$일 때 $k$라운드 동안 가능한 손에 남은 카드들의 점수 합의 최솟값을 나타냅니다.

예를 들어, $A = [6, 3, 9, 6, 3]$이고 $B = [4, 6, 9, 6]$이라면, 함수는 배열 $[19, 10, 4, 0]$을 반환해야 합니다.

제한

• $1 \le N, M \le 10^6$
• $1 \le i \le N$인 각 $i$에 대해 $1 \le A[i] \le 10^9$
• $1 \le i \le M$인 각 $i$에 대해 $1 \le B[i] \le 10^9$

서브태스크

참고

프로그래밍 안내

이 문제에서는 프로그램을 작성하여 그레이더(Grader) 시스템에 제출하는 방식이, 참가자가 입력을 받는 부분과 출력을 표시하는 부분을 직접 작성해야 하는 일반적인 프로그래밍 형식과 다릅니다. 이 문제에서 참가자는 지정된 함수 안에 필요한 계산 부분만 작성해야 합니다. 여러 입력 데이터는 함수의 매개변수를 통해 사용할 수 있으며, 계산 결과 또한 함수를 통해 반환해야 합니다. 참가자는 입력을 받는 부분의 프로그램을 작성할 필요가 없으며 출력 부분을 작성할 필요도 없습니다.

참가자에게는 다음과 같이 여러 파일이 제공됩니다. 참가자는 문제에서 지정한 단 하나의 파일만 수정하여 그 파일을 시스템에 제출해야 합니다:

• grader.cpp는 입력을 받고 출력을 내보내는 역할을 하는 메인 파일입니다.
• kang.cpp는 참가자가 여러 계산 프로그램을 작성해야 하는 파일이자 시스템에 제출하는 파일입니다(kang.cpp 파일 안에는 main() 함수가 없어야 하지만, 다른 함수들은 있을 수 있습니다).
• run_cpp.sh는 참가자가 전체 프로그램을 실행하기 위해 호출할 수 있는 파일입니다.
• compile_cpp.sh는 참가자가 프로그램을 컴파일하기 위해 호출할 수 있는 파일입니다.

참가자는 시스템에서 다운로드할 수 있는 .zip 파일을 받게 되며, 해당 파일의 압축을 풀면(extract) 4개의 파일이 모두 들어 있습니다. 참가자는 텍스트 에디터나 IDE를 사용하여 kang.cpp 파일을 수정하고, compile_cpp.sh 또는 run_cpp.sh를 호출하여 프로그램을 컴파일하거나 실행해야 합니다.

참가자가 프로그램을 실행하기 위해 run_cpp.sh 파일을 호출하면, 프로그램은 grader.cpp 파일에 명시된 대로 동작하며 “그레이더 파일 설명” 항목에서 해당 파일의 동작 방식을 설명합니다.