Computer Networks is a very important course in computer science. Suppose there are two machines, A and B, that need to transmit data through a chain-like network formed by $$$n-1$$$ routers. Specifically, when machine A wants to send data to machine B, it first sends the data to router 1, which then forwards it to router 2, router 2 forwards it to router 3, and so on, until router $$$n-1$$$ finally forwards the data to machine B.
Now, machine A needs to send $$$K$$$ bits of data to machine B. It first divides the data into $$$m$$$ groups, where the size of each group is $$$l_i$$$, satisfying $$$\Sigma l_i=K$$$. These groups are pushed to router 1 in the order of $$$l_1,l_2,...,l_m$$$. The push rate of machine A is $$$r_0$$$ bit/s, the push rate of router 1 is $$$r_1$$$bit/s, ..., and the push rate of router $$$n-1$$$ is $$$r_{n-1}$$$bit/s. The routers forward data in units of groups. When a router receives bits from a group, it waits until all bits of that group have arrived before starting to push the group to the next router. The forwarding strategy of the routers is first-come-first-served. While a router is forwarding data from one group, data from other groups is stored in the router's buffer, waiting to be forwarded. Assume that once a router or machine pushes a bit, the bit immediately arrives at the next router or machine. The question is: starting from the time when machine A pushes the first bit, at what time will machine B completely receive all $$$K$$$ bits of data sent by machine A?
The first line contains three positive integers $$$n(1 \leq n \leq 10^5), m(1 \leq m \leq 3\times 10^5), K(1\leq K\leq 3\times 10^5)$$$, which represent that the communication between machine A and machine B passes through $$$n-1$$$ routers, machine A divides the data to be transmitted to B into $$$m$$$ groups, and the total number of bits of data that machine A wishes to transmit to B is $$$K$$$, respectively.
The second line contains $$$n$$$ positive integers. The first integer is $$$r_0(1\leq r_0\leq 10^9)$$$, representing the push rate (in bit/s) of machine A. The following $$$n-1$$$ integers are $$$r_i(1\leq r_i\leq 10^9)$$$, where the $$$i$$$-th integer represents the push rate (in bit/s) of the $$$i$$$-th router.
The third line contains $$$m$$$ positive integers. The $$$i$$$-th integer is $$$l_i(1\leq l_i\leq K)$$$, representing the number of bits in the $$$i$$$-th group. It is guaranteed that $$$\Sigma l_i=K$$$.
A real number, in seconds, representing the time from when machine A pushes the first bit until machine B completely receives the entire $$$K$$$ bits of data that machine A intends to transmit to B. Suppose your answer is $$$Your\_Answer$$$ and the standard answer is $$$Answer$$$. If either $$$\frac{|Your\_Answer−Answer|}{Answer}\leq 10^{−9}$$$ or $$$|Your\_Answer−Answer|\leq10^{−9}$$$ is satisfied, then your answer is considered correct.
2 2 32 11 2
3.500000000000000
The data link is: A $$$\to$$$ Router 1 $$$\to$$$ B, where the push rate of A is 2 bit/s, and the push rate of Router 1 is 1 bit/s.
A intends to transmit 3 bits of data to B. Before sending, A divides the data into two groups, with lengths of 1 bit and 2 bits, respectively. A first pushes the group of length 1, followed by the group of length 2.
The second group is completely pushed to Router 1 after waiting for $$$\frac{1+2}{2}=1.5$$$ seconds. Since the first group completely arrives at Router 1 after waiting for $$$\frac{1}{2}=0.5$$$ seconds (i.e., the time for A to push it), and Router 1 takes $$$\frac{1}{1}=1$$$ second to completely push out the first group after fully receiving it, the second group arrives at Router 1 exactly when the first group is completely pushed out from Router 1. Thus, the second group does not need to queue at Router 1 and can be pushed out immediately. Therefore, the answer is $$$\frac{2+1}{2}+\frac{2}{1}=3.5$$$ seconds.
