#include <iostream>
#include "AVLTree.h"
bool canSatisfy(int N, int M, int* aArr, int* bArr){
    AVLTree a;
    AVLTree b;

    for(int i = 0; i < N; i++){ // N*logM
        a.insertKey(aArr[i]);
        if(a.getSize() > M){
            a.removeKey(a.getMin());
        }
        b.insertKey(bArr[i]);
        if(b.getSize() > M){
            b.removeKey(b.getMax());
        }
    }
    int count = 0;
    while(a.getSize() != 0 && b.getSize() != 0){ // M*logM
        if(a.getMin() > b.getMin()){
            count++;
            a.removeKey(a.getMin());
            b.removeKey(b.getMin());
        }
        else{
            a.removeKey(a.getMin());
        }
        if(count >= M){
            return true;
        }
    }
    //total N*logM
    return false;
}
int main(int argc, char* argv[]){

    int aArr[] = {2,4,10,3,6,9,12,1,11,13,11,20};
    int bArr[] = {3,11,5,8,18,12,9,14,13,7,2,12};
    int N = 12;
    int M = 6;
    int L = 0;

    int left = M;
    int right = N;

    while(left <= right){ //Binary search logN
        int mid = left+((right-left)/2);
        if(canSatisfy(mid,M,aArr,bArr)){ // canSatisfy = N*logM
            L = mid;
            right = mid-1;
        }
        else{
            left = mid+1;
        }
    }
    //total O(N*logN*logM)
    std::cout << L << std::endl;
}

I think this solution achieves the desired O(NlogNlogM) time complexity. Thanks to the suggestions from @nocomment