C++ solution
\nclass Solution {\npublic:\n    long long kSum(vector<int>& nums, int k) {\n        long sum = 0;\n        vector<int> q;\n        \n        for (auto x: nums)
```\nclass Solution {\npublic:\n    long long kSum(vector<int>& nums, int k) {\n        long sum = 0;\n        vector<int> q;\n        \n        for (auto x: nums) {\n            if (x >= 0){\n                sum += x;\n                q.push_back(-x);\n            } else q.push_back(x);\n        }\n        \n        sort(q.begin(), q.end(), greater<int>());\n        \n        if (q.size() > k) q.erase(q.begin() + k, q.end());\n        vector<long> a(1, sum), b;\n        int t = 1;\n        \n        for (auto x: q) {\n            b.clear();\n            int i = 0, j = 0;\n            t = min(t * 2, k);\n            while (i < a.size() && j < a.size() && b.size() < t)\n                if (a[i] > a[j] + x) b.push_back(a[i++]);\n                else b.push_back(a[j++] + x);\n            while (i < a.size() && b.size() < t) b.push_back(a[i++]);\n            while (j < a.size() && b.size() < t) b.push_back(a[j++] + x);\n            a = b;\n        }\n        return a[k - 1];\n    }\n};\n```
[]