퀴즈 쇼
시간 제한5초메모리 제한128 MB
N개의 문제를 순서대로 풀면서 정답과 오답을 선택해 총점을 최대화하는 문제입니다. 정답을 맞히면 코인이 쌓이고 M개를 채우면 보너스 점수를 받으며, 오답을 내면 코인이 모두 초기화되고 점수가 깎입니다.
문제
도현이는 TV 퀴즈 쇼에 참가했다. 문제는 1번부터 N번까지 순서대로 풀어야 한다.
도현이는 모든 문제의 정답을 알고 있으므로, 각 문제마다 맞힐지 일부러 틀릴지 선택할 수 있다.
문제를 맞히면 코인 1개와 그 문제의 기본 점수를 얻는다. 문제를 틀리면 지금까지 가진 코인을 모두 잃고, 그 문제의 기본 점수만큼 점수가 감소한다.
문제를 맞혀서 코인이 M개가 되면, 그 문제의 보너스 점수를 추가로 얻고 모든 코인을 반납하여 코인 수가 0개가 된다.
도현이가 얻을 수 있는 최대 점수를 구하라.
입력
첫째 줄에 문제의 개수 N과 보너스 점수를 받기 위해 필요한 코인 수 M이 주어진다. (1 ≤ N, M ≤ 500,000)
둘째 줄에는 1번 문제부터 N번 문제까지의 기본 점수가 순서대로 주어진다. 셋째 줄에는 1번 문제부터 N번 문제까지의 보너스 점수가 순서대로 주어진다.
각 기본 점수는 1,000 이하의 음이 아닌 정수이고, 각 보너스 점수는 10,000 이하의 음이 아닌 정수이다.
출력
도현이가 얻을 수 있는 최대 점수를 출력한다.