#include<vector>
#include<algorithm>
#include<iostream>
#include<string>

using namespace std;

struct node {
  int source;
  bool used;
  int value;
  int pos;
  node(int v, int p, int s): used(false), value(v), pos(p), source(s){}
};

bool compare(node * prev, node * next)
{
  return prev->value > next->value;
}

string find_max(int *m, int *n, int M, int N, int K)
{
  vector<node*> ordered;
  string result;
  int i;

  if (M+N < K)
    return "Invaild Input";

  int k_left = K;
  int last_n = INT_MIN, last_m = INT_MIN;
  for(i = 0; i < M; i++)
    ordered.push_back(new node(m[i], i, 1));

  for(i = 0; i < N; i++)
    ordered.push_back(new node(n[i], i, 2));

  sort(ordered.begin(), ordered.end(), compare);

  while(result.length() < K)
  {
    for (i = 0; i < ordered.size(); i++)
    {
nt m_left, n_left;
      bool Is_m = false;

      if (ordered[i]->used)
        continue;

      if (ordered[i]->source == 1 && ordered[i]->pos > last_m)
      {
        m_left = M - ordered[i]->pos;
        n_left = (last_n == INT_MIN)? N: N - last_n -1;
        Is_m = true;
      } else if (ordered[i]->source == 2 && ordered[i]->pos > last_n)
      {
        m_left = (last_m == INT_MIN)? M: M - last_m -1;
        n_left = N - ordered[i]->pos;
      } else {
        continue;
      }

      if (m_left + n_left >= K-result.length())
      {
        result.push_back(ordered[i]->value + '0');
        if (Is_m)
          last_m = ordered[i]->pos;
        else
          last_n = ordered[i]->pos;
        break;
      }
    }
  }
  return result;
}

int main()
{
  int N[4] = { 3 , 4 , 6,5};
  int M[6] = {9,1,2,5,8,3};

  int K = 5;

  cout<<" max number = " << find_max(M, N, 6, 4, K)<<endl;
int N2[4] = { 3, 4, 6, 5};
  int M2[6] = {2,1,5,3,8,9};

  cout<<" max number = " << find_max(M2, N2, 6, 4, 6)<<endl;
  return 1;
}