Problem Description

The Programming Club has the president, E869120, and $ N $ members numbered from $ 1 $ to $ N $.
All members of the Programming Club participate in AtCoder contests. E869120's current rating is $ A $, and member $ i $'s current rating is $ a_i $.
To make the Programming Club stronger, E869120 decided to perform the following operations on the members (excluding himself) multiple times:

• Operation $ 1 $: Choose one member to educate.
  Educating member $ i $ once increases their rating by $ b_i $.
  Educating the same member multiple times will increase their rating by $ b_i $ each time.
  E869120 consumes $ c_i $ stamina each time he educates a member.

• Operation $ 2 $: Choose one current member to force out of the club.
  Forcing member $ i $ out of the club consumes $ d_i $ stamina.

E869120 wants to perform these operations such that the total stamina consumed is within $ K $ and maximize the average AtCoder rating of the Programming Club members including himself.
Find the maximum achievable average rating.
Note that E869120 cannot educate himself or leave the club.

Input Format

The input is given from the standard input in the following format:

$ 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 $

Output Format

Output the maximum achievable average rating.
The answer will be considered correct if the absolute or relative error is less than $ 10^{-4} $.

Sample Input and Output

Sample Input #1

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

Sample Output #1

2656.33333

Sample Input #2

2 170
1
30 1 10 50
20 30 50 50

Sample Output #2

47.66667

Sample Input #3

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

Sample Output #3

4089.00000

Notes/Hints

Constraints

• All inputs are integers.
• $1 \leq N \leq 1500$
• $1 \leq K \leq 1500$
• $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)$

Subtasks

This task has two subtasks:

1. (300 points) $N, K \leq 500$
2. (400 points) No additional constraints.

见题面 Input 部分

见题面 Output 部分