귀가

스파이더맨은 아직 고등학생이다. 우리 동네의 친절한 슈퍼히어로에게는 학교에서 듣는 과목이 $N$개 있으며, 번호는 0번부터 $N-1$번까지 매겨져 있다. 피터가 과목을 통과할 때마다 토니 스타크에게서 상금을 받는다. 피터가 $i$번 과목을 통과하면 $A_i$달러를 받는다.

과목을 통과하는 일은 안타깝게도 쉽지 않다. 통과하려면 교재를 몇 권 사야 한다. 물론 이 슈퍼히어로는 아주 똑똑해서 공부에 교재가 필요 없지만, 일부 선생님은 교재에 돈을 써야만 통과시켜 준다. 교재는 $N$권이 있으며 0번부터 $N-1$번까지 번호가 매겨져 있고, $i$번 교재의 가격은 $B_i$달러다.

$i$번 과목을 통과하려면 교재 $i$, $(i + 1) \bmod N$, $(i + 2) \bmod N$, $\ldots$, $(i + K - 1) \bmod N$을 사야 한다. 여기서 $K$는 주어진 상수다.

피터는 이제 학교에 관심이 없다. 그의 꿈은 어벤져스가 되는 것이므로 모든 과목을 통과하는지 여부는 상관없다. 피터는 시간을 아끼며, 시간이 곧 돈이므로 피터가 가장 큰 이익을 내도록 도와라.

$SN$을 $solve$의 모든 호출에 걸친 $N$의 총합이라 하고, $SNK$를 $solve$의 모든 호출에 걸친 $N \cdot K$의 총합이라 하자. 이때 다음이 성립한다.

• $1 \le K \le N \le 2{,}000{,}000$
• $1 \le SN \le 2{,}000{,}000$
• $0 \le A_i, B_i \le 1{,}000{,}000{,}000$

• 두 양의 정수 $A$와 $B$에 대해, $A \bmod B$는 $A$를 $B$로 나눈 나머지를 뜻한다.
• 공개 테스트는 다른 테스트와 묶이지 않는다.