A country is represented as a matrix of the size \(N \times M\) and each cell is considered to be a city.
There are \(Q\) missions and you are required to accomplish \(K\) missions to receive the tourist certification. In each mission, you are given a source and destination and you need to travel from source to destination.
Each city contains a development cost that depicts the state of development of the city. The development cost of a mission is considered to be the maximum development cost in the path between source and destination.The overall development cost for the certification is the maximum development cost of all the accomplished missions. Your task is to minimize the overall development cost to achieve the certificate.
Note:
- A path can visit a particular cell multiple times. It is possible to go up, down, left, and right from any cell.
- It is not necessary to accomplish the first \(K\) missions. You can accomplish any \(K\) missions out of the given \(Q\) missions.
- It is not necessary to travel from a source to a destination by using the shortest path. You are allowed to take any path to travel from a source to a destination.
Input format
- First line: Four integers \(N\), \(M\), \(Q\), and \(K\) respectively
- Next \(N\) lines: \(M\) integers, where the \(j^{th}\) integer on the \(i^{th}\) line representing \(A_{ij}\)
- Next \(Q\) lines: Four integers \(X_{source}, Y_{source}, X_{destination},\ and\ Y_{destination}\) respectively
Note: It is guaranteed that the source city and destination city do not coincide for a mission.
Output format
Print the minimum value of the overall development cost in accomplishing exactly \(K\) missions.
Input Constraints
\(1 \le N, M \le 500\)
\(1 \le K \le Q \le 5 \times 10^5\)
\(1 \le X_{source}, X_{destination} \le N\)
\(1 \le Y_{source}, Y_{destination} \le M\)
\(1 \le A_{ij} \le 10^9\)
3 3 3 2 1 3 12 14 7 2 5 6 4 1 1 1 2 2 1 1 3 3 1 2 3
6
Here, \(3\) missions have been given and we need to complete \(2\) of them. We can accomplish missions \(1\) and \(3\) to minimize the overall risk.
For mission \(1\): We can travel like this :- \((1, 1)\) -> \((1, 2)\) and riskiness of this mission will be \(3\).
For mission \(3\): We can travel like this :- \((3, 1)\) -> \((3, 2)\) -> \((3, 3)\)-> \((2, 3)\) and riskiness of this mission will be \(6\).
Hence, minimum possible overall riskiness for the certification will be max\((3, 6)\) that is \(6\).
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor
Login to unlock the editorial
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor