In the year 3333, on a planet in the galaxy, the X Legion and the Y Legion are engaged in fierce combat. At a certain stage of the battle, the Y Legion has dispatched $N$ giant robots to attack the X Legion's positions, where the $i$-th giant robot has an armor value of $A_i$. A giant robot is destroyed when its armor value is reduced to 0 or less. The X Legion has $M$ laser weapons, where the $i$-th laser weapon can reduce the armor value of a giant robot by $B_i$ per second. The laser weapon attacks are continuous. These laser weapons are quite peculiar: each laser weapon can only attack certain specific enemies. Seeing their giant robots being destroyed one by one by the X Legion, the Y Legion urgently needs to issue more instructions. To this end, the Y Legion needs to know the minimum time required for the X Legion to destroy all of the Y Legion's giant robots. However, they do not know how to calculate this, so they are asking for your help.

Input

The first line contains two integers, $N$ and $M$. The second line contains $N$ integers, $A_1, A_2, \dots, A_N$. The third line contains $M$ integers, $B_1, B_2, \dots, B_M$. The next $M$ lines each contain $N$ integers, which are either 0 or 1. The $j$-th integer in the $i$-th line of this section being 0 means the $i$-th laser weapon cannot attack the $j$-th giant robot, and 1 means the $i$-th laser weapon can attack the $j$-th giant robot.

Output

A single real number representing the minimum time required for the X Legion to destroy all of the Y Legion's giant robots. The result is considered correct if the absolute error compared to the standard answer does not exceed $10^{-3}$.

Examples

Input 1

2 2
3 10
4 6
0 1
1 1

Output 1

1.300000

Note 1

For the first 0.5 seconds after the battle begins, laser weapon 1 attacks giant robot 2, and laser weapon 2 attacks giant robot 1. Giant robot 1 is completely destroyed, and giant robot 2 has 8 armor value remaining. For the next 0.8 seconds, laser weapons 1 and 2 both attack giant robot 2. Giant robot 2 is completely destroyed.

Input 2

5 4
30 24 11 48 27
4 3 6 1
0 0 0 1 1
1 0 0 1 0
0 1 1 0 1
0 1 0 0 1

Output 2

11.142858

Constraints

For 30% of the data, $1 \le N, M \le 5$. For all data, $1 \le N, M \le 50$, $1 \le A_i \le 10^5$, $1 \le B_i \le 1000$. The input data guarantees that the X Legion can always destroy all of the Y Legion's giant robots.