[Python3] 17 Lines Code, Monotonic Stack
Monotonic stack should be the authentic solution for this question\n\n# Approach\n Describe your approach to solving the problem. \nFirstly, sort $(a, b)$ pairs
# Monotonic stack should be the authentic solution for this question\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nFirstly, sort $(a, b)$ pairs of two lists as well as queries $[x, y]$ by the first axis $x$.\n\nWith the sorted queries, we can iterate the queries start from the biggest $x$ reqirement. During iteration, we continuely add valid $(a, b)$ pairs that satisfy $a >= x$. Since newly added $(a, b)$ pairs always have a smaller or equal $a$ value than previous pairs, if newly added pairs sum is greater than previous pairs, it must have a greater b value. For this reason, the previous pairs with smaller sum than newly added pair are no longer useful for future queries in decreasing x, and they can be discarded (pop out from stack).\n\nThere is another case, if the later $(a, b)$ pairs sum is smaller than previous pair sum, but it have a greater $b$ value, it can still be useful. \nFor example, consider two pairs $(50, 48)$ and $(40, 50)$ with a query $[40, 49]$. Though the sum of $(50, 48)$ is greater than $(40, 50)$, $(50, 48)$ is not valid for query $[40, 49]$.\n\nA monotonic stack is then used to store these candidate pairs as $[b, sum(a,b)]$, where $b$ values are stacked in assending order and pair sums are in desending order, indicate the current maximum possible sum for $y \\geq b$.\nWe run binary insertion to find the greatest $sum$ for current query $y$ limit.\n\n# Complexity\n\n- Time complexity: $$n \\log n$$\n\n- Space complexity: $$n$$\n\n# Code\n```\nclass Solution:\n    def maximumSumQueries(self, nums1: List[int], nums2: List[int], queries: List[List[int]]) -> List[int]:\n        ab = sorted((a, b) for a, b in zip(nums1, nums2))\n        for i, q in enumerate(queries):\n            q.append(i)\n        queries.sort(key=lambda q: -q[0])\n        st = []\n        ans = [-1] * len(queries)\n        for x, y, qid in queries:\n            while ab and ab[-1][0] >= x:\n                a, b = ab.pop()\n                while st and st[-1][1] <= a + b:\n                    st.pop()\n                if not st or st[-1][0] < b:\n                    st.append([b, a + b])\n            index = bisect_left(st, [y, ])\n            if index < len(st):\n                ans[qid] = st[index][1]\n        return ans\n```\n\n# Please Vote Up If You Like This Solution
['Monotonic Stack', 'Python3']