AT_tkppc4_2_g 平均レーティング

[problemUrl]: https://atcoder.jp/contests/tkppc4-2/tasks/tkppc4_2_g パ研には部長の E869120 君の他に部員 $ 1 $ から部員 $ N $ までの $ N $ 人の部員がいます。 パ研部員たちは全員AtCoderのコンテストに参加しており、E869120 君の現在のレーティングは $ A $、部員 $ i $ の現在のレーティングは $ a_i $ です。 彼は、パ研をより強い部活にするため、自分以外の部員に対してこれから以下のような操作を何回か行うことにしました。 - **操作 $ 1 $: 部員 $ 1 $ 人を選び、教育する。** 部員 $ i $ を $ 1 $ 回教育すると、その部員のレーティングが $ b_i $ 上がります。 また、何度も同じ部員を教育すれば、そのたびにレーティングが $ b_i $ 上がります。 このとき、E869120 君は毎回体力を $ c_i $ 消費します。 - **操作 $ 2 $: 現在部員であるうちの $ 1 $ 人を選び、圧力をかけて退部させる。** 部員 $ i $ を退部させるとき、E869120 君は体力を $ d_i $ 消費します。 E869120 君は、消費する体力の合計が $ K $ 以下となるようにこれらの操作を行い、彼自身を含むパ研部員のAtCoderレーティングの平均を最大化したいです。 このとき、達成できる最大の平均レーティングを求めて下さい。 なお、E869120 君は彼自身を教育することはできず、また退部することもないものとします。

入力は以下の形式で標準入力から与えられます。 > $ N $ $ K $ $ A $ $ a_1 $ $ b_1 $ $ c_1 $ $ d_1 $ $ a_2 $ $ b_2 $ $ c_2 $ $ d_2 $ ... $ a_N $ $ b_N $ $ c_N $ $ d_N $

達成できる最大の平均レーティングを出力してください。 絶対誤差または相対誤差が $ 10^{-4} $ 未満であれば正解となります。

### 制約 - 入力は全て整数である。 - $ 1\ \leq\ N\ \leq\ 1\ 500 $ - $ 1\ \leq\ K\ \leq\ 1\ 500 $ - $ 1\ \leq\ A\ \leq\ 10^9 $ - $ 1\ \leq\ a_i,\ b_i\ \leq\ 10^9 $ $ (1\ \leq\ i\ \leq\ N) $ - $ 1\ \leq\ c_i,\ d_i\ \leq\ K $ $ (1\ \leq\ i\ \leq\ N) $ ### 小課題 この課題には $ 2 $ つの小課題があります。 1. (300 点) $ N,\ K\ \leq\ 500 $ 2. (400 点) 追加の制約はない。