406764: GYM102536 C Senpai

Valentine's Day was just around the corner, but Kouhai still hasn't confessed to Senpai at the Academy of Covert Machinations (ACM)! But alas, Kouhai knows that even if they do confess, it's all for nothing as Senpai has a track record of rejecting every single guy that confesses to her.

Senpai evaluates potential suitors using $$$q$$$ qualities. These qualities are also weighted with $$$W$$$ (where $$$W_i$$$ is the multiplier for the $$$i$$$th quality). Your quality scores is denoted by $$$P$$$, where $$$P_i$$$ is your score for the $$$i$$$th quality. For example, if the your score for quality $$$P_1$$$ is $$$3$$$, and it is weighted with $$$W_1 = 3$$$, your effective quality score is $$$3\times 3 = 9$$$. Obviously, a bigger quality score is better. Likewise, a smaller (or even negative) quality score hurts chances of getting Senpai to notice you.

Likewise Senpai has her own quality scores $$$S$$$, where $$$S_i$$$ is the score for the $$$i$$$th quality. You want to compare this with your own quality scores $$$P$$$. If $$$$$$\sum_{i=1}^{q} S_i \leq \sum_{i=1}^{q} P_i\cdot W_i$$$$$$ (i.e. your total sum of weighted qualities are at least the same as Senpai's), Senpai is then impressed and will accept your confession! $$$\heartsuit$$$ $$$\heartsuit$$$ $$$\heartsuit$$$ $$$\heartsuit$$$

However, a complicating factor is the fact that Senpai's qualities/standards change continuously over time, and can be represented using the equation: $$$$$$ S_i(t) = F_i\cdot t + C_i $$$$$$

In this equation, $$$t$$$ represents the time passed so far, $$$F_i$$$ represents the change rate factor for the $$$i$$$th quality, and $$$C_i$$$ is the constant factor for that quality. We can assume that at the start, $$$t = 0$$$, and that $$$F_i$$$ and $$$C_i$$$ are constants.

Since you're pretty average, all of your quality scores $$$P$$$ start out at zero too ($$$P_i(0) = 0$$$ for all $$$i$$$). To catch up, you have a growth rate limit $$$g$$$, which denotes the limit at which you can improve your quality scores as described by the following formula: $$$$$$ \sum_{i=1}^{q} \left(\frac{d}{dt}P_i(t)\right)^2 \leq g^2 $$$$$$

This means that the combined magnitude of all rate of changes in qualities is less than or equal to $$$g$$$. The rate of change $$$\frac{d}{dt}P_i(t)$$$ doesn't even need to be positive or constant — the total magnitude just needs to be less than or equal to your growth rate limit $$$g$$$.

Each quality score as a function of time, $$$P_i(t)$$$, can then be any continuously differentiable function as long as they satisfy the above condition.

Combining all aforementioned equations to compare to Senpai's score: $$$$$$\begin{align*} P_i(0) &= 0 \, \text{for all $i$ from $1$ to $q$}\\ \sum_{i=1}^{q} \left(\frac{d}{dt}P_i(t)\right)^2 &\leq g^2 \\ S_i(t) &= F_i\cdot t + C_i \end{align*}$$$$$$

And to win Senpai's heart, it must be true that $$$$$$\sum_{i=1}^{q} S_i(t) \leq \sum_{i=1}^{q} P_i(t)\cdot W_i.$$$$$$

Help Kouhai find the smallest $$$t$$$ that can satisfy the above criteria assuming he improves his qualities $$$P_i(t)$$$ optimally.

The first line of input contains a single integer $$$c$$$ denoting the number of test cases. The descriptions of the $$$c$$$ test cases follow.

The first line of each test case contains two space-separated positive integers $$$q$$$, and $$$g$$$; the number of qualities Senpai is looking at $$$q$$$, and Kouhai's growth limit with respect to time $$$g$$$.

A line containing $$$q$$$ space-separated integers follows, representing the weights $$$W_i$$$. The $$$i$$$th integer corresponds to $$$W_i$$$, the weight for the $$$i$$$th quality.

$$$q$$$ lines then follow, describing how Senpai's standards change over time. The $$$i$$$th line from which contains two space separated integers $$$F_i$$$ and $$$C_i$$$, the change rate factor and the constant factor for the $$$i$$$th quality ($$$S_i(t) = F_i\cdot t + C_i$$$).

Constraints

• $$$1 \le c \le 10^3$$$.
• $$$1 \leq q \leq 10^3$$$.
• The sum of the $$$q$$$s in a single test file is $$$\leq 10^4$$$.
• $$$1 \leq g \leq 5000$$$.
• $$$-5000 \leq W_i \leq 5000$$$.
• $$$-5000 \leq F_i, C_i \leq 5000$$$.
• The answer exists and is at most $$$5000$$$

For each test case, output a single line containing a single nonnegative real number $$$t_{\min}$$$, the earliest possible time $$$t \geq 0$$$ that Kouhai can win Senpai's heart.

Answers with an absolute or relative difference of at most $$$10^{-10}$$$ from the judge's answer will be accepted.

1
4 4
1 1 1 1
1 3
2 3
2 3
1 3

6.00000000000

The optimal way to achieve Senpai's standards is by distributing your growth rate like below:

1. $$$P_1(t) = 2t$$$
2. $$$P_2(t) = 2t$$$
3. $$$P_3(t) = 2t$$$
4. $$$P_4(t) = 2t$$$

This satisfies the constraints $$$$$$P_i(0) = 0$$$$$$ and $$$$$$\sum_{i=1}^{q} \left(\frac{d}{dt}P_i(t)\right)^2 \; \leq \; g^2.$$$$$$ With $$$P_i(t)$$$ like this, the earliest $$$t$$$ where $$$$$$\sum_{i=1}^{q} S_i(t) \leq \sum_{i=1}^{q} P_i(t)\cdot W_i$$$$$$ is $$$t = 6.0$$$. (Calculate the resulting $$$S_i(t)$$$ and $$$P_i(t)$$$ values to see.)

It can be shown that this is the minimum possible such $$$t$$$, among all possible choices of the $$$P_i$$$s.