F. Love at Cafe Liebe (Easy Version)
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

This is the easy 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 \le 50$$$).

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 50$$$, $$$0 \le m \le 10^3$$$, $$$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$$$ integers 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 \le 5$$$, $$$c_i = 1$$$). It is guaranteed that $$$x_i$$$, $$$y_i$$$, and $$$z_i$$$ are all distinct.

In the easy version, it always holds that $$$c_i = 1$$$.

Output

For each test, output a floating-point number, the answer.

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
4
3 1 20
011
2 2 3 3 1 1
1 0 1000000000000000000
0
8 12 8773
01100000
4 8 2 4 1 6
1 2 4 7 1 8
4 7 1 2 1 6
5 8 2 2 1 1
5 3 3 1 1 2
5 8 3 7 1 5
3 3 2 7 1 2
5 1 4 5 1 6
3 4 4 8 1 3
5 7 4 8 1 3
5 3 4 2 1 4
3 4 1 3 1 7
4 2 1
0011
2 3 5 4 1 2
5 2 1 4 1 1
Output
4.0
0
15.4726631393
0.02777777777777
Note

In the first test, you can ask for $$$8$$$ cups of type-2 coffee and $$$12$$$ cups of type-3 coffee. Then, you trade with customer $$$1$$$ using $$$k=4$$$, and thus recieve $$$4$$$ cups of type-1 coffee. We can show this is the maximum achievable.

In the second test, we cannot obtain any coffee of any type no matter what, so we output $$$0$$$.