最大フロー問題である.

\((u_i, p_i), (v_i, q_i)\) を頂点するグラフを作成する. 出発と到着は頂点を分けておかないと待ち時間がうまく表せないので注意する. ソース頂点は \((1, 0)\) であり, シンク頂点は \((N, 10^9)\) である.

まずは便の数だけ, \((u_i, p_i) \rightarrow (v_i, q_i)\) に辺を張る. 容量は \(w_i\) である.

続いて, \((u_i, p_i) \rightarrow (u_i, p_j)\) に辺を張る. 容量は無限大である. ただし, \(p_j\) は \(p_i\) の次に出発する便である.

さらに, \((v_i, q_i) \rightarrow (u_j, p_j)\) に辺を張る. 容量は無限大である. ただし, \(p_j\) は \(q_i+d\) より後で次に出発する便である.

さらにソースから空港1の一番早い出発便に辺を張り, 空港 \(N\) の到着便とシンクに辺を張る.

あとは Dinic 法なりを使ってこのグラフの最大フローを求める.