23834번 - 커여운 키위

문제

키위는 뉴질랜드에 사는 새다. 키위는 수직선 위를 움직이는데, 처음에 0ドル$에서 시작해서 다음과 같은 과정으로 움직인다.

1. $i$ 번째로 이동할 때, 키위는 현재 위치에서 양의 방향 또는 음의 방향중 하나를 선택하여 그 방향으로 $A_i$만큼 이동한다.
2. 최근 $M$번 이동이 모두 양의 방향인 경우, 키위는 특별한 능력을 사용하여 양의 방향으로 $B_i$만큼 추가로 이동한 후, 이동을 종료한다.
3. 키위가 총 $N$번 이동한 경우, 이동을 종료하고, 아닌 경우 1번으로 돌아가서 다음 이동을 한다.

키위는 이동을 종료할 때까지 양의 방향으로 최대한 많이 이동하고 싶다. 가능한 키위의 움직임 중, 키위의 위치의 최댓값을 구해보자.

입력

첫 번째 줄에 $N$과 $M$이 공백으로 구분되어 주어진다.

두 번째 줄에 $A_1, A_2, \cdots, A_N$이 공백으로 구분되어 주어진다.

세 번째 줄에 $B_1, B_2, \cdots, B_N$이 공백으로 구분되어 주어진다.

출력

가능한 키위의 움직임 중, 키위의 위치의 최댓값을 출력하여라.

제한

• 1ドル \le N, M \le 500,円 000$
• 1ドル \le A_i \le 500,円 000$ (1ドル \le i \le N$)
• 1ドル \le B_i \le 500,円 000$ (1ドル \le i \le N$)
• 입력으로 주어지는 모든 수는 양의 정수이다.

힌트