The garden at the Institute of Unbearable Torture (IUT) is known for its breathtaking beauty. Rows of vibrant flower columns line the pathways, each a testament to nature's charm. But lately, the greenery has started to fade.
There are $$$n$$$ flower columns in the garden. Each column has a total of $$$t_i$$$ flowers, out of which $$$s_i$$$ are healthy and green. To restore the garden's full glory, the campus gardening team will plant $$$m$$$ magical seeds. Each seed, when planted in a column, instantly grows into a new healthy flower.
The beauty score of a column is defined as: $$$\text{Score}_i = \dfrac{1}{t_i - s_i + 1}$$$
Your task is to determine the maximum average beauty score across all columns after planting the $$$M$$$ seeds optimally.
The first line contains an integer $$$t$$$ $$$(1 \le t \le 10^5)$$$ — the number of test cases.
Each test case consists of three lines:
The first line contains two integers $$$n$$$ and $$$m$$$ $$$(1 \le n \le 10^6,\ 0 \le m \le 10^9)$$$ — the number of flower columns and the number of magical seeds to be planted.
The second line contains $$$n$$$ integers $$$s_1, s_2, \dots, s_n$$$ $$$(1 \le s_i \le t_i)$$$ — the number of healthy flowers in each column.
The third line contains $$$n$$$ integers $$$t_1, t_2, \dots, t_n$$$ $$$(s_i \le t_i \le 10^9)$$$ — the total number of flowers in each column.
It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^6$$$.
Print a single real number — the maximum average beauty score achievable after planting the $$$M$$$ seeds optimally.
The answer will be considered correct if the absolute error does not exceed $$$10^{-6}$$$.
23 21 2 32 3 71 011
0.4 1
In the first test case, one of the optimal ways to plant the two seeds is to plant one seed in column $$$1$$$ and another in column $$$3$$$. After that, the beauty scores of the columns will be $$$\dfrac{1}{3 - 2 + 1} = 0.5$$$, $$$\dfrac{1}{3 - 2 + 1} = 0.5$$$ and $$$\dfrac{1}{8 - 4 + 1} = 0.2$$$ respectively. The average beauty score will be $$$0.4$$$.
