I. Love at Cafe Liebe (Hard Version)
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

This is the Hard version of the problem. The problems differ in their constraints and input formats. A solution to one may not work for the other.

Kanako-chan loves Hime-chan secretly, so she wants to give her as much coffee as possible (Hime is a caffeine addict). There are $$$n$$$ types of coffee numbered from $$$1$$$ to $$$n$$$, but Hime is only interested in type $$$1$$$.

Kanako was offered help by Sumika-senpai. Sumika has an unlimited supply of certain types of coffee. Specifically, you are given a binary string $$$s$$$ of length $$$n$$$, where $$$s_i = 1$$$ if and only if Sumika has coffee of type $$$i$$$. Kanako can ask for any non-negative real amount of coffee of each type that Sumika has, as long as the total volume of coffee she requests is at most $$$v$$$.

After getting some coffee from Sumika, Kanako can then trade with other customers at Cafe Liebe. In particular, there are $$$m$$$ customers willing to trade. To trade with the $$$i$$$-th customer, Kanako must do the following:

  • Choose a non-negative real number $$$k$$$.
  • Give the customer $$$ka_i$$$ cups of coffee $$$x_i$$$ and $$$kb_i$$$ cups of coffee $$$y_i$$$
  • In return, the customer will give Kanako $$$kc_i$$$ cups of coffee $$$z_i$$$.

Kanako can trade with customers as many times as she wants. What is the maximum amount of coffee of type $$$1$$$ she can obtain?

Input

Input consists of multiple tests. The first line contains $$$t$$$, the number of tests ($$$1 \le t \leq 10$$$).

The first line of each test contains $$$n$$$, $$$m$$$, and $$$v$$$  — the number of coffee types, the number of customers, and the maximum amount of starting coffee ($$$1 \le n \le 20$$$, $$$0 \le m \le 100$$$, $$$1 \le v \le 10^{18}$$$).

The second line contains a string $$$s$$$ of length $$$n$$$ consisting of 0s and 1s. The $$$i$$$-th character is 1 if and only if Sumika has coffee of type $$$i$$$.

The next $$$m$$$ lines contain $$$6$$$ numbers each: $$$a_i$$$, $$$x_i$$$, $$$b_i$$$, $$$y_i$$$, $$$c_i$$$, and $$$z_i$$$, describing their trades ($$$1 \le x_i, y_i, z_i \le n$$$, $$$1 \le a_i, b_i, c_i \le 10^6$$$). Note that $$$x_i$$$, $$$y_i$$$, and $$$z_i$$$ are integers, whereas $$$a_i$$$, $$$b_i$$$, $$$c_i$$$ can be float numbers in the hard version. It is guaranteed that $$$x_i$$$, $$$y_i$$$, and $$$z_i$$$ are all distinct.

In the hard version, it always holds that $$$c_i \leq 5$$$.

Output

For each test, output a floating-point number, the answer. If Kanako can get an arbitrarily large amount of coffee, output $$$-1$$$.

Your answer is considered correct if its absolute or relative error does not exceed $$$10^{-6}$$$.

Formally, let your answer be $$$a$$$, and the jury's answer be $$$b$$$. Your answer is accepted if and only if $$$\frac{|a - b|}{\max{(1, |b|)}} \le 10^{-6}$$$.

Example
Input
1
3 2 1
011
2 2 1 3 4.5 1
2 1 2 3 4 2
Output
1.750000000000000000
Note

In the sample, one can show that the optimal exchange can't yield above 1.75 cups. It can be further shown that there exists some initial ratio such that the final value infinitely approaches 1.75.