Statement

Erin loves farming PP (performance points) in osu!, and he wants to maximize his gains. He has an assortment of N beatmaps which he has played before, numbered from 0 to N-1, where each beatmap has an assigned PP value. He also has M other beatmaps that he hasn't played yet, which are likewise numbered from 0 to M-1 and each one of the N+M beatmaps has an assigned PP value. In order to quench his addiction, he decides to take a look at Q scenarios of the type: "What if my top plays are only made up of the already played maps from [l_1, r_1], and I can take any number, K, of unplayed maps from [l_2, r_2], and overwrite any K of my top plays; what is the maximum possible PP sum that I can obtain, if I choose K and the K beatmaps optimally?" For each of these scenarios, you have to find the maximum PP sum that can be obtained, choosing K optimally.