Home Coming

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

• 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.