Background

Translated from BalkanOI 2018 Day 1 T2 “Homecoming”. Since Luogu is much slower than loj, the time limit is adjusted from 300 ms to 500 ms.

Problem Description

There are $N$ courses, numbered from $0$ to $N-1$. If you pass course $i$, you can earn $A_i$ dollars.
There are $N$ textbooks, numbered from $0$ to $N-1$. The price of textbook $i$ is $B_i$ dollars.
If you want to pass course $i$, you need to buy the textbooks numbered $i, (i+1) \bmod N, (i+2) \bmod N, \cdots, (i+K-1) \bmod N$. $K$ is a given constant.
Your goal is to make money rather than pass all courses. Please compute the maximum number of dollars you can earn.

Input Format

See “Interaction”.

Output Format

See “Interaction”.

Hint

Constraints and Limits

Let the sum of $N$ over all calls to the solve function be $S_N$, and the sum of $NK$ be $S_{NK}$. Then:

• $1\le K\le N\le 2\times 10^6$
• $1\le S_N\le 2\times 10^6$
• $0\le A_i,B_i\le 10^9$

The detailed subtasks and additional limits are shown in the table below.

Translated by ChatGPT 5