Technology has moved on a little bit in the last 20+ years...
A fleet of AUV's might be a faster and cheaper way of doing the sea floor search. I guess it depends on how quickly someone can build and deploy them. I think 100 would be a reasonable number to start with and you might even get the unit price below the current 2M USD.