Segment Tree + Index compression
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n Describe your approach to solving the problem. \n\n# Complexity\n- Time 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\n\nclass Solution {\npublic:\n    vector<int> tree;\n    void update(int id, int l, int r, int ql, int qr, int val) {\n        if (qr < l || r < ql) return;\n        if (ql <= l && r <= qr) {\n            tree[id] = val;\n            return;\n        }\n        int mid = (l+r)/2;\n        update(2*id, l, mid, ql, qr, val);\n        update(2*id+1, mid+1, r, ql, qr, val);\n        tree[id] = max(tree[2*id], tree[2*id+1]);\n    }\n    int query(int id, int l, int r, int ql, int qr) {\n        if (qr < l || r < ql) return -1e4-1;\n        if(ql <= l && r<=qr) {\n            return tree[id];\n        }\n        int mid = (l+r)/2;\n        return max(query(2*id, l, mid, ql, qr), query(2*id+1, mid+1, r, ql, qr));\n    }\n    vector<int> maximumSumQueries(vector<int>& a, vector<int>& b, vector<vector<int>>& q) {\n        set<int> st;\n        for (auto& x : a) st.insert(x);\n        for (auto&x: b) st.insert(x);\n        for (auto& x : q) {\n            st.insert(x[0]);\n            st.insert(x[1]);\n        }\n        unordered_map<int,int> m;\n        int idx = 0;\n        for (auto&x : st) {\n            m[x] = idx;\n            idx++;\n        }\n        int sz = st.size();\n        tree.resize(4*sz+3,0);\n        vector<pair<int,int>> p;\n        for (int i = 0; i < a.size(); i++) {\n            p.push_back({a[i], b[i]});\n        }\n        for (int i = 0; i < q.size(); i++) {\n            q[i].push_back(i);\n        }\n        sort(p.begin(), p.end());\n        sort(q.begin(), q.end());\n        vector<int> ans(q.size(),-1);\n        idx = p.size()-1;\n        for (int i = q.size() -1; i >=0; i--) {\n            int x = q[i][0], y = q[i][1], z = q[i][2];\n            while(idx >=0 && p[idx].first >= x) {\n                int qi = query(1, 0, sz, m[p[idx].second],m[p[idx].second]);\n                if (qi < p[idx].first + p[idx].second) update(1,0,sz,m[p[idx].second],m[p[idx].second], p[idx].first + p[idx].second);\n                idx--;\n            }\n            int qi = query(1, 0, sz, m[y], sz);\n            if (qi > 0) {\n                ans[z] = qi;\n            }\n        }\n        return ans;\n    }\n};\n```
['Segment Tree', 'Sorting', 'C++']