Problem E
Ice Cream

Ice cream is a difficult topic. You are at the ice cream store and have some trouble deciding how you want your ice cream. How many scoops? What flavours? In what order? The only way to ensure that you are making the right decisions is to approach the problem systematically.

Therefore, you examine each of the $k$ flavours and estimate that the tastiness of a scoop of the $i$th flavour is $t_ i$. However, you are aware that some flavours complement each other, resulting in a tastiness greater than the sum of the individual flavours, whereas others just do not go very well together. Therefore, you have estimated the additional tastiness experienced whenever a scoop of one flavour is directly on top of a scoop of another, and what happens when you put two scoops of the same flavour on top of each other. The additional tastiness experienced whenever flavour $i$ is on top of flavour $j$ is $u_{i,j}$. Of course, you would like to maximize the total tastiness of your ice cream, but there are two problems.

Firstly, your stomach is, regrettably, finite. Therefore, you do not want to order more that $n$ scoops. You may order fewer scoops, if this is better.

Secondly, ice cream isn’t free. Each scoop costs $a$ gold coins, and the cone costs $b$ gold coins (regardless of the number of scoops of ice cream you buy).

You would like to find the maximum possible tastiness per gold coin ratio. The store has an infinite amount of each flavour.

Input

The first line of input consists of the integers $n$ ($1 \leq n \leq 2 \cdot 10^9$), $k$ ($1 \leq k \leq 100$), $a$ and $b$ ($1 \leq a,b \leq 200$).

The following line consists of $k$ integers $t_ i$ ($-200 \leq t_ i \leq 200$), the tastiness of each of the flavours.

The following $k$ lines each contain $k$ integers. The $j$th number on the $i$th line is the additional tastiness $u_{i,j}$ ($-200 \leq u_{i,j} \leq 200$).

Output

If it is impossible to get an ice cream with positive tastiness, display $0$.

Otherwise, display the largest possible value of the quotient of the tastiness and the cost of an ice cream.

Your answer will accepted if it is within a relative or absolute error of at most $10^{-6}$ of the correct answer.

20 3 5 5
0 0 0
0 -10 0
30 0 0
0 0 0

2

10 1 8 20
5
0

0.500000000