Damaged Roads :
Difficulty Level : Hard
Submissions : 819
Asked In :
Marks :10
: 10 | : 4
You are the Prime Minister of a country and once you went for a world tour.
After 5 years, when you returned to your country you were shocked to see the condition of the roads between the cities. So, you plan to repair them, but you cannot afford to spend a lot of money.
The country can be represented as a N*M grid, where Country[i,j] is a city.
The cost of repairing a repairing a road between [i,j] and [i+1,j] is A[i].
The cost of repairing a road between [i,j] and [i,j+1] is B[i].
Return the minimum cost of repairing roads such that all cities become a connected network.
As the cost can be large, return the cost modulo $$$10^9+7$$$.
First line contains 2 space separated values N , M.
Second line contains N-1 values corresponding to content of A.
Third line contains M-1 values corresponding to content of B.
Constraints
$$$2 \le N,M \le 1e5$$$
$$$0 \le A[i],B[i] \le 1e3$$$
Return an integer representing the minimum possible cost.
4 4 1 1 1 1 1 2
16
4 4 1 2 3 4 5 6
39
