どのようにしても橋が崩落してしまうのは、\(\max(w) > \min(v)\) の場合に限られます。 以降は \(\max(w) \leq \min(v)\) を仮定します。

ラクダたちの隊列が昇順でなくてはならない場合を考えてみましょう。 すると、\(1 \leq i < j \leq N\) を満たす \(i,j\) についてラクダ \(i,j\) 間の距離は \(x_{i,j}\) 以上でなくてはならない、という形の制約が \(N(N-1)/2\) 個与えられることがわかります。\(x_{i,j}\) は前処理をしておくことで \(O( \log M)\) で求められます。 このとき、頂点 \(i\) から \(j\) に \(x_{i,j}\) の有向辺を張ったグラフの頂点 \(1\) から \(N\) への、最長路の長さが(隊列を固定したときの)求める答えと対応しています。 このグラフは閉路を持たないため、動的計画法により最長路の長さを \(O(N^2)\) で求めることができます。

ラクダたちの隊列を全探索し、それぞれの場合について最長路を求めればよいです。 これは \(O(N! N^2 \log M)\) で実行可能であり、十分高速です。