G - 平均レーティング Editorial /

Time Limit: 3 sec / Memory Limit: 1024 MB

配点: 700 点

問題文

パ研には部長の 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 君は彼自身を教育することはできず、また退部することもないものとします。

制約

  • 入力は全て整数である。
  • 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 点) 追加の制約はない。

入力

入力は以下の形式で標準入力から与えられます。

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

3 200
2804
2416 20 30 80
2269 80 20 80
2115 30 40 70

出力例1

2656.33333

以下のような操作によって平均レーティングを最大にできます。

  • まず、部員 3 に圧力をかけて退部させる。このとき E869120 君は体力を 70 消費する。
  • 次に、部員 2 を 6 回教育する。このとき E869120 君は体力を 120 消費する。

操作の後、残っている部員は E869120 君と部員 1、部員 2 のみで、それぞれレーティングは 2804、2416、2749 になります。

入力例2

2 170
1
30 1 10 50
20 30 50 50

出力例2

47.66667

E869120 君は自分よりレーティングの高い部員も教育できることに注意して下さい。

入力例3

4 300
4089
2800 20 30 40
3200 30 40 50
3600 30 50 60
4000 20 70 80

出力例3

4089.00000

最適な操作をした場合、E869120 君は他の部員を全員退部させ、パ研部員は E869120 君 1 人となります。

writer: autumn_eel