High Score (Hard Version)

**This is the hard version of the problem. The only difference is that in the easy version, $N$ is guaranteed to be equal to $M$.** You are given two arrays $A$ and $B$, of lengths $N$ and $M$ respectively, each consisting of positive integers. Your score is initially $0$. You can perform the following operation any number of times, as long as both arrays $A$ and $B$ are non-empty: - Select an