各 \(i\) に対して、主菜 \(i\) と合わせられない副菜の集合を高速に走査できるようにしておきます（隣接リストと似たような形式の配列などに入れておくとよい）。

セグ木 \((s_1, s_2, \dots, s_M)\) を \((b_1, b_2, \dots, b_M)\) で初期化しておきます。

主菜 \(i\) に対し、合わせられない副菜 \(j\) たちについて \(s_j \gets -\infty\) で更新した後、セグ木の全体の最大値と \(a_i\) の和を求めます。これが、主菜 \(i\) が選ばれる定食の価格の最大値となります。 主菜 \(i\) に対する計算をした後は、\(s_j \gets b_j\) に戻し、次の主菜についての計算をします。

セグ木の更新は全体で \(2L\) 回、最大値計算は \(N\) 回なので、計算量は \(O((N+L)\log(M))\) 時間です。