#include <iostream>
#include <limits>

constexpr auto NoAnswer = std::numeric_limits<int>::min();

int FindKthMinSum(int* A, int* B, int szA, int szB, int k) {
    int a = 0, b = 0;
    
    for (int i = 1; i < k; ++i) {       // k is 1-based
        if (a == b || a + 1 >= szA) {   // must incrememt b
            if (++b >= szB)
                return NoAnswer;
        }
        else if (b + 1 >= szB)          // must increment a
            a++;
        else if (A[a + 1] < B[b + 1])   // otherwise choose smallest
            a++;
        else
            b++;
    }
    
    return A[a] + B[b];
}

int main() {
    int A[] {1, 2,  3};
    int B[] {1, 2, 99};
    
    std::cout << FindKthMinSum(A, B, 3, 3, 3) << '\n';  // prints 4
}

#include <iostream>
using namespace std;

int kthsum( int A[], int na, int B[], int nb, int k )
{
   int a = 0, b = 0;
   for ( int nth = 2; nth <= k; nth++ )
   {
      bool ok1 = ( a + 1 < na ) && ( a < b );
      bool ok2 = b + 1 < nb;
      if ( !( ok1 || ok2 ) ) return -1;  // whatever
      if ( !ok1 )
      {
         a = 0;
         b++;
      }
      else if ( !ok2 )
      {
         a++;
      }
      else
      {
         if ( A[a+1] + B[b] <= A[0] + B[b+1] )
         {
            a++;
         }
         else
         {
            a = 0;
            b++;
         }
      }
   }
   return A[a] + B[b];
}

int main()
{
   int A[] = { 1, 2, 3 };
   int B[] = { 1, 2, 99 };
   for ( int k = 1; k <= 7; k++ ) cout << kthsum( A, 3, B, 3, k ) << '\n';
}

#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>

template<typename T, size_t Sz> size_t SizeOf(T(&)[Sz]) { return Sz; }

struct Record {
    int i, j, ai, bj, sum;
    Record(int i, int j, int ai, int bj, int sum)
        : i(i), j(j), ai(ai), bj(bj), sum(sum) {}
};

std::ostream& operator<<(std::ostream& os, const Record& o) {
    auto W = std::setw;
    return os << W(5) << o.i  << W(5) << o.j
              << W(5) << o.ai << W(5) << o.bj
              << W(6) << o.sum;
}

int main() {
    int A[] { 3, 5, 13, 14, 22, 23};
    int B[] { 1, 2,  3,  6,  9, 10, 11, 13, 15, 18};

    std::vector<Record> v;
    for (int i = 0; i < (int)SizeOf(A); ++i)
        for (int j = i; j < (int)SizeOf(B); ++j)
            v.push_back(Record(i, j, A[i], B[j], A[i] + B[j]));

    std::sort(v.begin(), v.end(),
        [](const Record& a, const Record& b){
            if (a.sum == b.sum) return a.i < b.i;
            return a.sum < b.sum;
        });

    std::cout << "  k    i    j  A[i] B[j]  sum\n";
    int k = 0;
    for (const auto& o: v)
        std::cout << std::setw(3) << ++k << o << '\n';
    std::cout << '\n';
}

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;


int kthsum( const vector<int> &A, const vector<int> B, int k )
{
   int na = A.size(), nb = B.size();
   int largest  = A[na-1] + B[nb-1];
   int smallest = A[0] + B[0];      

   // Reject impossible k values
   if (   ( na <= nb && na * ( nb + nb - na + 1 ) / 2 < k )   ||
          ( na >  nb && nb * ( nb + 1           ) / 2 < k )      ) return smallest - 1;

   int amax, sum;

   // Current "front" ... the largest values of b currently used for a given a
   vector<int> lastb(na);
   for ( int a = 0; a < na; a++ ) lastb[a] = a - 1;

   // First sum
   sum = smallest;
   lastb[0] = 0;
   amax = 0;

   for ( int nth = 2; nth <= k; nth++ )
   {
      // Find minimum sum on the current "front" moved up 1 in the b direction
      sum = largest + 1;
      int aval;
      for ( int a = 0; a <= min( amax + 1, na - 1 ); a++ )
      {
         int b = lastb[a] + 1;   if ( b >= nb ) continue;
         int test = A[a] + B[b];
         if ( test <= sum )
         {
            aval = a;
            sum = test;
         }
      }
      if ( aval > amax ) amax = aval;
      lastb[aval]++;
   }
   return sum;
}


int main()
{
   vector<int> A = { 3, 5, 13, 14, 22, 23};
   vector<int> B = { 1, 2,  3,  6,  9, 10, 11, 13, 15, 18};
   int smallest = A[0] + B[0];

   for ( int k = 1; k <= 46; k++ )
   {
      int ksum = kthsum( A, B, k );
      if ( ksum >= smallest ) cout << k << '\t' << ksum         << '\n';
      else                    cout << k << '\t' << "Impossible" << '\n';
   }
}

 #include <iostream>
#include <ctime>
#include <string>
#include <cstdlib>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{  
  
   vector<int> A = { 3, 5, 13, 14, 22, 23};
   vector<int> B = { 1, 2,  3,  6,  9, 10, 11, 13, 15, 18};
   vector<int> res; //reserve space for performance, ignored here. 

   for(int i = 0; i < A.size(); i++)
    for(int j =i; j < B.size(); j++)	   
      res.push_back(A[i]+B[j]);   
    
    sort(res.begin(), res.end()); 
	for(int i = 0; i < res.size(); i++)
		cout << i+1 << " " << res[i] << endl;
   
}