P1902 Assassinate the Ambassador

A certain organization is planning the assassination of an ambassador. They arrive at the embassy and prepare to carry out the plan. To enter the embassy, they must first get through the defensive maze in front of it. The maze consists of $n \times m$ identical small rooms. Each room is connected by doors to its four neighboring rooms. In row $n$, there are $m$ mechanisms located in its $m$ rooms, and all of these mechanisms must be switched on to enter the embassy. The $m$ rooms in row $1$ each has a door that opens to the outside; these are the entrances to the maze. Except for the rooms in rows $1$ and $n$, every room has a laser damage device installed by the embassy’s security, which will inflict some damage on anyone entering the room. The damage value of the room at row $i$, column $j$ is $p_{i,j}$ (all $p$ values in rows $1$ and $n$ are $0$). The organization wants to enter the maze and switch on all mechanisms with the minimum damage cost. They may send any number of people through any entrances, but they must reach every room in row $n$. A soldier’s damage is the maximum damage value among all rooms on his path to some mechanism. The whole team’s damage is the maximum among the damages of all soldiers. Given full knowledge of the maze, they need to determine how to arrange the routes so that the team’s damage is minimized.

The first line contains two integers $n, m$, representing the size of the maze. Then follow $n$ lines, each containing $m$ numbers. The number at row $i$, column $j$ is $p_{i,j}$.

Output a single number representing the minimum damage cost.

- For $50\%$ of the testdata, $n, m \leq 100$. - For $100\%$ of the testdata, $n, m \leq 1000$, $p_{i,j} \leq 1000$. Translated by ChatGPT 5