The Fire Rises !
All submissions for this problem are available.
James Moriarty started fire at M places in London. Sherlock Holmes has been called to help extinguish the fires as quickly as possible. There are exactly N fire stations in the city, each having infinite amount of fire trucks. But the time taken by each fire station to fill a truck is different and the fire stations can only fill one truck at a time. Initially all the fire trucks are empty.
Given the time taken by each fire station to fill one truck and the time taken for a fire truck to reach the jth place from the ith fire station, Sherlock needs to tell the minimum time taken to extinguish the fire at all places.
First line contains T,(T<=50) the no. of test cases.
Each line of first test case contains two integers N and M,(N,M <=50) where N denotes the no. of fire stations and M denotes the no. of places under fire.
Next line contains N space separated integers, where the ith integer denotes the time taken (1<=time taken<=20) by ith fire station to fill one truck.
Then next N lines will follow, each containing M integers, where the integer at ith row and jth column denotes the time taken (1<=time taken<=20) by a fire truck from ith fire station to reach jth place.
Output of each test case is a single line denoting the minimum time required to extinguish the fire completely.
Consider that as soon as a fire truck reaches the place, the fire extinguishes there in no time.
Each place will require exactly one truck to extinguish the fire.
Fire truck once used can not be used again.
There are infinite number of fire trucks at every station.
Input: 1 3 4 2 5 4 1 2 3 1 2 3 1 2 2 2 3 1 Output: 6
The 1st fire station sends trucks to both 1st and 4th place. Time Taken=5
The 2nd fire station sends a truck to 3rd place. Time Taken=6
The 3rd fire station sends a truck to 2nd place. Time Taken=6
|Time Limit:||3 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.