Problem J
Landscaping
Preparations for a good harvest in Spring start now and farmer John is preparing his field for a good season. He went over-budget last year, as the tractors moving up and down the hills needed more fuel than he expected.
When harvesting, his tractors need to move both horizontally
and vertically across all the land. In the image, you can see a
region at low altitude in light green and a region at high
altitude in dark green. When harvesting, his tractors will have
to cross all the hills marked in red and they will have to go
up or down
This year, he is wondering whether he should level some parts of his field before sowing in order to lower his harvesting costs later on. Can you help him decide where the bulldozers should work in order to lower his costs?
Farmer John knows that his tractors need
What is the minimum amount of money he will have to pay this season?
Task
Given a description of the field, the price to change the height of a patch of land and the price his tractors pay when moving between adjacent patches, the goal is to find out the minimum amount that farmer John will have to pay this year.
Input
The first line consists of
The next
Constraints
|
Size of the field. |
|
Cost to change any height or to move between adjacent patches. |
Output
You should output a single line with a single integer representing the minimum amount of money that farmer John will have to pay.
Sample Output Explanation
Farmer John has a
Farmer John needs €
Not changing any patch would cost him €
Sample Input 1 | Sample Output 1 |
---|---|
5 4 1000 2000 ...# #..# ...# ##.. ###. |
11000 |