시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 512 MB189484524.590%

문제

키위는 뉴질랜드에 사는 새다. 키위는 수직선 위를 움직이는데, 처음에 $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$)
  • 입력으로 주어지는 모든 수는 양의 정수이다.

예제 입력 1

3 2
3 2 1
1 1 10

예제 출력 1

10

다음과 같은 방법으로 $10$만큼 양의 방향으로 움직일 수 있다.

  • 음의 방향으로 $3$만큼 이동한다. 키위의 위치는 $-3$이 된다.
  • 양의 방향으로 $2$만큼 이동한다. 키위의 위치는 $-1$이 된다.
  • 양의 방향으로 $1$만큼 이동한 후, 특별한 능력을 사용하여 $10$만큼 추가로 이동한다. 키위의 위치는 $10$이 된다.

예제 입력 2

2 3
1 1
1 1

예제 출력 2

2

출처

High School > 세종과학예술영재학교 > SASA Programming Contest 2021 I번