Development Cost

★★★★★

3.2

8 votes

Algorithms, Binary Search, Depth First Search, Disjoint set, Easy, Graphs, Life-cycle assessment, Searching

Details

Submissions

Discussion

Editorial

Problem

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$

Sample Input

Sample Output

Time Limit: 2

Memory Limit: 256

Source Limit:

Explanation

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$ .

Contributers:

Ashish Gupta

Pranjal Jain