Short Monotonic Stack + Binary Search in Python, faster than 90%
Intuition\n Describe your first thoughts on how to solve this problem. \nSort both the number pairs (xi, yi) and queries in the order of x. \nProcessing the que
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nSort both the number pairs `(xi, yi)` and queries in the order of x. \nProcessing the queries one by one from the largest `x_q`. \nMaintain a monotonic stack that stores the best `(xi+yi)` for each `yi` with all the `xi >= x_q`.\nIn this way, the solution can be found in the monotonic stack with the max `(xi, yi)` for `yi > y_q`. \nBinary search can be used for the monotonic stack since the elements are sorted by `yi`. \n\n# Code\n```\nclass Solution:\n    def maximumSumQueries(self, nums1: List[int], nums2: List[int], queries: List[List[int]]) -> List[int]:\n        nums = sorted([(v, u) for v, u in zip(nums1, nums2)])\n        stack = []\n        ans = [-1] * len(queries)\n        for x, y, i in sorted([(x, y, i) for i, (x, y) in enumerate(queries)], reverse=True):\n            while nums and nums[-1][0] >= x:\n                nx, ny = nums.pop()\n                while stack and stack[-1][0] <= ny and stack[-1][1] < nx + ny:\n                    stack.pop()\n                if not stack or stack[-1][0] < ny:\n                    stack.append([ny, nx + ny])\n            p = bisect_left(stack, [y, -inf])\n            if p < len(stack):\n                ans[i] = stack[p][1]\n        return ans\n```
['Binary Search', 'Greedy', 'Monotonic Stack', 'Python3']