AT_bogosortcontest_div2_j RTA Strategy

jastaway くんは、全 $ N $ 個のステージからなるゲームのタイムアタックに挑戦しています。 現在の世界記録は $ T + 1 $ 秒であり、 jastaway くんの目標は全ステージのクリア時間の合計を $ T $ 秒以下にして世界記録を更新することです。 ステージは好きな順番で挑戦することができます。 ステージ $ i $ をクリアするには、 $ L_i $ 秒以上 $ R_i $ 秒以下の一様ランダムな整数の時間がかかります。 各ステージのクリア時間は、挑戦するたびに、それまでの結果とは独立に決まります。 実際にかかった時間は、そのステージをクリアした瞬間に判明します。 jastaway くんは、任意のステージをクリアした直後（または最初のステージに挑戦する前）に以下のいずれかの行動をとることができます。 1. 挑戦の継続：まだクリアしていないステージから1つ選び、挑戦する。 2. リセット：現在のタイムアタックの記録とクリア状況を全てリセットし、最初からやり直す。 リセットを行った場合、タイムアタックの記録タイムは $ 0 $ に戻りますが、 jastaway くんがこのゲームのタイムアタックを開始してからの経過時間（現実世界での経過時間）はリセットされず、加算され続けます。 また、各ステージ内で経過する時間以外の時間は無視できるものとします。 適切に行動を選んだ時、 jastaway くんが世界記録を更新するまでにかかる現実世界での経過時間の期待値の最小値を求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ T $ $ L_1 $ $ R_1 $ $ L_2 $ $ R_2 $ $ \vdots $ $ L_N $ $ R_N $

答えを出力せよ。 真の解との絶対誤差または相対誤差が $ 10^{-4} $ 以下のとき正解と判定される。

### Sample Explanation 1 以下のように行動するのが最適です - 最初にステージ $ 2 $ に挑戦する - 現在のタイムアタックの記録タイムが $ 3 $ 秒以上ならリセットし最初に戻る - ステージ $ 1 $ に挑戦する - 現在のタイムアタックの記録タイムが $ 4 $ 秒以上ならリセットし最初に戻る - ステージ $ 3 $ に挑戦する - 現在のタイムアタックの記録タイムが $ 6 $ 秒以上ならリセットし最初に戻る - 現在のタイムアタックの記録タイムが $ 5 $ 秒以下なら記録を更新したので終了する このときの世界記録を更新するまでにかかる現実世界での経過時間の期待値は $ 38.25 $ 秒です ### Sample Explanation 2 すべてのステージでクリアタイムのブレがないので、どの順番で挑戦しても確実に $ 10 $ 秒ですべてのステージをクリアできます。 ### Constraints - $ 1 \leq N \leq 9 $ - $ 1 \leq T \leq 250 $ - $ 1 \leq L_i \leq R_i \leq 250 $ - $ R_i - L_i \leq 12 $ - $ \sum_{i=1}^{N} L_i \leq T $ - 入力される数値はすべて整数