P3324 [SDOI2015] Interstellar War

In the year $3333$, on a certain planet in the Milky Way, the X Legion and the Y Legion are fighting fiercely. At a certain stage of the battle, the Y Legion sends $N$ giant robots to attack the X Legion’s position. The $i$-th giant robot has an armor value of $A_i$. When a robot’s armor value drops to $0$ or below, the robot is destroyed. The X Legion has $M$ laser weapons. The $i$-th laser weapon can reduce the armor of a single giant robot by $B_i$ per second. The laser weapons’ attacks are continuous over time. These laser weapons are peculiar: each weapon can attack only certain designated enemies. Seeing their robots being destroyed one after another, the Y Legion urgently needs to issue more commands. To this end, the Y Legion needs to know the minimum time the X Legion requires to destroy all of the Y Legion’s giant robots. However, they cannot compute this themselves, so they ask you for help.

The first line contains two integers, $N, M$. The second line contains $N$ integers, $A_1, A_2 \cdots A_N$. The third line contains $M$ integers, $B_1, B_2 \cdots B_M$. Each of the next $M$ lines contains $N$ integers, each being $0$ or $1$. In this part, the $j$-th integer of the $i$-th line is $0$ if the $i$-th laser weapon cannot attack the $j$-th giant robot, and $1$ if it can.

Output a single real number: the minimum time required for the X Legion to destroy all of the Y Legion’s giant robots. Answers with an absolute error not exceeding $10^{-3}$ are accepted.

- Sample Explanation 1: For the first $0.5$ seconds, laser weapon $1$ attacks robot $2$, and laser weapon $2$ attacks robot $1$. Robot $1$ is completely destroyed; robot $2$ has $8$ armor remaining. For the next $0.8$ seconds, laser weapons $1$ and $2$ attack robot $2$ simultaneously. Robot $2$ is completely destroyed. - Constraints: For all testdata, $1 \le N, M \le 50$, $1 \le A_i \le 10^5$, $1 \le B_i \le 1000$, and the input guarantees that the X Legion can destroy all of the Y Legion’s giant robots. Translated by ChatGPT 5