산유국

면접 대비

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

요약

원형으로 배치된 구역에서 위협 집단이 있는 구역을 K개 이상 포함하는 연속 구간을 골라 A의 합을 최대로 만드는 문제입니다.

문제

명실상부한 대국 The United States of Jooddae는 오늘도 세계 평화를 위해 힘쓴다. 이를 위해 USJ의 수장 오주원은 오늘도 평화 유지에 기여하기로 결심했다.

여러분도 잘 알다시피, 평화로운 민주주의를 유지하는 데 가장 중요한 조건은 바로 석유이다. 당신은 윤라크의 연속된 구역을 점령해 기름을 얻어낼 준비를 하고 있다.

USJ의 적국 윤라크는 $1$ 번부터 $N$ 번까지 번호가 붙은 원형 구역으로 나뉘어 있는 나라이다. 이 구역 중 일부에는 위협 단체가 존재한다.

하지만 석유를 추출하려고 적국을 침공하면 다른 나라의 눈치가 보이므로, 당신은 적국을 침공하면서 위협 단체가 존재하는 구역을 적어도 $K$ 개 점령하겠다고 선포했다.

$i$ 번째 구역을 점령하면 석유를 추출해 $A_i$ 만큼의 이익을 얻을 수 있다. 단, 점령에 드는 비용이 채산성보다 크면 이익은 음수가 될 수도 있다.

주원이가 최대한의 이익을 얻으려면 땅을 어떻게 점령해야 할까?

첫 번째 줄에는 구역의 개수 $N$ 과 점령한 구역에 있어야 하는 위협 단체의 최소 개수 $K$ 가 주어진다.

두 번째 줄에는 정수 $A_1, A_2, \dots, A_N$ 이 차례로 공백을 사이에 두고 주어진다.

세 번째 줄에는 $B_1, B_2, \dots, B_N$ 이 차례로 공백을 사이에 두고 주어진다. $B_i$ 가 $0$ 이면 $i$ 번째 구역에 위협 단체가 없고, $1$ 이면 있다.

주원이가 얻을 수 있는 최대 이익을 출력한다.