vector<vector<int>> kClosest(vector<vector<int>> points, int k)
{
    sort(points.begin(), points.end(), sortX);

    multimap<int, int> M;
    int n = points.size();

    vector<vector<int>> V;

    // Calculate Eucledian distance for each point and insert it into a multimap
    // We are using a multimap because two different points may have the same distance from the origin
    for (int i = 0; i < n; i++)
    {
        int x = points[i][0], y = points[i][1];
        int d = (x * x) + (y * y);
        // Multimap values get automatically sorted based on their keys
        M.insert({d, i});
    }

    // Push the first k values into the resultant vector
    for (auto iter = M.begin(); iter != M.end() && k > 0; iter++, k--)
        V.push_back({points[iter->second][0], points[iter->second][1]});

    return V;
}
// Time Complexity : O(NLogN)
// Space Compelxity : O(N)

bool compare(const vector<int> &V1, const vector<int> &V2)
{
    return V1[1] < V2[1];
}

vector<vector<int>> optimalSum(vector<vector<int>> V1, vector<vector<int>> V2, int k)
{
    // Sort both arrays in ascending order of values
    sort(V1.begin(), V1.end(), compare);
    sort(V2.begin(), V2.end(), compare);

	// Necessary to initialize the 2D vector to {} because a test case demanded that we return an empty list incase there is no optmial sum
    vector<vector<int>> V = {};

    // Initialize the maximum sum
    int maxSum = INT_MIN;

    int m = V1.size();
    int n = V2.size();

    // Start from beginning of V1 and end of V2
    int left = 0, right = n - 1;

    while (left < m && right >= 0)
    {
        // Compute the sum of the values
        int valueSum = V1[left][1] + V2[right][1];

        // If sum is greater than k, decrement right by 1
        if (valueSum > k)
            right--;

        // If sum is lesser than k
        else
        {
            // If the maximum sum computed until now is lesser than or equal to the current computed sum
            if (maxSum <= valueSum)
            {
                // Since there exists a greater sum, clear the result vector
                if (maxSum < valueSum)
                {
                    maxSum = valueSum;
                    V.clear();
                }

                // Insert the values on the left and right indices
                V.push_back({V1[left][0], V2[right][0]});
                int index = right - 1;

                // Iterate till the beginning of V2 so as to check for pairs having the same value
                while (index >= 0 && V2[index][1] == V2[index + 1][1])
                    V.push_back({V1[left][0], V2[index--][0]});
            }
            left++;
        }
    }
    return V;
}