시간 제한메모리 제한제출정답맞힌 사람정답 비율
0.3 초 512 MB422100.000%

## 문제

Spiderman is still in high school. Our friendly neighborhood superhero has N subjects at school numbered from 0 to N-1. For each subject Peter passes, he receives a prize in money from Tony Stark. If Peter passes subject number i, he receives Ai dollars.

Passing a subject is unfortunately not that easy. In order to pass he needs to buy some textbooks. Of course, our friendly superhero is very smart, so he doesn’t need any textbook to study, but some teachers just won’t let him pass unless he invests some money in the books. There are N textbooks numbered from 0 to N – 1, the i-th of which costs Bi dollars.

In order to pass subject number i, Peter needs to buy textbooks i, (i + 1) % N, (i + 2) % N, …, (i + K – 1) % N, where K is a given constant.

Peter doesn’t care about school anymore since his dream is to become an Avenger, so it’s not relevant whether he passes all subjects or not. Peter loves time, and time is money, so help Peter make the biggest profit.

## 제한

Let SN be the sum of all N’s over all calls of solve, and let SNK be the sum of N*K over all calls of solve. Then:

• 1 ≤ K ≤ N ≤ 2,000,000
• 1 ≤ SN ≤ 2,000,000
• 0 ≤ Ai, Bi ≤ 1,000,000,000

## 인터랙션

The contestant should include the header homecoming.h.

The contestant needs to implement the following function:

long long int solve(int N, int K, int *A, int *B);

This function may be called multiple times over the course of a single run.

## 예제

call returned value
solve(3, 2, [40, 80, 100], [140, 0, 20]) 60

## 서브태스크

번호배점제한
113

1 ≤ SN ≤ 500

218

1 ≤ SN ≤ 5,000

331

1 ≤ SNK ≤ 2,000,000

438

## 노트

• Given two positive numbers A and B, A % B denotes the remainder of A when divided by B.
• The visible tests will not be grouped with other tests.

## 제출할 수 있는 언어

C++17, C++14, C++20, C++14 (Clang), C++17 (Clang), C++20 (Clang)

## 채점 및 기타 정보

• 예제는 채점하지 않는다.