Maximizing Profit from Courses

There are $N$ courses numbered from $0$ to $N-1$ and $N$ textbooks also numbered from $0$ to $N-1$. If you pass course $i$, you earn $A_i$ dollars. However, to pass course $i$, you must purchase the textbooks numbered $i$, $(i+1) \bmod N$, $(i+2) \bmod N$, (\ldots), $(i+K-1) \bmod N$. The $i$-th textbook costs $B_i$ dollars. Note that when passing a course, you must buy a new copy of each required textbook even if it has been purchased for another course. Your goal is not to pass all courses, but to maximize your total profit. The profit for course $i$ can be expressed in (\LaTeX) as:

[ \text{profit}i = A_i - \sum{j=0}^{K-1} B_{(i+j)\bmod N} ]

You may choose any subset of courses (possibly none) so that the sum of positive profits is maximized. Write a function that, given the parameters, returns the maximum profit you can earn.

inputFormat

The function receives the following parameters:

• int N: the number of courses (and textbooks).
• int K: the number of consecutive textbooks required to pass a course.
• int *A: an array of length N where A[i] is the reward for passing course i.
• int *B: an array of length N where B[i] is the cost of textbook i.

For C++ the function signature is:

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

For other languages, implement an equivalent function.

outputFormat

The function should return a long long integer representing the maximum profit achievable.

The profit for each course (i) is calculated as:

[ \text{profit}i = A_i - \sum{j=0}^{K-1} B_{(i+j)\bmod N} ]

Only courses with positive profit should be considered. The answer is the sum of the profits of those courses.

sample

N = 3, K = 2, A = [40, 80, 100], B = [140, 0, 20]

60