Still sounds like an amusing challenge to me. Air and/or water will do to make underwater-breathing magic items. Then you can take the Maenads for some scuba combat, reducing their food consumption
and eventually getting you an underwater foothold.
PvK