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 つの小課題があります。- (300 点) N, K \leq 500
- (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